別名方法

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

算法

算法在内部构造两张表:概率 Ui别名表 Ki (1 ≤ in)。随机取样时,首先由一个均匀的骰子确定表内索引。而后,根据概率表索引位置存储的概率,进行一次有偏硬币英语Biased_coin抛投实验,从而确定最终结果是 i 还是 Ki[4]

具体来说,算法进行如下操作:

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

Marsaglia等人曾提出名为「平方直方图」的概率表的替代方案。[5]该方案在上述第3步使用 x < Vi(其中 Vi = (Ui + i − 1)/n)作为判断条件,从而无需计算 y

表的生成

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

生成表的第一步是执行 Ui = npi,由此将表中的元素为三类:

  • 「溢满」组:Ui > 1
  • 「不满」组:Ui < 1Ki 尚未初始化,
  • 「恰好」组:Ui = 1Ki 已被初始化。

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

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

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

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

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

别名表的构造不唯一。

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

效率

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

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

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

文献

实现

参考文献

  1. ^ Walker, A. J. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters. April 1974, 10 (8): 127. doi:10.1049/el:19740097. 
  2. ^ Walker, A. J. An Efficient Method for Generating Discrete Random Variables with General Distributions. ACM Transactions on Mathematical Software. September 1977, 3 (3): 253–256. doi:10.1145/355744.355749. 
  3. ^ Vose, Michael D. A linear algorithm for generating random numbers with a given distribution (PDF). IEEE Transactions on Software Engineering. September 1991, 17 (9): 972–975 [2019-12-02]. Bibcode:10.1.1.398.3339 请检查|bibcode=值 (帮助). doi:10.1109/32.92917. (原始内容存档 (PDF)于2013-10-29). 
  4. ^ Darts, Dice, and Coins: Sampling from a Discrete Distribution. KeithSchwarz.com. 29 December 2011 [2011-12-27]. (原始内容存档于2012-01-04). 
  5. ^ Marsaglia, George; Tsang, Wai Wan; Wang, Jingbo, Fast Generation of Discrete Random Variables, Journal of Statistical Software, 2004-07-12, 11 (3): 1–11, doi:10.18637/jss.v011.i03