产生poisson和二项式随机数的算法？

Question

我一直在环顾四周，但是我不确定该怎么做。

我发现此页面在最后一段中说：

使用以下简单公式即可获得从poisson分布中提取的随机数的简单生成器：如果x 1，x 2，…是在零和一之间均匀分布的随机数序列，则k是第一个整数，乘积x 1 ·x 2 ·…·x k + 1 <e -λ

我找到了另一页 描述如何生成二项式数的页面，但是我认为它使用的是泊松生成的近似值，这对我没有帮助。

例如，考虑二项式随机数。二项式随机数是硬币N次抛掷的正面数目，其中任何一次抛掷的正面概率为p。如果您在间隔（0,1）上生成N个统一随机数，并计算出小于p的数，则该计数是具有参数N和p的二项式随机数。

我知道有图书馆可以做到这一点，但我不能使用它们，只能使用该语言提供的标准统一生成器（在这种情况下为Java）。

Answer 1

poisson分布

下面是维基百科说，克努特说，这样做：

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（我从Wikipedia文章链接到该书）的非均匀随机变量生成（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）。根据这些值通常的大小以及您需要调用生成器的频率，您可能需要更好的算法。我上面链接的论文有更复杂的算法，这些算法可以在恒定时间内运行，但是我会将这些实现留给读者练习。:)