[本文鏈接]
http://www.cnblogs.com/hellogiser/p/reservoir-sampling.html
問題起源於編程珠玑Column 12中的題目10，其描述如下：
How could you select one of n objects at random, where you see the objects sequentially but you do not know the value of n beforehand? For concreteness, how would you read a text file, and select and print one random line, when you don’t know the number of lines in advance?
（1）在不知道文件總行數n的情況下，如何從文件中隨機的抽取一行？
解：先選擇第一個行，並使用1/2的概率選擇第二個行，使用1/3的概率選擇第三行，使用1/i的概率選擇第i行，以此類推。在過程結束時，每個對像被選中的概率都是1/n。
用P(i)表示處於第i行時第i行被選中的概率。
P(1)=1
P(2)=1/2
P(3)=1/3
則選擇第3行的時候，對於第1行來講選中的概率=第一行被選中概率*第二行沒被選中*第3行沒被選中概率。
p(1)all=P(1)*(1-P(2))(1-P(3))=1/3
p(2)all=P(2)*(1-P(3))=1/3
p(3)all=P(3)=1/3
證明：
1最終被選中的概率：1被選中的概率*2沒有被選中的概率*3沒有被選中的概率*…*n沒有被選中的概率
p(1)all=1*(1-1/2)(1-1/3)*…*(1-1/n)=1/n
m最終被選中的概率：m被選中的概率*m+1沒有被選中的概率*m+2沒有被選中的概率*…*n沒有被選中的概率(1<=m<n)
p(m)all=1/m*[1-1/(m+1)][1-1/(m+2)]*…*[1-1/n]=1/n
（2）對其進行擴展，即如何從未知或者很大樣本空間隨機地取k個數？
給你一個長度為N的鏈表。N很大，但你不知道N有多大。你的任務是從這N個元素中隨機取出k個元素。你只能遍歷這個鏈表一次。你的算法必須保證取出的元素恰好有k個，且它們是完全隨機的（出現概率均等）。
解：先選中前k個， 從第k+1個元素到最後一個元素為止， 以k/i (i=k+1, k+2,...,N) 的概率選中第i個元素，並且隨機替換掉一個原先選中的元素， 這樣遍歷一次得到k個元素， 可以保證完全隨機選取。
證明：
n最終被選中的概率： n被選中的概率*[(n+1)沒有被選中的概率+(n+1)被選中概率*n沒被替換的概率]
p(n)all=k/n*[(1-k/(n+1))+k/(n+1)*(1-1/k)]=k/(n+1)
【參考】
http://www.cnblogs.com/ttltry-air/archive/2012/08/10/2632215.html
[本文鏈接]
http://www.cnblogs.com/hellogiser/p/reservoir-sampling.html
