Java中有效的二项式随机数生成器代码
相关问题是： 生成泊松和二项式随机数的算法？
我只是对二项式随机数进行描述：
例如，考虑二项式随机数。 二项式随机数是硬币N次投掷中的头数，其中任意一次投掷的头部概率为p。 如果在区间（0,1）上生成N个均匀随机数并计算小于p的数，则计数是具有参数N和p的二项式随机数。
算法中有一个简单的解决方案来生成泊松和二项式随机数？ 通过使用迭代：
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。
如果你有一个小的p值，你会比你引用的天真实现更喜欢这个。 它仍然循环，但预期的迭代次数是O(np)所以它对于小p值来说非常快。 如果您正在使用大p值，请用q = 1-p替换q = 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++; } }
该实现是他的文本“非均匀随机变体生成”第522页中Luc Devroye的“第二等待时间方法”的变体。
有更快的方法基于接受/拒绝技术，但它们实现起来要复杂得多。
我可以想象一种通过常数因子加速它的方法（例如4）。
投掷4次后，你将投掷头部0,1,2,3或4。
它的概率类似于[0.6561,0.2916,0.0486,0.0036,0.0001]。
现在，您可以生成一个数字随机数并模拟4个原始投掷。 如果不清楚我怎么能详细说明一点。
这种方式经过一些原始的预先计算后，您可以将该过程加速几乎4次。 它要求精确的唯一要求是随机生成器的粒度至少为p ^ 4。