別名方法

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

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

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

 输出一个均匀的随机变量 。
 记  及 。（此时  均匀分布于 }， 均匀分布于 。）
 如果 ，则返回 。这是有偏硬币抛投实验。
 否则，返回 。

Marsaglia等人曾提出名为「平方直方图」的概率表的替代方案。该方案在上述第3步使用 （其中 ）作为判断条件，从而无需计算 。

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

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

 「溢满」组：，
 「不满」组： 且  尚未初始化，
 「恰好」组： 或  已被初始化。

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

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

 任意从「溢满」组和「不满」组各选择一个元素  和 。（若其中一个存在，则另一个也必然存在。）
 别名表中索引为  的空间尚未被设置，将其设置为 ：。
 更新概率表中索引为  的空间： 。
 元素  现在应归为「恰好」组。
 对于元素 ，根据更新后的 ，将其分在恰当的组中。

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

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

别名表的构造不唯一。

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

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

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

再举一个例子，当概率特别不平衡时，会有很多  的情形。例如，如果  且 ；那么多数时候，只需少量随机比特即可决定结果为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/ransampl Joachim Wuttke：C实现，一个小的C语言库
 https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 Liam Huang：C++实现

 参考文献 

Category:伪随机数生成器