一种在n*p很小时工作的二项随机数生成算法
我需要生成二项式随机数：
例如，考虑二项式随机数。二项式随机数是指硬币的N个掷头数，其概率p为一枚硬币的头数。如果在区间(0,1)上生成N个均匀随机数，并对小于p的数进行计数，则计数是参数N和p的二项式随机数。
在我的例子中，我的N可以从1*10^3到1*10^10，我的p大约是1*10^(-7)。
我的n*p通常在1*10^(-3)左右。
有一个简单的实现可以通过循环生成这样的二项式随机数：
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;
}这个本机实现非常慢。我尝试了在Colt (http://acs.lbl.gov/software/colt/)库中实现的验收拒绝/反转方法1。它的速度非常快，但是当n*p不是很小时，生成的数的分布只与本机实现相一致。在我的情况下，当n*p = 1*10^(-3)时，本机实现仍然可以在多次运行后生成数字1，但接受拒绝/反转方法永远不能生成数字1(总是返回0)。
有人知道这里有什么问题吗？或者你能提出一个更好的二项式随机数生成算法来解决我的情况。
1 V. Kachitvichyanukul，B.W. Schmeiser (1988)：二项式随机变量生成，ACM 31,216-222的通信。
回答 2
Stack Overflow用户
发布于 2014-05-10 13:48:05
如果n*p是一个固定的小数t，且n远大于1/t，则二项分布与泊松分布非常接近，后者返回k的概率为e^{-t} ^k/k！
这是一些伪码
r=e^t * RandomReal[0,1];
s=1;
k=0;
While[s<r,
(k++; s=s+t^k/k!;)]
Return k;如果t真的很小，它将很难区分这和一个例程之间的区别，它只是返回的概率为1-t和t的其他时间。例如，如果t=0.001和n是大的，那么k的各种值的概率是
k=0 0.9990005
k=1 0.0009990
k=2 0.0000005
k>2 1.7 * 10^{-10}Stack Overflow用户
发布于 2014-05-10 13:13:01
在np很小的情况下，只有极小的n值才有可能。您可以计算出这些概率，然后使用方法。如果您感到格外谨慎，您可以计算出高于您准备处理的值发生的概率，并转移到具有此概率的特殊情况方法，例如生成第二个别名表，以处理在您处理的第一个别名方法之上的最可能的N值。
https://stackoverflow.com/questions/23579630
复制相似问题
腾讯云开发者
