隨機抽樣中的Alias算法及其改進

賈文寶，王仲奇，張本愛

（1.南京航空航天大學，江蘇 南京 210016；

2.中國原子能科學研究院，北京 102413；

3.北京應(yīng)用物理與計算數(shù)學研究所，北京 100088）

隨機抽樣中的Alias算法及其改進

賈文寶1，王仲奇2，張本愛3

（1.南京航空航天大學，江蘇 南京 210016；

2.中國原子能科學研究院，北京 102413；

3.北京應(yīng)用物理與計算數(shù)學研究所，北京 100088）

為減少隨機數(shù)的使用次數(shù)和降低抽樣時間，基于等概化思路（或古典概型思路），對著名的Alias抽樣方法進行了改進.以存儲空間的少量增加為代價，使改進后的抽樣方法A＿Ⅰ和A＿Ⅱ隨機數(shù)的平均使用次數(shù)為Alias方法的75%和62.5%，平均抽樣時間大約為Alias方法的80%和70%.

Alias方法；改進；隨機抽樣

隨機變量抽樣是蒙特卡羅方法的基礎(chǔ)，同時也在其他許多領(lǐng)域廣泛使用.由于計算機的特征與限制，通常連續(xù)型隨機變量也要化作離散型隨機變量來處理，因此離散型隨機變量的抽樣方法是概率統(tǒng)計學科中的一個重要問題.為了方便起見，除特殊指明外，我們提到的隨機變量均為離散型隨機變量.

同時為了論述方便，首先將任意離散型隨機變量不失一般性地轉(zhuǎn)換成為

式中P1，P2，…為相應(yīng)的概率.

直接抽樣方法也稱查找算法，完全基于離散隨機變量概率分布的定義而得到的.它的抽樣思路十分簡潔，被稱為“非常理想”的方法［1］.它是通過將隨機數(shù)與階梯性的隨機變量分布值逐項比較而確定相應(yīng)的隨機事件.為了得到所需要的隨機事件，直接抽樣方法所需進行的比較次數(shù)同樣也形成了另外一個隨機變量，而這個隨機變量的數(shù)學期望與原隨機變量的數(shù)學期望是一致的.這就形成2個問題：不確定的比較次數(shù)提高了抽樣算法實現(xiàn)的復(fù)雜程度，影響了計算機的編譯系統(tǒng)對程序的優(yōu)化程度，這在并行化處理中頗受關(guān)注；對于數(shù)學期望比較大的隨機變量來說，不斷的比較將增加抽樣所需時間.

A.J.Walker在1974年給出了一個很巧妙的算法——Alias算法［2－4］，大大改善了對隨機變量的抽樣方法.在Alias算法中，只需要使用2個隨機數(shù)，進行一次與隨機數(shù)的比較操作，即可得到隨機變量的樣本.

我們將討論Alias算法，并以此為基礎(chǔ)進行改進，減少對隨機數(shù)的使用，減少抽樣所需的時間.

1 直接抽樣方法

對于隨機變量（1）有直接抽樣方法

很明顯，對于任意的離散型分布，都可以利用（2）式實現(xiàn)其抽樣.因此，從這個角度上說，直接抽樣是一個簡單而理想的算法.

由于在計算機處理中，進行一次比較操作所需時間將超過進行四則運算操作所需時間，而且比較操作將影響計算機處理的流程，妨礙編譯系統(tǒng)對程序的優(yōu)化，也就是說，在計算機上“比較”操作是一個“不好”的操作，應(yīng)該盡量避免和減少.因此所需比較的次數(shù)是抽樣方法優(yōu)劣的一個標志，應(yīng)想辦法減少所需比較的次數(shù).

由（2）式可知，要確定對應(yīng)于隨機數(shù)ξ的樣本值XF，需要通過將ξ與F（xi）不斷的比較而得到.對于一個確定的離散型分布，抽樣所需要進行的比較次數(shù)的數(shù)學期望應(yīng)為

總的來說，抽樣所需比較次數(shù)首先取決于隨機變量的容量，即包含的隨機事件的數(shù)量.隨機事件越多所需比較的次數(shù)就越多；其次隨機事件的排列秩序的不同也將影響抽樣所需比較次數(shù)的不同，概率大的事件秩序越靠前，所需比較的次數(shù)越少，反之亦然.例如下面一個隨機變量的不同表述方法所需抽樣比較的次數(shù)就會不同：

計算將顯示，利用（2）式抽樣，基于X1表述的隨機變量所需的比較次數(shù)將大于基于X2的比較次數(shù).

這說明隨機變量表述方法對抽樣所需比較次數(shù)存在影響，但這個影響是可以很簡單去掉的.而隨機變量容量對比較次數(shù)的影響則是本質(zhì).如何減少抽樣所需比較的次數(shù)，是改進抽樣方法的目標.

2 Alias算法

