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

2022-09-02 00:35:54

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

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

从泊松分布中获取的随机数的简单生成器是使用以下简单公式获得的:如果 x1, x2, ...是一个随机数序列,在零和 1 之间均匀分布,k 是乘积 x1 ·x2 ·... ·xk+1 < e-λ

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

例如,考虑二项式随机数。二项式随机数是掷硬币的 N 次掷出中的人头数,在任何一次投掷中,掷硬币的概率为 p。如果在区间 (0,1) 上生成 N 个均匀随机数并对小于 p 的数进行计数,则该计数是具有参数 N 和 p 的二项式随机数。

我知道有库可以做到这一点,但我不能使用它们,只有语言提供的标准统一生成器(在这种情况下是java)。


答案 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)。根据这些值通常有多大,以及需要调用生成器的频率,您可能需要更好的算法。我上面链接到的论文具有更复杂的算法,这些算法在恒定时间内运行,但我将这些实现留给读者作为练习。:)


答案 2

对于这个问题和其他数字问题,圣经是数字食谱书。

这里有一个免费的C版本:http://www.nrbook.com/a/bookcpdf.php(需要插件)

或者你可以在谷歌图书上看到它:http://books.google.co.uk/books?id=4t-sybVuoqoC&lpg=PP1&ots=5IhMINLhHo&dq=numerical%20recipes%20in%20c&pg=PP1#v=onepage&q=&f=false

C代码应该很容易转移到Java。

这本书值得一试,它为许多数字问题提供了黄金的重量。在上面的网站上,您还可以购买该书的最新版本。


推荐