假设我有一个例程，当被调用时，它将使用 RNG 并返回True30% 的时间，False否则。这很简单。True但是，如果我想模拟调用该例程 100 亿次会得到多少结果呢？
在一个循环中调用它 100 亿次将花费太长时间。将 100 亿乘以 30% 将产生 30 亿的统计预期结果，但不会涉及实际的随机性。（结果正好是30 亿的可能性也不是很大。）
是否有一种算法可以模拟这样一系列随机事件的聚合结果，这样如果它被多次调用，它给出的结果将显示与实际运行它多次模拟的随机序列相同的分布曲线，运行在O(1) 时间（即随着要模拟的系列长度的增加不需要更长的运行时间）？
我会说 -它可以在 O(1) 中完成！
描述您的情况的二项分布（在某些情况下）可以通过正态分布来近似。它可以在两者n*p和n*(1-p)大于 5 时完成，所以p=0.3它可以为 all 完成n > 17。什么时候n变得非常大（如数百万），近似值越来越好。
使用Box–Muller 变换可以很容易地计算出具有正态分布的随机数。您需要做的就是两个介于 0 和 1 之间的随机数。Box-Muller 变换从N(0,1)分布中给出两个随机数，称为标准正态。N(μ, σ2)可以使用X = μ + σZ公式来实现，其中Z是标准正态。
经过更深入的思考，我可以提出这个 Python 解决方案，它在 O(log(n)) 中工作并且不使用任何近似值。但是，对于较大的 n，@MarcinJuraszek 的解决方案更合适。
第一步的成本是 O(n)——但你只需要做一次。第二步的成本只是 O(log(n))——本质上是二分查找的成本。由于代码有很多依赖关系，你可以看一下这个截图：
import numpy.random as random
import matplotlib.pyplot as pyplot
import scipy.stats as stats
import bisect
# This is the number of trials.
size = 6;
# this generates in memory an object, which contains
# a full information on desired binomial
# distribution. The object has to be generated only once.
# THIS WORKS IN O(n).
binomialInstance = stats.binom(size, 0.3)
# this pulls a probabilty mass function in form of python list
binomialTable = [binomialInstance.pmf(i) for i in range(size + 1)]
# this pulls a python list from binomialInstance, first
# processing it to produce a cumulative distribution function.
binomialCumulative = [binomialInstance.cdf(i) for i in range(size + 1)]
# this produces a plot of dots: first argument is x-axis (just
# subsequent integers), second argument is our table.
pyplot.plot([i for i in range(len(binomialTable))], binomialTable, 'ro')
pyplot.figure()
pyplot.plot([i for i in range(len(binomialCumulative))], binomialCumulative, 'ro')
# now, we can cheaply draw a sample from our distribution.
# we can use bisect to draw a random answer.
# THIS WORKS IN log(n).
cutOff = random.random(1)
print "this is our cut-off value: " + str(cutOff)
print "this is a number of successful trials: " + str(bisect.bisect(binomialCumulative, cutOff))
pyplot.show()
正如其他评论者所提到的，您可以使用二项分布。但是，由于您要处理大量样本，您应该考虑使用正态分布近似。