隨機變量X：｛Pi＝1／M，i＝1，2，…，M｝，這是一個事件等概率的隨機變量.對它的抽樣是非常簡單的XF＝i，如果［M·ξ］＋1＝i.這里不需要任何比較操作.這是因為隨機變量所包含的隨機事件具有等概率的獨特性質(zhì).如果將隨機事件進行“等概化變形”就可能會減少比較次數(shù)的途徑.

對i＝1，2，…，m.基于這個表示，以1／m的等概率確定表中的一個單元（AI，BI，P（Ai）），再利用一個隨機數(shù)用直接抽樣確定AI或BI，進而確定XF.文獻［5-6］分別給出了相應(yīng)的證明.

可以將Alias算法的流程表述如下［7］.持續(xù)執(zhí)行上述過程直至所有的事件都完全歸入表中，再將所有的P（Ai）乘上相同的倍數(shù)m即可.

第二步：抽樣

由此可以看出無論多大容量的隨機變量，使用Alias算法抽樣都只需進行1次與隨機數(shù)的比較，這樣將大大的節(jié)省抽樣所需時間，這將從后面的計算中體現(xiàn)出來.但是在減少比較操作次數(shù)的同時，Alias算法比直接抽樣方法多使用了一個隨機數(shù).

3 對Alias算法的改進

Alias算法的思路是將隨機變量進行適當變形向等概率方向靠近.沿著這個思路，繼續(xù)嘗試對Alias算法進行再次變形，以考察其是否能夠進一步減少判斷比較的次數(shù)或減少隨機數(shù)的使用次數(shù).

基于表T構(gòu)造新的 Alias表：T′＝｛A′i，B′i，P（A′i），i＝1，2，…，2m｝，即將每一個單元（Ai，Bi，P（Ai））變?yōu)?個單元

這樣我們將隨機變量變形為等概率的2部分組成，各由等概率單元組成.其中一部分的單元由概率為1的單“子事件”構(gòu)成（原隨機事件可以包含多個“子事件”）；而另一部分的單元由2個不等概率的“子事件”組成.

使用Alias抽樣方法，當確定的單元為單“子事件”單元則必然事件發(fā)生，不必繼續(xù)判斷；當確定的單元為雙“子事件”單元，與Alias算法做相同的工作.我們稱上面Alias算法的變化為1次改進.

同理，以構(gòu)造對Alias算法的1改進（為方便起見，將Alias方法記做A方法，將對Alias方法的1改進記做A＿Ⅰ方法，將對Alias方法的2改進記做A＿Ⅱ方法）.這樣隨機變量就變形為由等概率的4部分組成，其中3部分的單元均為單“子事件”單元，只有1部分的單元為雙“子事件”單元.

4 計算分析

為了直觀的比較Alias算法以及其改進算法與直接抽樣方法，隨機地構(gòu)造隨機變量，計算上述各種方法在對已確定的隨機變量抽樣時產(chǎn)生的誤差和花費的計算機時間.

首先均勻隨機產(chǎn)生各個事件的概率，作為待抽樣隨機變量.對于這個隨機變量分別用直接抽樣方法（DI），Alias抽樣方法（Alias）以及關(guān)于Alias方法的1改進（A＿Ⅰ）與2改進方法（A＿Ⅱ）進行抽樣，考察它們所形成的抽樣誤差和所耗費的計算機時間.

計算結(jié)果顯示，這幾種方法所形成的抽樣誤差是相當?shù)?而在計算機時間上則隨著隨機變量容量的增大體現(xiàn)出明顯的區(qū)別.

圖1給出對于不同容量的隨機變量，各種抽樣方法所需抽樣時間.從圖1可以看出，當隨機變量容量比較小時，Alias系列方法并不比直接抽樣方法優(yōu)越；當容量比較大時，Alias系列抽樣方法體現(xiàn)出其優(yōu)勢所在.Alias系列抽樣方法的抽樣時間在隨機變量容量變化時保持穩(wěn)定，不隨容量的增大而增大，而直接抽樣的抽樣時間與隨機變量的容量是相關(guān)的.

前面提到，對于不同的隨機事件排列次序的相同容量的隨機變量，直接抽樣方法的比較次數(shù)并不相同，因此其抽樣時間也是不相同的.圖2給出了容量為40的不同隨機變量的抽樣時間的分布情況.圖2中所顯示的是不同抽樣方法對于所含隨機事件容量相同但排列次序不同的隨機變量的抽樣時間，出于方便的考慮直接抽樣所需的比較次數(shù)來放映隨機事件的不同排列.這個結(jié)果反映了Alias系列方法的抽樣時間既不隨隨機變量的容量變化而變化，也基本上不隨隨機事件排列次序的變化而變化.

圖1 不同抽樣方法的隨機變量的容量與抽樣時間的變化趨勢

Alias系列方法的這個特點是非常重要的.在研究容量巨大的隨機變量的抽樣和考慮抽樣的并行化問題時，充分利用Alias系列方法，將非常有利于問題的解決.

