java - Java中高效的二项式随机数生成器代码

Question

相关问题是:Algorithm to generate Poisson and binomial random numbers?

我只是将她的描述用于二项式随机数:

For example, consider binomial random numbers. A binomial random number is the number of heads in N tosses of a coin with probability p of a heads on any single toss. If you generate N uniform random numbers on the interval (0,1) and count the number less than p, then the count is a binomial random number with parameters N and p.

Algorithm to generate Poisson and binomial random numbers? 中有一个简单的解决方案通过使用迭代:

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++;
   }
}

该实现是 Luc Devroye 在他的文本“非均匀随机变量生成”的第 522 页上的“第二等待时间方法”的变体。

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