一尘不染

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

algorithm

我只用她对二项式随机数的描述:

例如,考虑二项式随机数。二项式随机数是硬币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。

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。


阅读 265

收藏
2020-07-28

共1个答案

一尘不染

如果您的p价值很小,那么您会比引用的天真的实现更喜欢这一点。它仍然会循环,但是预期的迭代次数是多少,O(np)因此对于较小的p值来说它相当快。如果您使用的是大p值,请替换pq = 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页上的“第二个等待时间方法”的变体。

有一些基于接受/拒绝技术的更快的方法,但是实现起来实际上要复杂得多。

2020-07-28