概率相关题目
1，如何生成概率
主要參考大牛的博客：http://www.cnblogs.com/miloyip/archive/2010/04/21/1717109.html
問(wèn)題定義
游戲(和一些模擬程序)經(jīng)常需要使用隨機(jī)數(shù)，去應(yīng)付不同的游戲(或商業(yè))邏輯。本文分析一個(gè)常見(jiàn)問(wèn)題：有N類物件，設(shè)第i類物件的出現(xiàn)概率為P(X=i)，如何產(chǎn)生這樣的隨機(jī)變量X？
例如對(duì)概率的要求是
P(X=0)=0.12
P(X=1)=0.4
P(X=2)=0.4
P(X=3)=0.07
P(X=4)=0.01
輸入數(shù)組<0.12, 0.4, 0.4, 0.07, 0.01>?輸出符合以上概率的隨機(jī)數(shù)序列，如<1, 4, 2, 1, 2, 2, 1, 0, ...> 。
以下先談一些統(tǒng)計(jì)學(xué)背景知識(shí)，再給這問(wèn)題的可行解法。
概率分布
這問(wèn)題要產(chǎn)生一個(gè)隨機(jī)變量，接近指定的概率分布(probability distribution)。大部份程序語(yǔ)言都提供接近均勻分布(uniformly distributed)的偽隨機(jī)數(shù)產(chǎn)生器(pseudorandom number generator, PRNG)，例如JavaScript提供的Math.random()函數(shù)，可傳回?半開(kāi)區(qū)間的均勻分布偽隨機(jī)數(shù)。
密度分布函數(shù)
現(xiàn)在，不仿測(cè)試一下JavaScript的Math.random()函數(shù)，看看它是否均勻分布。一個(gè)變數(shù)的分布以密度分布函數(shù)(probability density function, PDF)定義，一般寫(xiě)作，隨機(jī)變量在區(qū)間上的概率為定積分:
為了把PDF視覺(jué)化，可以把X分為若干區(qū)間，統(tǒng)計(jì)各區(qū)間X出現(xiàn)的頻率，繪畫(huà)其直方圖(histogram)。筆者寫(xiě)了一個(gè)簡(jiǎn)單的JavaScript框架，用HTML5 Canvas繪畫(huà)直方圖。以下測(cè)試代碼，可繪畫(huà)Math.random()的PDF估值(estimate)。
function step() {
? ? var x = Math.random();
? ? var bin = Math.floor(x * frequency.length);//譬如，x=0.45,則bin為4，就是給第四個(gè)桶的計(jì)數(shù)加1
? ? frequency[bin]++;
? ? sampleCount++;
? ? plotPdf(frequency, sampleCount, 1/frequency.length, "Estimated pdf of Math.random (n=" + sampleCount + ")");
}
var frequency = new Array(10);
var sampleCount = 0;
for (var i = 0; i < frequency.length; i++)
? ? frequency[i] = 0;
? ??
start("canvas1", step);//不斷的循環(huán)執(zhí)行step函數(shù)
因?yàn)橛惺畟€(gè)桶，所以每個(gè)桶的概率大致相同
累積分布函數(shù)
密度分布函數(shù)，可以變換為累積分布函數(shù)(cumulative distribution function, CDF)，代表隨機(jī)變量X小于x的概率:
在X為連續(xù)(continuous)的情況下，CDF可用PDF定義:
在X為離散(discrete)的情況下，CDF可定義為:
以下的pdf2cdf()函數(shù)，能把離散的PDF數(shù)組，轉(zhuǎn)換為CDF數(shù)組。由于浮點(diǎn)小數(shù)相加會(huì)有誤差，最后的值可能少于1，有機(jī)會(huì)產(chǎn)生bug，函數(shù)里強(qiáng)制指定最后一個(gè)元素為1。
function pdf2cdf(pdf) {//積累函數(shù)的意義在于，0表示落在0號(hào)桶的計(jì)數(shù)，1表示落在0,1號(hào)桶的計(jì)數(shù)...所以落在9號(hào)桶的概率肯定為1? ? var cdf = pdf.slice();
? ? ?
? ? for (var i = 1; i < cdf.length - 1; i++)
? ? ? ? cdf[i] += cdf[i - 1];
?
? ? // Force set last cdf to 1, preventing floating-point summing error in the loop.
? ? cdf[cdf.length - 1] = 1;
? ? ?
? ? return cdf;
}
題解
這問(wèn)題其實(shí)正式來(lái)說(shuō)，可稱為模擬離散取樣(simulated discrete sampling)，跟據(jù)有限類別的指定概率，來(lái)模擬取樣。
要制造指定的概率分布隨機(jī)變量，關(guān)鍵就是如何把均勻分布變換。
逆變換取樣
在上節(jié)中，顯示了CDF的一些特性，例如CDF的范圍是，而且是一個(gè)單調(diào)遞增(monotonic increasing)函數(shù)。逆變換取樣(inverse transform sampling)利用了這些特性，去解決這個(gè)問(wèn)題。逆變換取樣方法其實(shí)很簡(jiǎn)單，給一個(gè)目標(biāo)CDF，只要計(jì)算其逆函數(shù)(inverse function)，就可以把均勻的隨機(jī)變數(shù)轉(zhuǎn)換為目標(biāo)CDF:
這方法能用在所有CDF(包括連續(xù)及離散的)。其數(shù)學(xué)證明可參考維基百科。
下圖顯示這個(gè)方法的直觀解讀，在Y軸范圍里均勻取樣()，之后向右和CDF取交點(diǎn)，求交點(diǎn)的X軸位置()，X則是符合CDF的概率分布。
以上只是講的pdf為連續(xù)函數(shù)的做法，因?yàn)閥的取值范圍是0-1，所以先通過(guò)[0,1]均勻分布，獲得y的一個(gè)取樣，然后代入Fx的反函數(shù)即可以求出x的取樣
這個(gè)方法用在離散的情況就更簡(jiǎn)單，只需搜尋目標(biāo)的CDF，找出超過(guò)均勻取樣的元素即可。代碼如下:
functiondiscreteSampling(cdf) {//一定要注意cdf是累計(jì)概率vary = Math.random();for(varx incdf)if(y < cdf[x])//returnx;return-1; // should never runs here, assuming last element in cdf is 1 }
題目的測(cè)試:
var targetPdf = [0.12, 0.4, 0.4, 0.07, 0.01];
var targetCdf = pdf2cdf(targetPdf);
function step() {
? ? var bin = discreteSampling(targetCdf);
? ? frequency[bin]++;
? ? sampleCount++;
? ? plotPdf(frequency, sampleCount, 0.4, "Estimated cdf of discreteSampling (n=" + sampleCount + ")");
}
var frequency = new Array(targetCdf.length);
var sampleCount = 0;
for (var i = 0; i < frequency.length; i++)
? ? frequency[i] = 0;
? ??
start("canvas3", step);
截圖是：
分析
在離散的情況下(本文題目要求)，其時(shí)間復(fù)雜度是O(N)，其中N為類別數(shù)目。
讀者可能會(huì)注意到，這里用了線性搜尋(linear search)，如果targetPdf數(shù)組是由大至小排列，平均而言會(huì)更快找到結(jié)果。另外，也可以用二分搜尋(binary search)，那么復(fù)雜度會(huì)降低為O(lg N)，這留給讀者作為練習(xí)。
事實(shí)上，這個(gè)問(wèn)題用二分搜尋是標(biāo)準(zhǔn)的方法。那么，還有沒(méi)有更快的方法呢？答案是肯定的，例如別名方法(alias method)、近似方法等，有興趣的讀者可參考[1]。當(dāng)然，在N很小的情況下，線性搜尋和二分搜尋也足夠。
總結(jié)
