茶年 · 中文维基百科

別名方法

Wikipedia · 2025-12-06 维基百科 👁 0 阅读

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

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

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

输出一个均匀的随机变量 。

记 及 。（此时 均匀分布于 {{Math|{1, 2, …, n}}}， 均匀分布于 。）

如果 ，则返回 **'。这是有偏硬币抛投实验。

否则，返回 **'。

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

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

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

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

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

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

任意从「溢满」组和「不满」组各选择一个元素 和 。（若其中一个存在，则另一个也必然存在。）

别名表中索引为 ' 的空间尚未被设置，将其设置为 '：。

更新概率表中索引为 **' 的空间： 。

元素 **' 现在应归为「恰好」组。

对于元素 '，根据更新后的 '，将其分在恰当的组中。

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

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

别名表的构造不唯一。

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

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

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

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

文献

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

实现

参考文献

#伪随机数生成器

评论 (0)

  • 还没有评论，来抢沙发吧。