随機取樣-蓄水池問題

看了多篇講解蓄水池問題的文章，感覺下面轉載的這一篇是證明最為嚴謹的。

原文位址：http://www.cnblogs.com/growup/archive/2012/02/07/2341912.html

如何在事先不知道文本檔案行數n的情況下讀取該檔案，從中随機選擇并輸出一行？

（事先不知道n的大小，但是一次可以看到這n個對象）

即蓄水池抽樣（Reservoir Sampling）問題

證明如下：

    問題: 證明目前任意一行為取出行的機率為1/i，i為目前掃描到的行号，也即每一行取出的機率相等

   我們用數學歸納法來證明，

當i=1時，目前隻浏覽了第一行，是以第一行為取出行的機率為1/1=1，符合直接取出的條件

當i=k時，有前k行為取出行的機率為1/k，我們要證明的是，當i=k+1時，前k+1行每一行被取出的機率均相等，且為1/(k+1)。當掃描到第k+1行時，我們以1/(k+1)機率替換choice，易知，第k+1行為choice的機率即為1/(k+1)，對于第k行，其為choice的機率是 第k行為取出行的機率 * 第k+1行沒有被取出的機率即，

   對于第k行的證明同樣可應用到前k-1行，對于其中第m行其為choice的機率是 第m行為取出行的機率 * 第m+1行沒有被取出的機率 * … *第k+1行沒有被取出的機率，即

  由此證得當i=k+1時，所有行的取出機率為1/(k+1)。證畢。

可以對其進行擴充，即如何從未知或者很大樣本空間随機地取k個數？

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

證明我們仍然使用數學歸納法：

  問題，證明對于任意樣本号n,n>=k,每個樣本作為取出樣本的機率相等，即k/n。

  證明：

  當n=k時，由我們把前k個數放入蓄水池可知，每個樣本的取出機率均相等，即k/k=1。   設目前樣本号為n，其每個取出樣本機率均相等，即為k/n，我們要證明的是這種情況對于n+1也成立。

  由于我們以k/(n+1)決定是否把n+1放入蓄水池，那麼對于n+1其出現在蓄水池中的機率就是k/(n+1)，對于前n個元素中的任意元素m(k+1<=m<=n)，其出現在蓄水池中的機率為 m出現在蓄水池中的機率 * [(m+1被選中的機率*m沒被m+1替換的機率 + m+1沒被選中的機率)*(m+2被選中的機率*m沒被m+2替換的機率 + m+2沒被選中的機率)*…*(n+1被選中的機率*m沒被n+1替換的機率 + n+1沒被選中的機率)]，即

  可見，對于n+1每個樣本取出機率也相等，即為k/(n+1)。證畢。

其僞代碼如下：

Init : a reservoir with the size： k  

1.        for    i= k+1 to N  
2.            M=random(1, i);  
3.            if( M < k)  
4.                 SWAP the Mth value and ith value  
5.       end for  

個人總結：如果在知道N的大小情況下，我們可以從[1、N]中随機選擇一個數作為選擇對象。但是現在不知道N的大小，要使每一個元素被取的機率相等（随機）。