让我们假设我有一组概率[0.1，0.6，0.2，0.1]。我想从这组概率中采样位置。例如当我采样时，应该比其他位置更频繁地获得位置1。我知道我可以用Matlab（使用mnrnd命令）或其他语言来实现。但是，我想知道算法细节。我想知道一个非常简单的算法，可用于从多项式分布中进行采样。
在您的情况下，创建一个包含累积概率的数组cdf = [0.1, 0.7, 0.9, 1.0]。生成U，一个统一的（0,1）随机值。选择第一个索引，例如cdf[i] <= U。对于少量结果，可以通过线性搜索（O（n））来完成，如果结果数量很大，则可以使用二元搜索（O（log n））。
别名表要求您使用条件概率来构造主要元素和别名值的表，使得对于每个主要/别名对，总概率是相同的。然后，您可以使用一个随机数来选择表中的一列（具有相等的概率），并使用第二个值在主别名和别名之间进行二项式选择。一旦构建了表，运行时间为O（1），这需要O（n）的努力。有关详情，请参见Wikipedia。请注意，每个结果需要两个制服，因此这不是反转，并且您无法做类似生成antithetic variates的有趣技巧。