相关的问题是：Algorithm生成泊松和二项随机数？

我只是把她描述为二项随机数：

I just take her description for the Binomial random number:

例如，考虑二项随机数。二项式随机   号是一个硬币的在N-头的数量掷以概率p   对任何单一折腾了头。如果产生N个均匀随机   在区间号码（0,1），并计算比数P少，那么   伯爵是一个二项式随机数的参数n和p。

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生成泊松和二项随机数中通过使用迭代：

There is a trivial solution in Algorithm to generate Poisson and binomial random numbers? through using iterations:

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

然而，缩拢二项式随机数发生器的我的目的只是为了避免低效环路（ⅰ从0到n）。我的n可以取非常大。且p是通常非常小。

However, my purpose of pursing a binomial random number generator is just to avoid the inefficient loops (i from 0 to n). My n could be very large. And p is often very small.

我的案子的玩具例子是：N = 1 * 10 ^ 6，P = 1 * 10 ^（ - 7）

A toy example of my case could be: n=1*10^6, p=1*10^(-7).

第n范围可以从1 * 10 ^ 3〜1×10 ^ 10。

The n could range from 1*10^3 to 1*10^10.

推荐答案

如果你有小 P 值，你会喜欢比你提到的天真实现这更好。它仍然环，但反复的预期数量为 O（NP）所以它的pretty的速度快于小型 P 值。如果你正在使用大 P 值，替换 P 与 Q = 1-P 和减去返回值n 。显然，这将是在最坏的情况时， P = Q = 0.5 。

If you have small p values, you'll like this one better than the naive implementation you cited. It still loops, but the expected number of iterations is O(np) so it's pretty fast for small p values. If you're working with large p values, replace p with q = 1-p and subtract the return value from n. Clearly, it will be at its worst when 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++;
   }
}

的实施是吕克Devroye的第二等待时间的方法，他的文本522页上的一个变种非均匀随机变量产生。

The implementation is a variant of Luc Devroye's "Second Waiting Time Method" on page 522 of his text "Non-Uniform Random Variate Generation."

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

There are faster methods based on acceptance/rejection techniques, but they are substantially more complex to implement.