math - 将随机数生成循环变成一个方程？

Question

这是一些伪代码:

count = 0
for every item in a list
    1/20 chance to add one to count

这或多或少是我当前的代码，但该列表中可能有数十万个项目；因此，它很快就会变得低效。 (这不是叫 0(n) 什么的吗？)

有没有办法把它压缩成一个方程？

Answer 1

让我们看看您描述的随机变量的属性。报价 Wikipedia :

The binomial distribution with parameters n and p is the discrete probability distribution of the number of successes in a sequence of n independent yes/no experiments, each of which yields success with probability p.

让 N是列表中的项目数， C是表示 count 的随机变量你从你的伪代码中获得。 C将遵循二项式概率分布(如下图所示)，p = 1/20:



剩下的问题是如何有效地轮询具有所述概率分布的随机变量。有许多库允许您从具有指定 PDF 的随机变量中抽取样本。我从来没有自己实现过，所以我不太清楚细节，但是很多都是开源的，你可以自己引用实现。

以下是计算 count 的方法与 numpy Python中的库:

n, p = 10, 0.05                  # 10 trials, probability of success is 0.05
count = np.random.binomial(n, p) # draw a single sample