如何对连续负二项分布进行高效采样？

Question

我想做的是利用我对连续负二项分布进行抽样的事实，这是得到头部所需要的试验数的分布，也就是说，如果f(X)是这个分布，那么f(X)给出了在我们遇到头部之前有X个尾部的概率，其中X不必是整数。如果我能对这个分布进行采样，那么我能做的就是，如果X是尾部的数量，那么我就能看到X是大于还是小于信用的数量；如果大于，那么我们用完所有的学分，但什么也没有发生，如果小于或等于，那么好事发生了，我们从学分的数目中减去X。此外，因为分布是连续的，我可以很容易地处理分数学分。

有没有人知道一种方法让我能够有效地对连续负二项分布（也就是从这个分布中产生随机数的函数）进行采样？

Answer 1

这个问题在StatsExchange上可能会得到更好的回答，但在这里我将尝试一下。

您是正确的，尝试直接计算这将是计算昂贵的，因为您无法避免beta和/或gamma函数依赖。我知道的唯一一个统计上有效的近似值是，如果s所需的成功次数很大，而p既不是很小也不是很大，那么你可以用均值和方差的特殊值的正态分布来近似它。你可以在这里读到更多，但我猜这个近似不会普遍适用于你。

负二项分布也可以近似为泊松分布的混合，但这并不能使你摆脱伽马函数的依赖关系。

我所知道的唯一有效的负二项式采样器使用了优化的接受-拒绝技术。本PDF的第10-11页描述了该方法背后的概念。本PDF的第6页（内部第295页）包含使用相关技术对二项式偏差进行采样的源代码。请注意，即使这些方法仍然需要随机的统一偏差以及sqrt()、log()和gammln()调用。对于少量的试验（可能少于100次？）如果仅仅用快速随机数生成器模拟试验比接受-拒绝技术还要快，我一点也不会感到惊讶。一定要从获得一个快速的PRNG开始；他们并非生而平等。

编辑：

只要p不是很大（太接近1.0)，下面的伪代码对于绘制随机离散负二项式分布的值可能是相当有效的。它将返回在达到您的第一个“期望”结果之前所需的试验次数（从分布来看，这实际上是第一个“失败”）：

// assume p and r are the parameters to the neg. binomial dist.
// r = number of failures (you'll set to one for your purpose)
// p = probability of a "success"
double rnd = _rnd.nextDouble(); // [0.0, 1.0)
int k = 0;  // represents the # of successes that occur before 1st failure
double lastPmf = (1 - p)^r;
double cdf = lastPmf;
while (cdf < rnd)
{
    lastPmf *= (p * (k+r) / (k+1));
    cdf += lastPmf;
    k++;
}
return k;
// or return (k+1) to also count the trial on which the failure occurred