賈文寶，王仲奇，張本愛(ài)

（1.南京航空航天大學(xué)，江蘇 南京 210016；

2.中國(guó)原子能科學(xué)研究院，北京 102413；

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

隨機(jī)抽樣中的Alias算法及其改進(jìn)

賈文寶1，王仲奇2，張本愛(ài)3

（1.南京航空航天大學(xué)，江蘇 南京 210016；

2.中國(guó)原子能科學(xué)研究院，北京 102413；

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

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

Alias方法；改進(jìn)；隨機(jī)抽樣

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

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

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

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

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

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

1 直接抽樣方法

對(duì)于隨機(jī)變量（1）有直接抽樣方法

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

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

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

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

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

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

2 Alias算法

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

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

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

第二步：抽樣

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

3 對(duì)Alias算法的改進(jìn)

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

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

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

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

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

4 計(jì)算分析

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

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

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

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

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

圖1 不同抽樣方法的隨機(jī)變量的容量與抽樣時(shí)間的變化趨勢(shì)

Alias系列方法的這個(gè)特點(diǎn)是非常重要的.在研究容量巨大的隨機(jī)變量的抽樣和考慮抽樣的并行化問(wèn)題時(shí)，充分利用Alias系列方法，將非常有利于問(wèn)題的解決.

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

從使用隨機(jī)數(shù)方面，改進(jìn)方法的確具有優(yōu)勢(shì).因?yàn)樵谠S多情況下，隨機(jī)數(shù)也是一種短缺的資源.Alias系列方法抽樣時(shí)間比較見(jiàn)圖3.

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

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

圖3 Alias系列方法抽樣時(shí)間比較

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

上述對(duì)Alias算法的改進(jìn)是以增加存儲(chǔ)空間的耗費(fèi)為代價(jià)的.對(duì)于容量為M的隨機(jī)變量，直接抽樣方法需要使用1個(gè)M長(zhǎng)的整數(shù)數(shù)組和1個(gè)M長(zhǎng)的實(shí)數(shù)數(shù)組；Alias方法需要使用2個(gè)M長(zhǎng)的整數(shù)數(shù)組和1個(gè)M長(zhǎng)的實(shí)數(shù)數(shù)組；A＿Ⅰ方法需要使用3個(gè)M長(zhǎng)的整數(shù)數(shù)組和1個(gè)M長(zhǎng)的實(shí)數(shù)數(shù)組；A＿Ⅱ方法需要使用5個(gè)M長(zhǎng)的整數(shù)數(shù)組和1個(gè)M長(zhǎng)的實(shí)數(shù)數(shù)組.

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

5 討論

我們?cè)谶@里仔細(xì)分析了著名的Alias方法，并在此基礎(chǔ)上對(duì)其做了改進(jìn)，以適當(dāng)?shù)拇鎯?chǔ)空間為代價(jià)，進(jìn)一步節(jié)省了抽樣所需隨機(jī)數(shù)和抽樣所需時(shí)間.

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

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

［2］ 上官丹驊.任意分布抽樣程序的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(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

江蘇省博士后基金資助項(xiàng)目（0602034B）.

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

石紹慶）