-
29-09-2019 - |
题
我有一个概率问题,我需要在合理的时间内进行模拟。以简化的形式,我有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是“我的硬币是头”的概率)。
现在,您可以在动态编程算法中使用此关系。具有13个概率的向量(代表p(n -1,i)的i在0..12中)。使用上述复发关系为P(n,i)构建13个新向量。重复直到n = 30。当然,您从向量(1、0、0、0,...)开始n = 0(因为没有硬币,您一定不会有头部)。
使用此算法的最坏情况是O(n^2),而不是指数。
其他提示
这实际上是一个有趣的问题。我受到启发写一篇有关它的博客文章,详细介绍了公平与不公平的硬币一路扔到OP的情况下,每个硬币的可能性都不同。您需要一种称为动态编程的技术来在多项式时间内解决此问题。
一般问题: 给出 C, , 一系列的 n 硬币 p1 到 pn 在哪里 p一世 表示 一世- the头来了,概率是多少 k 扔掉所有硬币的头部?
这意味着解决以下复发关系:
p(n,k,C,一世) = p一世 X p(n-1,k-1,C,一世+1) + (1-p一世) X p(n,k,C,一世+1)
执行此操作的Java代码片段是:
private static void runDynamic() {
long start = System.nanoTime();
double[] probs = dynamic(0.2, 0.3, 0.4);
long end = System.nanoTime();
int total = 0;
for (int i = 0; i < probs.length; i++) {
System.out.printf("%d : %,.4f%n", i, probs[i]);
}
System.out.printf("%nDynamic ran for %d coinsin %,.3f ms%n%n",
coins.length, (end - start) / 1000000d);
}
private static double[] dynamic(double... coins) {
double[][] table = new double[coins.length + 2][];
for (int i = 0; i < table.length; i++) {
table[i] = new double[coins.length + 1];
}
table[1][coins.length] = 1.0d; // everything else is 0.0
for (int i = 0; i <= coins.length; i++) {
for (int j = coins.length - 1; j >= 0; j--) {
table[i + 1][j] = coins[j] * table[i][j + 1] +
(1 - coins[j]) * table[i + 1][j + 1];
}
}
double[] ret = new double[coins.length + 1];
for (int i = 0; i < ret.length; i++) {
ret[i] = table[i + 1][0];
}
return ret;
}
这是在构造一张表,该表显示了来自 p一世 到 pn 包含 k 头。
为了更深入地介绍二项式概率和有关如何应用动态编程的讨论 硬币抛弃,二项式和动态编程.
伪代码:
procedure PROB(n,k,p)
/*
input: n - number of coins flipped
k - number of heads
p - list of probabilities for n-coins where p[i] is probability coin i will be heads
output: probability k-heads in n-flips
assumptions: 1 <= i <= n, i in [0,1], 0 <= k <= n, additions and multiplications of [0,1] numbers O(1)
*/
A = ()() //matrix
A[0][0] = 1 // probability no heads given no coins flipped = 100%
for i = 0 to k //O(k)
if i != 0 then A[i][i] = A[i-1][i-1] * p[i]
for j = i + 1 to n - k + i //O( n - k + 1 - (i + 1)) = O(n - k) = O(n)
if i != 0 then A[i][j] = p[j] * A[i-1][j-1] + (1-p[j]) * A[i][j-1]
otherwise A[i][j] = (1 - p[j]) * A[i][j-1]
return A[k][n] //probability k-heads given n-flips
最坏的情况= o(kn)