Java中有效的二项式随机数生成器代码

Question

相关问题是:生成泊松和二项式随机数的算法？

我只是对二项式随机数进行描述:

例如,考虑二项式随机数.二项式随机数是硬币的N次投掷中的头数,在任何单次投掷中具有头部的概率p.如果在区间(0,1)上生成N个均匀随机数并计算小于p的数,则计数是具有参数N和p的二项式随机数.

算法中有一个简单的解决方案来生成泊松和二项式随机数？通过使用迭代:

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.

Answer 1

如果你的p值很小,你会比你引用的天真实现更喜欢这个.它仍然循环,但预期的迭代次数O(np)对于小p值来说非常快.如果您正在处理大p值,请替换p为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++;
   }
}

该实现是他的文本"非均匀随机变体生成"第522页中Luc Devroye的"第二等待时间方法"的变体.

有更快的方法基于接受/拒绝技术,但它们实现起来要复杂得多.