從統(tǒng)計(jì)學(xué)的角度看， 一個(gè)rand7就相當(dāng)于符合均勻分布的隨機(jī)變量X1，當(dāng)n個(gè)rand7做運(yùn)算的時(shí)候，相當(dāng)于X1...Xn是符合均勻分布的邊緣隨機(jī)變量，而F(X1, X2,...,Xn)是他們的
聯(lián)合分布，這個(gè)分布并非是均勻的，甚至很復(fù)雜，如果不用窮舉法，幾乎沒(méi)有簡(jiǎn)便的方法計(jì)算每個(gè)數(shù)字出現(xiàn)的概率。現(xiàn)在要將多隨機(jī)變量的F(X1,X2,...,Xn)映射到1到10的均勻分布，顯然是有一定難度的， 而在本題來(lái)說(shuō)，是不可能的，這是因?yàn)椋?/div>
1) 對(duì)rand7的一元運(yùn)算只能有7種結(jié)果，不可能產(chǎn)生10個(gè)隨機(jī)數(shù)
2) 現(xiàn)在有二元運(yùn)算(X)可以是加減乘除或者任何函數(shù)任何映射關(guān)系，rand7(X)rand7的可能運(yùn)算方式是7*7種，,n次二元(X)運(yùn)算后的可能是運(yùn)算方式是7^(n+1)種，現(xiàn)在要用7^(n+1)種運(yùn)算過(guò)程得到均勻的10種結(jié)果，這是不可能的，(因?yàn)?^(n+1)不能被10整除)，所以只能是近似均勻。
下面來(lái)看怎樣獲得近似的均勻，
ju136提醒我注意到，其中的一個(gè)比較好的方法是：
(rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7())%10+1
他獲得的均勻度非常好，1出現(xiàn)的最多，5出現(xiàn)的最少，但是概率上僅僅相差0.00002，人類(lèi)的感覺(jué)已經(jīng)分辨不出來(lái)了。但是這個(gè)方法需要調(diào)用10次rand7，效率上差一些。
有人希望用這樣的方法：調(diào)用兩次rand7從而生成一個(gè)7進(jìn)制的數(shù)，然后轉(zhuǎn)換成0-49，剛好是50個(gè)數(shù)的均勻分布，再取模10。這個(gè)方法貌似可行，可是很遺憾的是，這樣生成的7進(jìn)制0-66對(duì)應(yīng)到10進(jìn)制是0-48，而不是49，少了一個(gè)數(shù)。
下面這個(gè)方法也比較好，(rand7+(rand7+7) +(rand7+14)+...+(rand7+42))%10，這個(gè)表達(dá)式生成7個(gè)隨機(jī)數(shù)，分別均勻分布在1-7,8-14,...7個(gè)區(qū)間，相加之后再做模10運(yùn)算，映射到0-9這10個(gè)數(shù)字。這7^7種運(yùn)算，統(tǒng)計(jì)每個(gè)數(shù)字可以得到次數(shù)，其中5最高，0最低，但是他們幾率的差僅為0.00041，人的感覺(jué)幾乎分辨不出來(lái)了。這個(gè)方法需要調(diào)用7次rand7，效率比上面的代碼高一些，因此有：
代碼3
int rand10_7plus()
{
return (rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+147)%10+1;
}
這種直接方法，無(wú)論怎樣在理論上都做不到均勻分布，所以，我們要想一些辦法來(lái)提高。
3. 直接法——利用組合方法進(jìn)一步提高
考慮數(shù)組
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
{6, 5, 4, 3, 2, 1, 10, 9, 8, 7 }
用rand7_plus在第一行中選擇的時(shí)候6的機(jī)會(huì)最大，1的機(jī)會(huì)最小，但是在第二行選擇的時(shí)候1的機(jī)會(huì)最大，6的機(jī)會(huì)最小，這兩行有一定的互補(bǔ)性，所以如果輪流選擇這兩行，會(huì)得到更均勻的分布，根據(jù)上面的計(jì)數(shù)結(jié)果，可以得知，最小幾率與最大幾率的差僅為萬(wàn)分之一。推廣一下，如果在數(shù)組
int seed10[10][10] = {
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
{10, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{9, 10, 1, 2, 3, 4, 5, 6, 7, 8 },
{8, 9, 10, 1, 2, 3, 4, 5, 6, 7 },
{7, 8, 9, 10, 1, 2, 3, 4, 5, 6 },
{6, 7, 8, 9, 10, 1, 2, 3, 4, 5 },
{5, 6, 7, 8, 9, 10, 1, 2, 3, 4 },
{4, 5, 6, 7, 8, 9, 10, 1, 2, 3 },
{3, 4, 5, 6, 7, 8, 9, 10, 1, 2 },
{2, 3, 4, 5, 6, 7, 8, 9, 10, 1 },
};
之中，依次在每一行用rand10_7plus選擇，由于每個(gè)數(shù)字出現(xiàn)的幾率均等，并且在每行和每列上出現(xiàn)的幾率均等，在多次調(diào)用之后就可以得到均勻分布。
代碼4
unsigned int gi = 0;
int rand10_matrix()
{
//用rand10_7plus生成一個(gè)數(shù)，選擇列
int n = rand10_7plus() - 1;
//輪流選擇seed10的行
return seed10[gi++ % 10][n];
}
如果利用模運(yùn)算的循環(huán)性質(zhì)，就不需要seed10這個(gè)矩陣，可以驗(yàn)證下面的代碼與rand10_matrix是等效的：
代碼5
unsigned int gi = 0;
int rand10_mod()
{
return ((rand10_7plus() - 1) + gi++) % 10 + 1;
}
這個(gè)算法每次調(diào)用7次rand7，做一次模運(yùn)算，不需要額外的內(nèi)存以及循環(huán)，從統(tǒng)計(jì)意義上說(shuō)，已經(jīng)是個(gè)比較好的偽隨機(jī)數(shù)生成器。
4. 隨機(jī)數(shù)測(cè)試
最初我在些這個(gè)文章的時(shí)候，在測(cè)試方面出了問(wèn)題，所以在這里強(qiáng)調(diào)兩點(diǎn)：
1). 隨機(jī)度測(cè)試，需要每隔10次調(diào)用計(jì)數(shù)一次，以驗(yàn)證每個(gè)數(shù)字在各個(gè)位置上出現(xiàn)的次數(shù)是均等的。
代碼要與如下類(lèi)似：
for (k = 0; k < 100000; k++) {
n = 0;
for (j = 0; j < 10; j++)
n = rand10_7plus10();
result[n - 1]++;
}
注意result[n - 1]++是在j=0~10這個(gè)循環(huán)之外的。
2). 概率計(jì)算
在編寫(xiě)代碼之前，一定要先證明1-10的均勻分布。例如前面10個(gè)rand連加的算法，在人的感覺(jué)之中已經(jīng)分辨不出來(lái)概率的差別了，因此需要仔細(xì)統(tǒng)計(jì)一下10個(gè)數(shù)字，寫(xiě)一個(gè)簡(jiǎn)單的10層循環(huán)計(jì)數(shù)就可以了。很多朋友忽視了這點(diǎn)，并且，我們上面在第2小節(jié)證明了這是不可能做到均勻的。如果想不清楚或者很難證明你的方法，于是這個(gè)最簡(jiǎn)單的代碼就非常有用:
for (i1 = 1; i1 <= 7; i1++)
for (i2 = 1; i2 <= 7; i2++)
for (i10 = 1; i10 <= 7; i10++)
result[(i1 + i2 + + i10) % 10]++;
5. 直接法——分布變換與連續(xù)隨機(jī)變量的分布——更實(shí)際的應(yīng)用
除了這道題的一些技巧，題目本身在實(shí)戰(zhàn)中沒(méi)有任何應(yīng)用，比較實(shí)際的問(wèn)題是，假設(shè)一個(gè)班的學(xué)生成績(jī)符合正態(tài)分布，如何模擬生成考試成績(jī)。
我們先看如果rand7是1-7的連續(xù)均勻分布，如何獲得1-10的均勻分布。答案很簡(jiǎn)單，從幾何的角度上看，我們可以把[a,b]線段上的點(diǎn)按照一對(duì)一映射到另一個(gè)線段[c,d]上去，只需要做一個(gè)線性變換y=(x-a)/(b-a)*(d-c)+c. 那么，若x=rand()~U(a,b),則y=~U(c,d)，也就是如果rand()是a到b上的均勻分布，則y=(d-c)(x-a)/(b-a)+c是c到d上的均勻分布。對(duì)于本例rand10=(rand()-1)/6*9+1. 下面是證明，更一般的情況同理可證：
另外有一個(gè)重要的定理來(lái)表明變換之后的分布。這可以處理如Y=X^2, Y=e^X等多種變換。定理如下：
這個(gè)定理還可以更強(qiáng)一些，f(x)是分段還是也可以，甚至只是一個(gè)覆蓋(包括)就可以了。從符合一種分布的隨機(jī)數(shù)生成另外一種分布的隨機(jī)數(shù)是統(tǒng)計(jì)模擬的課題，其中有非常有趣的變換方法，例如，如果X是(0,1)上的均勻分布，則Y=-a*log(X)是指數(shù)分布。
現(xiàn)在來(lái)回答如何按照正態(tài)分布模擬生成一個(gè)班的學(xué)生成績(jī)。這個(gè)方法被稱(chēng)為Box-Muller算法，如果U1和U2服從 (0,1)區(qū)間的均勻分布，做變換R=sqrt(-2*logU1), alpha=2*pi*U2，則X=Rcos(alpha)和Y=Rsin(alpha)是一對(duì)獨(dú)立的 標(biāo)準(zhǔn)正態(tài)分布n(0,1)。證明從略。按照這個(gè)方法，C語(yǔ)言的rand()，可以模擬生成近似的(0,1)均勻分布，只要rand()/MAX_RAND就可以了，做Box-Muller變換到n(0,1)，就可以做出符合學(xué)生成績(jī)分布了，概率統(tǒng)計(jì)課的基礎(chǔ)內(nèi)容就有。
6. 其他方法
舍去法也是非常重要的一類(lèi)隨機(jī)，用來(lái)生成各種分布的隨機(jī)數(shù)，另外的方法：比如Metropolis算法，比較著名的還有Markov Chain Monte Carlo (MCMC)算法，這類(lèi)方法可以看成是一個(gè)黑盒子，要求在算法內(nèi)部通過(guò)幾次運(yùn)算很快收斂到一種概率分布，然后返回一個(gè)隨機(jī)數(shù)。
7. 參考文獻(xiàn)
[2]
Kunth第2卷Seminumerical Algorithms, Random Numbers.