在Alias抽樣中需要使用2個隨機數(shù)，進行1次比較.在Alias的1次改進抽樣中，對于一半的情況只需使用1個隨機數(shù)，不需要進行比較；而對另一半情況需要使用2個隨機數(shù)進行1次比較.在Alias的2次改進抽樣中，對1和4情況需要使用2個隨機數(shù)，進行1次比較，而對其他3／4情況只需使用1個隨機數(shù)，不需要進行比較.但是在這2個改進方法中，確定屬于需要使用第2個隨機數(shù)情況需要增加1次比較.也就是說利用上述2種改進的Alias方法1次抽樣分別需要使用1.5，1.25個隨機數(shù)和1.5，1.25次比較（依概率的意義）.

從使用隨機數(shù)方面，改進方法的確具有優(yōu)勢.因為在許多情況下，隨機數(shù)也是一種短缺的資源.Alias系列方法抽樣時間比較見圖3.

但從需要進行比較的次數(shù)這個指標來看，似乎這里所謂改進的抽樣方法不是在前進而是在后退，盡管從圖3可以得到結(jié)論，但改進的方法在計算時間上具有很大的優(yōu)勢.

圖2 規(guī)模為40的不同隨機變量的抽樣時間分布

圖3 Alias系列方法抽樣時間比較

在Alias算法中需要進行1次實數(shù)之間的比較，而改進的Alias算法只需要進行0.5（A＿Ⅰ），0.25（A＿Ⅱ）次實數(shù)之間的比較.綜合其他因素，2種對于Alias的改進算法的平均耗費時間分別大約為Alias方法的80%和70%.

上述對Alias算法的改進是以增加存儲空間的耗費為代價的.對于容量為M的隨機變量，直接抽樣方法需要使用1個M長的整數(shù)數(shù)組和1個M長的實數(shù)數(shù)組；Alias方法需要使用2個M長的整數(shù)數(shù)組和1個M長的實數(shù)數(shù)組；A＿Ⅰ方法需要使用3個M長的整數(shù)數(shù)組和1個M長的實數(shù)數(shù)組；A＿Ⅱ方法需要使用5個M長的整數(shù)數(shù)組和1個M長的實數(shù)數(shù)組.

在對Alias算法的改進中，逐漸減少對隨機數(shù)的使用，減少與隨機數(shù)的比較次數(shù).在減少隨機數(shù)使用次數(shù)的同時，降低了平均抽樣時間.

5 討論

我們在這里仔細分析了著名的Alias方法，并在此基礎(chǔ)上對其做了改進，以適當?shù)拇鎯臻g為代價，進一步節(jié)省了抽樣所需隨機數(shù)和抽樣所需時間.

不僅如此，可以看出，沿著這里給出的思路，可以繼續(xù)減少對隨機數(shù)的使用，減少與隨機數(shù)的比較次數(shù)，以達到節(jié)省資源的目的，但是同時也要考慮到對存儲空間的消耗.

［1］ 裴鹿成，張孝澤.蒙特卡羅方法及其在粒子輸運問題中的應(yīng)用［M］.北京：科學出版社，1980：58.

［2］ 上官丹驊.任意分布抽樣程序的設(shè)計與實現(xiàn)［J］.計算機工程與應(yīng)用，2004，7：107-109.

［3］ WALKER A J.New fast method for generating discrete random numbers with arbitrary frequency distribution［J］.Electronic Letters，1974，10：127-128.

［4］ WALKER A J.An efficient method for generating discrete random number with general distribution［J］.ACM Trans Math.Software，1977，3：253-256.

［5］ KRONMAL R A，PETERSON A V.On the alias method for generating random variables from a discrete distribution［J］.Amer Statist，1979，4：214-218.

［6］ DIETER U.An alternative proof for the representation of discrete distributions by equiprobable mixtures［J］.J Appl Prob，1982，19 ：869-872.

［7］ FISHMAN G S.Monte Carlo concepts，algorithms，and applications［M］.New York：Springer，1995：165-169.

Alias algorithm and improved in the random sampling

JIA Wen-bao1，WANG Zhong－qi2，ZHANG Ben-ai3

（1.Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China；
2.China Institute of Atomic Energy，Beijing 102413，China；
3.Beijing Application Physics and Computational Mathematics Research Institute，Beijing 100088，China）

Based on the generalizability theory（or the classical probability model），the famous Alias sampling method has been improved for reduce the using times of random numbers and the sampling time.A small increase in the storage space for the cost，the average using time of the improved method is 75%and 62.5%to Alias method's，and the average sampling time of the improved method is about 80%and 70%to Alias method's.

Alias algorithm；improving；random sampling

O242.1

110·61

A

1000-1832（2012）01-0023-05

2010-11-05

江蘇省博士后基金資助項目（0602034B）.

賈文寶（1968—），男，博士，副教授，主要從事核信息處理及核技術(shù)應(yīng)用研究；通訊作者：王仲奇（1962—），男，研究員，主要從事計算物理研究.

石紹慶）