http://www.cnblogs.com/yysblog/archive/2012/06/27/2566276.html

1、問題定義可以簡(jiǎn)化如下：在不知道文件總行數(shù)的情況下，如何從文件中隨機(jī)的抽取一行？

　 　首先想到的是我們做過類似的題目嗎?當(dāng)然，在知道文件行數(shù)的情況下，我們可以很容易的用C運(yùn)行庫(kù)的rand函數(shù)隨機(jī)的獲得一個(gè)行數(shù)，從而隨機(jī)的取出一 行，但是，當(dāng)前的情況是不知道行數(shù)，這樣如何求呢？我們需要一個(gè)概念來幫助我們做出猜想，來使得對(duì)每一行取出的概率相等，也即隨機(jī)。這個(gè)概念即蓄水池抽樣（Reservoir Sampling）。

　　有了這個(gè)概念，我們便有了這樣一個(gè)解決方案：定義取出的行號(hào)為choice，第一次直接以第一行作為取出行 choice ，而后第二次以二分之一概率決定是否用第二行替換 choice ，第三次以三分之一的概率決定是否以第三行替換 choice ……，以此類推，可用偽代碼描述如下：

i = 0

while more input lines

?????????? with probability 1.0/++i

?????????????????? choice = this input line

print choice

　　這種方法的巧妙之處在于成功的構(gòu)造出了一種方式使得最后可以證明對(duì)每一行的取出概率都為1/n（其中n為當(dāng)前掃描到的文件行數(shù)），換句話說對(duì)每一行取出的概率均相等，也即完成了隨機(jī)的選取。

　　證明如下：

　　回顧這個(gè)問題，我們可以對(duì)其進(jìn)行擴(kuò)展，即

2、如何從未知或者很大樣本空間隨機(jī)地取k個(gè)數(shù)？

　　類比下即可得到答案，即先把前k個(gè)數(shù)放入蓄水池，對(duì)第k+1，我們以k/(k+1)概率決定是否要把它換入蓄水池，換入時(shí)隨機(jī)的選取一個(gè)作為替換項(xiàng)，這樣一直做下去，對(duì)于任意的樣本空間n，對(duì)每個(gè)數(shù)的選取概率都為k/n。也就是說對(duì)每個(gè)數(shù)選取概率相等。

　　偽代碼：

Init : a reservoir with the size： k

for i= k+1 to N

??? M=random(1, i);

??? if( M < k)

???? SWAP the Mth value and ith value

end for?

　　證明如下：

　　

?

　　蓄水池抽樣問題是一類問題，在這里總結(jié)一下，并由衷的感嘆這種方法之巧妙，不過對(duì)于這種思想產(chǎn)生的源頭還是發(fā)覺不夠，如果能夠知道為什么以及怎么樣想到這個(gè)解決方法的，定會(huì)更加有意義。

3、等概率隨機(jī)排列數(shù)組（洗牌算法）

　　問題描述：假設(shè)有一個(gè)數(shù)組，包含n個(gè)元素?，F(xiàn)在要重新排列這些元素，要求每個(gè)元素被放到任何一個(gè)位置的概率都相等（即1/n），并且直接在數(shù)組上重排（in place），不要生成新的數(shù)組。用 O(n) 時(shí)間、O(1) 輔助空間。

　　先想想如果可以開辟另外一塊長(zhǎng)度為n的輔助空間時(shí)該怎么處理，顯然只要對(duì)n個(gè)元素做n次（不放回的）隨機(jī)抽取就可以了。先從n個(gè)元素中任選一個(gè)，放入新空間的第一個(gè)位置，然后再?gòu)氖Ｏ碌膎-1個(gè)元素中任選一個(gè)，放入第二個(gè)位置，依此類推。

　　按照同樣的方法，但這次不開辟新的存儲(chǔ)空間。第一次被選中的元素就要放入這個(gè)數(shù)組的第一個(gè)位置，但這個(gè)位置原來已經(jīng)有別的（也可能就是這個(gè)）元素了，這時(shí)候只要把原來的元素跟被選中的元素互換一下就可以了。很容易就避免了輔助空間。

用Python來寫一段簡(jiǎn)單的程序描述這個(gè)算法：

1 2 3 4 5 6 7

from?random?import?Random def?Shuffle(li): ? rand?=?Random() ??for?x?in?xrange(len(li)?-?1,?0,?-1): ?# 逆序遍歷li ? ? y?=?rand.randint(0,?x)?? ? ? ? ? ? ?# 從剩余數(shù)據(jù)中隨機(jī)選取一個(gè) ? ? li[x],?li[y]?=?li[y],?li[x]?? ? ? ??# 將隨機(jī)選取的元素與當(dāng)前位置元素互換

主要的代碼僅僅三行而已，淺顯易懂。

來計(jì)算一下概率。如果某個(gè)元素被放入第i（1≤i≤n）個(gè)位置，就必須是在前 i - 1 次選取中都沒有選到它，并且第 i 次選取是恰好選中它。其概率為：

pi=n?1n×n?2n?1×?×n?i+1n?i+2×1n?i+1=

