別名方法

在計算機科學的計算中，別名方法（英語：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₂ = ¹⁄₂，然後一個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++實現