我有一个概率问题,我需要在合理的时间内进行模拟。简单的说,我有30个不公平的硬币,每个硬币有不同的已知概率。然后我想问一些问题,比如“什么是正确的12的概率?”,或者“至少5会是尾巴的概率是多少?”。我知道基本的概率论,所以我知道我可以枚举所有(30选择x)的可能性,但这不是特别的可扩展性。最坏的情况(30选15)有超过1.5亿组合。从计算的角度来看,有没有更好的方法来处理这个问题?结果概率算法
任何帮助非常感谢,谢谢! :-)
我有一个概率问题,我需要在合理的时间内进行模拟。简单的说,我有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个概率的向量(表示在0..12中,i代表P(n-1,i))。使用上述递归关系为P(n,i)构建一个新的向量13。重复,直到n = 30。当然,你从n = 0的矢量(1,0,0,0,...)开始(因为没有硬币,你一定没有头)。
使用此算法的最坏情况是O(n^2)而不是指数。
这实际上是一个有趣的问题。我受到启发,写了一篇关于它的博客文章,详细介绍了公平与不公平投币一直抛到OP对每枚硬币有不同概率的情况。你需要一种称为动态规划的技术来解决多项式时间的问题。
一般问题:鉴于Ç,一系列Ñ硬币p到pÑ其中p我表示概率i -th co在即将到来的头脑中,抛掷所有硬币的概率是多少?
这意味着求解以下递推关系:
P(Ñ,ķ,Ç,我)= p我 X P( n -1,k -1,Ç,我 1)+(1-p我)×P(Ñ,ķ,Ç,我 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 A序列我到pÑ包含ķ头的概率。
有关二项概率的更深入介绍以及关于如何应用动态规划的讨论,请参阅Coin Tosses, Binomials and Dynamic Programming。
感谢您的答案和您的博客文章,我现在相信了解动态编程:) – Konerak 2011-02-26 17:25:49
伪代码:
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)? – dirkgently 2010-08-19 06:53:02
请参阅更新后的帖子。 – cletus 2010-08-20 03:55:24