algorithm - 给定 n 个独立试验的个体概率，如何准确计算 k 个成功的概率？

Question

给定n次独立试验的个体概率P_i，1≤i≤n，我如何计算k次试验成功的概率？

在特殊情况 k=n 中，n 次成功的概率只是概率的乘积。但是我如何计算 1 的 k 次成功试验的概率

我可以手动计算的小例子:

1. `P = [0.8, 0.7]，k=1。一次试验成功的概率为 0.8*(1-0.7) + (1-0.8)*0.7 = 0.38
2. `P = [0.8, 0.7, 0.6]，k=2。一次试验成功的概率为 0.8*0.7*(1-0.6) + 0.8*(1-0.7)*0.6 + (1-0.8)*0.7*0.6 = 0.452

但是这种学校方法无法扩展到大型示例，因为总和中有“n 选择 k”项。例如n=50, k=20, P=[0.01,0.03,0.05,...,0.99]，就会有“50选20”项，即47129212243960。当然一定有更简单的计算方法概率。

Answer 1

令 P(i, j) 为第一个 i 次试验中 j 次成功的概率。

那么P满足:

P(0, j) = 1 if j == 0 otherwise 0
P(i, j) = p_i * P(i-1, j-1) + (1-p_i) * P(i-1, j)

这是一个简短的 Python 程序，它计算 O(nk) 时间和 O(k) 空间中的概率，本质上是对每个 i 迭代使用上述递归关系。在 p 循环的 i 次迭代之后，数组条目 P[j] 保存 P(i, j)。该代码运行您问题中的三个示例(包括 n=50、k=20 的困难示例)。结果是精确的分数，并且代码基本上立即运行。

from fractions import Fraction as F

def prob(ps, k):
    P = [1] + [0] * k
    for p in ps:
        for j in xrange(k, -1, -1):
            P[j] = p * (P[j-1] if j>0 else 0) + (1 - p) * P[j]
    return P[k]

for tc in [
        ([F(8, 10), F(7, 10)], 1),
        ([F(8, 10), F(7, 10), F(6, 10)], 2),
        ([F(1, 100) + F(2, 100) * i for i in xrange(50)], 20),
        ]:
    print 'ps = [%s]' % ', '.join(map(str, tc[0]))
    print 'k = %s' % tc[1]
    print 'probability = %s' % prob(tc[0], tc[1])
    print

输出:

ps = [4/5, 7/10]
k = 1
probability = 19/50

ps = [4/5, 7/10, 3/5]
k = 2
probability = 113/250

ps = [1/100, 3/100, 1/20, 7/100, 9/100, 11/100, 13/100, 3/20, 17/100, 19/100, 21/100, 23/100, 1/4, 27/100, 29/100, 31/100, 33/100, 7/20, 37/100, 39/100, 41/100, 43/100, 9/20, 47/100, 49/100, 51/100, 53/100, 11/20, 57/100, 59/100, 61/100, 63/100, 13/20, 67/100, 69/100, 71/100, 73/100, 3/4, 77/100, 79/100, 81/100, 83/100, 17/20, 87/100, 89/100, 91/100, 93/100, 19/20, 97/100, 99/100]
k = 20
probability = 6354741607005879635747506856181887568383689465714196334804901357522358768197915724707861/204800000000000000000000000000000000000000000000000000000000000000000000000000000000000000