我有一个概率的问题，我需要在一个合理的时间量来模拟。在简单的形式，我有30个不公平的硬币每一个不同的已知概率。那么我要问的东西，如什么是正好12将是正面的概率？，或者是什么，至少5将是尾部的概率是多少？。

I have a probability problem, which I need to simulate in a reasonable amount of time. In simplified form, I have 30 unfair coins each with a different known probability. I then want to ask things like "what is the probability that exactly 12 will be heads?", or "what is the probability that AT LEAST 5 will be tails?".

我知道基本的概率论，所以我知道我可以枚举所有（30选X）的可能性，但是这并不特别可扩展性。在最坏的情况下（30选15）拥有超过1.5亿的组合。有没有更好的方法来从计算的角度看解决这个问题？

I know basic probability theory, so I know I can enumerate all (30 choose x) possibilities, but that's not particularly scalable. The worst case (30 choose 15) has over 150 million combinations. Is there a better way to approach this problem from a computational standpoint?

任何帮助是极大的AP preciated，谢谢！ ： - ）

Any help is greatly appreciated, thanks! :-)

推荐答案

您可以使用动态规划方法。

You can use a dynamic programming approach.

例如，要计算12正面的概率出30金币，令P（n，k）的是，有k个正面的前n个硬币的概率。

For example, to calculate the probability of 12 heads out of 30 coins, let P(n, k) be the probability that there's k heads from the first n coins.

则P（N，K）= P_N * P（N - 1，K - 1）+（1 - P_N）* P（N - 1，k）的

Then P(n, k) = p_n * P(n - 1, k - 1) + (1 - p_n) * P(n - 1, k)

（这里p_i为第i个硬币是正面的概率）。

(here p_i is the probability the i'th coin is heads).

现在你可以使用这个关系在动态规划算法。有13概率向量（即重新present P（N - 在0..12 1，I）对我）。建立13对p一个新的载体（N，I）使用上述递推关系。重复，直到N = 30。当然，你开始用向量（1，0，0，0，...）对于n = 0（因为没有硬币，你一定要得到无头）。

You can now use this relation in a dynamic programming algorithm. Have a vector of 13 probabilities (that represent P(n - 1, i) for i in 0..12). Build a new vector of 13 for P(n, i) using the above recurrence relation. Repeat until n = 30. Of course, you start with the vector (1, 0, 0, 0, ...) for n=0 (since with no coins, you're sure to get no heads).

采用这种算法的最坏情况是O（n ^ 2），而不是指数。

The worst case using this algorithm is O(n^2) rather than exponential.