生成泊松和二项式随机数的算法？

Question

我一直在四处寻找,但我不知道该怎么办.

我发现这个页面在最后一段中说:

使用这个简单的方法得到一个从泊松分布中取得的随机数的简单生成器:如果x ₁,x ₂,...是一个在0和1之间均匀分布的随机数序列,k是第一个整数,乘积x ₁ ·x ₂ ·...·x _{k + 1} <e ^-λ

我发现了另一个描述如何生成二项式数的页面,但我认为它使用的是泊松生成的近似值,这对我没有帮助.

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

我知道有库可以做到这一点,但我不能使用它们,只能使用语言提供的标准统一生成器(在本例中为java).

Answer 1

泊松分布

以下是维基百科说Knuth所说的:

init:
     Let L ? e^(??), k ? 0 and p ? 1.
do:
     k ? k + 1.
     Generate uniform random number u in [0,1] and let p ? p × u.
while p > L.
return k ? 1.

在Java中,那将是:

public static int getPoisson(double lambda) {
  double L = Math.exp(-lambda);
  double p = 1.0;
  int k = 0;

  do {
    k++;
    p *= Math.random();
  } while (p > L);

  return k - 1;
}

二项分布

通过Luc Devroye 的非均匀随机变量生成(PDF)的第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;
}

请注意

这些算法都不是最佳的.第一个是O(λ),第二个是O(n).根据这些值通常的大小以及调用生成器的频率,您可能需要更好的算法.我上面链接的论文有更复杂的算法,它们在恒定的时间内运行,但我会将这些实现作为练习留给读者.:)