algorithm - 结果概率算法

Question

我有一个概率问题，我需要在合理的时间内进行模拟。在简化形式中，我有 30 个不公平的硬币，每个硬币都有不同的已知概率。然后我想问诸如“恰好 12 个正面朝上的概率是多少？”或“至少 5 个正面反面的概率是多少？”之类的问题。

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

非常感谢任何帮助，谢谢! :-)

Answer 1

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

例如，要计算 30 个硬币出现 12 个正面朝上的概率，设 P(n, k) 为前 n 个硬币出现 k 个正面朝上的概率。

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

(这里 p_i 是第 i 个硬币正面朝上的概率)。

您现在可以在动态规划算法中使用此关系。有一个包含 13 个概率的向量(表示 0..12 中 i 的 P(n - 1, i))。使用上述递归关系为 P(n, i) 构建一个新的向量 13。重复直到 n = 30。当然，您从 n=0 的向量 (1, 0, 0, 0, ...) 开始(因为没有硬币，您肯定不会正面朝上)。

使用此算法的最坏情况是 O(n^2) 而不是指数。