别名方法

在计算机科学的计算中，别名方法（英语：Alias Method），又称别名采样法、别名表法、别名表采样法，是一个由A. J. 沃克（英语：A. J. Walker）提出的用于从一个离散的概率分布中取样的高效算法。 该算法可在任意的概率分布 p_i 下返回整数值 1 ≤ i ≤ n。此类算法通常需要 O(n log n) 或 O(n) 的预处理时间，之后可 O(1) 时间复杂度内进行随机取样。

算法

算法在内部构造两张表：概率表 U_i 和别名表 K_i (1 ≤ i ≤ n)。随机取样时，首先由一个均匀的骰子确定表内索引。而后，根据概率表索引位置存储的概率，进行一次有偏硬币抛投实验，从而确定最终结果是 i 还是 K_i。

具体来说，算法进行如下操作：

1. 输出一个均匀的随机变量 0 ≤ x < 1。
2. 记 i = ⌊nx⌋ + 1 及 y = nx + 1 − i。（此时 i 均匀分布于 {1, 2, …, n}，y 均匀分布于 [0, 1)。）
3. 如果 y < U_i，则返回 i。这是有偏硬币抛投实验。
4. 否则，返回 K_i。

Marsaglia等人曾提出名为“平方直方图”的概率表的替代方案。该方案在上述第3步使用 x < V_i（其中 V_i = (U_i + i − 1)/n）作为判断条件，从而无需计算 y。

表的生成

可以在原概率分布上，增加若干 p_i = 0 的情形，以将 n 增加到某些便于计算的值，例如2的幂。

生成表的第一步是执行 U_i = np_i，由此将表中的元素为三类：

• “溢满”组：U_i > 1，
• “不满”组：U_i < 1 且 K_i 尚未初始化，
• “恰好”组：U_i = 1 或 K_i 已被初始化。

若 U_i = 1，则相应的别名表值 K_i 永远不会被用到，因而其取值是无关紧要的。但令 K_i = i 会更加自然。

只要不是所有的元素是在“恰好”组，就重复执行以下步骤：

1. 任意从“溢满”组和“不满”组各选择一个元素 U_i > 1 和 U_j < 1。（若其中一个存在，则另一个也必然存在。）
2. 别名表中索引为 j 的空间尚未被设置，将其设置为 i：K_j = i。
3. 更新概率表中索引为 i 的空间： U_i = U_i − (1 − U_j) = U_i + U_j − 1。
4. 元素 j 现在应归为“恰好”组。
5. 对于元素 i，根据更新后的 U_i，将其分在恰当的组中。

每轮迭代至少使一个元素进入“恰好”组。因此，至多经过 n−1 轮迭代后，该过程必然终止。每轮迭代可在 O(1) 时间内完成，从而生成表的过程可在 O(n) 时间内完成。

Vose<ref name="Vose">指出，浮点数四舍五入带来的误差可能导致第1步中提到的断言不成立。若其中一个组别已无剩余元素，则可将另一个组内剩余的其他元素的 U_i 以课忽略的误差设置为1。

别名表的构造不唯一。

由于当 y < U_i 时，查表过程会稍微快一些（因为无需访问 K_i）；生成表时，人们会期望最大化所有 U_i 的和。然而，这是一个NP困难问题<ref name="marsaglia">，但以贪心算法可以合理地接近这一目标：从最富有者拆解给最贫穷者。也就是说，在每次迭代中，选取最大的 U_i 和最小的 U_j。在这个过程中，我们要对 U_i 进行排序，于是需要 O(n log n) 的时间复杂度。

效率

尽管在产生均匀随机变量非常快时，Alias方法非常高效；但在某些情况下，就随机比特的使用而言，还有很大优化空间。这是因为，哪怕其实只需少量随机比特，Alias方法每回也都使用随机变量 x 的所有随机比特。

举个例子，当概率特别平衡时，会有很多 U_i = 1 的情形；此时 K_i 是不必要的。因此，产生 y 就是浪费时间了。例如，如果 p₁ = p₂ = 1⁄2，然后一个3 位的随机变量 x 可以用来做32次随机取样，但Alias方法只能用一次。

再举一个例子，当概率特别不平衡时，会有很多 U_i ≈ 0 的情形。例如，如果 p₁ = 0.999 且 p₂ = 0.001；那么多数时候，只需少量随机比特即可决定结果为1。在这种情况下，Marsaglia 提出的表方法<ref name="marsaglia">更为有效。若在相同概率分布下进行大量重复取样，平均而言，我们只需远少于1个随机比特即可。利用算术编码技术，在给定二元熵函数时，我们可以达到这一下限。

文献

• Donald Knuth, 计算机程序设计艺术, 第二卷：半数值算法，3.4.1 节

实现

• http://www.keithschwarz.com/darts-dice-coins/（页面存档备份，存于互联网档案馆） Keith Schwarz：对算法的详细解释，数值稳定版本的Vose算法，Java实现
• http://apps.jcns.fz-juelich.de/ransamplArchive.is的存档，存档日期2013-08-15 Joachim Wuttke：C实现，一个小的C语言库
• https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 Liam Huang：C++实现