我有一个概率问题，我需要在合理的时间内模拟。在简化形式中，我有30个不公平的硬币，每个都有不同的已知概率。然后我想问一些问题，比如“12个脑袋到底有多大的概率？”，或者“至少有5个是尾部的概率是多少？”是的。
我知道基本的概率论，所以我知道我可以列举所有（30选择x）的可能性，但这不是特别可伸缩的。最坏的情况（30选15）有超过1.5亿个组合。有没有更好的方法从计算的角度来解决这个问题？
非常感谢您的帮助，谢谢！：-）
最佳答案
您可以使用动态编程方法。
例如，要计算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。当然，你从向量（1，0，0，0，…）开始，n=0（因为没有硬币，你肯定不会得到头像）。
使用该算法的最坏情况是o（n^2），而不是指数。
关于algorithm - 成果算法的概率，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3519395/