可見任何元素出現(xiàn)在任何位置的概率都是相等的。

4、利用等概率Rand5產(chǎn)生等概率Rand3

int?Rand3()
{
? ??int?x;
? ??do
? ??{
? ? ? ? x?=?Rand5();
? ??}?while?(x?>=?3);
? ??return?x;
}

算法很簡(jiǎn)單，x是我們最終要輸出的數(shù)字，只要它不在[0, 3)范圍內(nèi)，就不斷地調(diào)用Rand5來更新它。直觀地看，算法輸出的數(shù)字只有0、1、2這三個(gè)，而且對(duì)任何一個(gè)都沒有偏袒，那么顯然每個(gè)數(shù)字的概率都是1/3，那讓我們來嚴(yán)格地計(jì)算一下。

以輸出0為例，看看概率是多少。x的第一個(gè)有效數(shù)值是通過Rand5得到的。Rand5返回0的概率是1/5，如果這事兒發(fā)生了，我們就得到了0， 否則只有當(dāng)Rand5返回3或4的時(shí)候，我們才有機(jī)會(huì)再次調(diào)用它來得到新的數(shù)據(jù)。第二次調(diào)用Rand5之后，又是有1/5的概率得到0，2/5的概率得到 3或4導(dǎo)致循環(huán)繼續(xù)執(zhí)行下去，如此反復(fù)。因此概率的計(jì)算公式為：

p=====15+25×(15+25×(15+25×(?)))15×∑∞i=0(25)i15×11?2515×5313

喏，計(jì)算表明，Rand3輸出0的概率確實(shí)是1/3，對(duì)于另外兩個(gè)數(shù)字也是一樣的。

5、給定一個(gè)函數(shù)rand5()，使函數(shù)rand7()可以隨機(jī)等概率的生成1-7的整數(shù)

題目：

給定一個(gè)函數(shù)rand5()，該函數(shù)可以隨機(jī)生成1-5的整數(shù)，且生成概率一樣。現(xiàn)要求使用該函數(shù)構(gòu)造函數(shù)rand7()，使函數(shù)rand7()可以隨機(jī)等概率的生成1-7的整數(shù)。

思路：

很 多人的第一反應(yīng)是利用rand5() + rand()%3來實(shí)現(xiàn)rand7()函數(shù)，這個(gè)方法確實(shí)可以產(chǎn)生1-7之間的隨機(jī)數(shù)，但是仔細(xì)想想可以發(fā)現(xiàn)數(shù)字生成的概率是不相等的。rand()%3 產(chǎn)生0的概率是1/5，而產(chǎn)生1和2的概率都是2/5，所以這個(gè)方法產(chǎn)生6和7的概率大于產(chǎn)生5的概率。

正確的方法是利用rand5()函數(shù)生成1-25之間的數(shù)字，然后將其中的1-21映射成1-7，丟棄22-25。例如生成(1，1)，(1，2)，(1，3)，則看成rand7()中的1，如果出現(xiàn)剩下的4種，則丟棄重新生成。

簡(jiǎn)單實(shí)現(xiàn)：

Java代碼?

public?class?Test?{????

????public?int?rand7()?{????

????????int?x?=?22;????

????????while(x?>?21)?{????

????????????x?=?rand5()?+?(rand5()?-?1)*5;????

????????}????

????????return?1?+?x%7;????

????}????

????

}????

???我的備注：

????這 種思想是基于，rand()產(chǎn)生[0,N-1]，把rand()視為N進(jìn)制的一位數(shù)產(chǎn)生器，那么可以使用rand()*N+rand()來產(chǎn)生2位的N進(jìn) 制數(shù)，以此類推，可以產(chǎn)生3位，4位，5位...的N進(jìn)制數(shù)。這種按構(gòu)造N進(jìn)制數(shù)的方式生成的隨機(jī)數(shù)，必定能保證隨機(jī)，而相反，借助其他方式來使用 rand()產(chǎn)生隨機(jī)數(shù)(如?rand5() + rand()%3?)都是不能保證概率平均的。

????此題中N為5，因此可以使用rand5()*5+rand5()來產(chǎn)生2位的5進(jìn)制數(shù)，范圍就是1到25。再去掉22-25，剩余的除3，以此作為rand7()的產(chǎn)生器.

給定一個(gè)函數(shù)rand()能產(chǎn)生0到n-1之間的等概率隨機(jī)數(shù)，問如何產(chǎn)生0到m-1之間等概率的隨機(jī)數(shù)？

int?random(int?m,int?n){

????int?k=rand();

????int?max=n-1;

????while(k<m){

????????k=k*n+rand();

????????max=max*n+n-1;

????}

????return?k/(max/n);

}

如何產(chǎn)生如下概率的隨機(jī)數(shù)？0出1次，1出現(xiàn)2次，2出現(xiàn)3次，n-1出現(xiàn)n次？

int?random(int?size){

????while(true){

????????int?m=rand(size);

????????int?n=rand(size);

????????if(m+n<size)

????????????return?m+n;

????}

}

標(biāo)簽:?Algorithm

總結(jié)

以上是生活随笔為你收集整理的概率随机问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。