我只用她对二项式随机数的描述:
例如,考虑二项式随机数。二项式随机数是硬币N次抛掷的正面数目,其中任何一次抛掷的正面概率为p。如果您在时间间隔(0,1)上生成N个统一随机数,并且对小于p的数进行计数,则该计数是具有参数N和p的二项式随机数。
算法中有一个简单的解决方案可以生成泊松和二项式随机数?通过使用迭代:
相关的问题是:生成泊松和二项式随机数的算法?
例如,考虑二项式随机数。二项式随机数是硬币N次抛掷的正面数目,其中任何一次抛掷的正面概率为p。如果您在间隔(0,1)上生成N个统一随机数,并计算出小于p的数,则该计数是具有参数N和p的二项式随机数。
在算法中有一个简单的解决方案[可以生成泊松和二项式随机数?](http://codingdict.com/questions/115608通过使用迭代:
public static int getBinomial(int n, double p) { int x = 0; for(int i = 0; i < n; i++) { if(Math.random() < p) x++; } return x; }
但是,我追求二项式随机数生成器的目的只是为了避免效率低下的循环(i从0到n)。我的n可能很大。p通常很小。
我的情况的一个玩具示例可能是:n = 1 * 10 ^ 6,p = 1 * 10 ^(-7)。
n的范围可以从1 * 10 ^ 3到1 * 10 ^ 10。
如果您的p价值很小,那么您会比引用的天真的实现更喜欢这一点。它仍然会循环,但是预期的迭代次数是多少,O(np)因此对于较小的p值来说它相当快。如果您使用的是大p值,请替换p为q = 1-p并从中减去返回值n。显然,这将是最坏的时候p = q = 0.5。
p
O(np)
q = 1-p
n
p = q = 0.5
public static int getBinomial(int n, double p) { double log_q = Math.log(1.0 - p); int x = 0; double sum = 0; for(;;) { sum += Math.log(Math.random()) / (n - x); if(sum < log_q) { return x; } x++; } }
该实现是Luc Devroye在其文章“非均匀随机变量生成”的第522页上的“第二个等待时间方法”的变体。
有一些基于接受/拒绝技术的更快的方法,但是实现起来实际上要复杂得多。