解決的問題：假設你有一條超長資料流或不知道總長度的資料(例如日誌、Sensor stream)，想要等機率抽到1筆或k筆當作隨機樣本，但你不能把全部資料存起來。
抽一筆的流程
- 先把第一筆當作樣本sample
- 讀到第i筆時(i從2開始)，以1/i的機率用它替換掉sample
- 最後留下來的那一筆，會是所有資料中等機率的隨機一筆
1/i機率的程式寫法可以random(0, i-1)等於0得之
證明為等機率，第j筆最後留下來的機率計算方式為，
- 第j筆換掉sample的機率是1/j，換不掉的機率是1-(1/j)
- 後續筆數都換不掉被選中為sample的機率為 (1-(1/(j+1)))(1-(1/(j+2)))(1-(1/(j+3)))...(1-(1/n)))，連乘後消去((j)/(j+1))((j+1)/(j+2))((j+2)/(j+3))...((n-1)/n)=j/n
- 合併算式後(1/j)(j/n)=1/n，所以每一筆為樣本sample的機率為1/n，得證等機率
抽k筆的流程
- 先放k筆進池子
- 第i筆(i > k)以機率k/i決定要不要進池子
- 若要進池子，就隨機踢掉池子中的一筆(每個位置機率1/k)
- 依照以上方式，任一筆出現在蓄水池的機率都是k/n
k/i機率的程式寫法可以random(0, i-1)落於[0, k-1]得之
證明機率為k/n，可分兩種情況證明
t > k 後來才來的元素
- 當在處理第t筆時，其被選進池內的機率是k/t
- 被選進池內後一路不被踢掉，直到處理完第n筆的機率計算為
每一筆後續元素i=t+1...n，第i筆發生替換事件的機率為k/i，而在替換事件發生的前提下，池內元素被踢掉的機率為1/k，所以處理第i筆時t被替換掉的機率為(k/i)(1/k)等於1/i，因此處理第i筆時t不被替換掉的機率為1-(1/i)等於(i-1)/i，直到處理完第n筆都替換不掉t的機率為(t/(t+1))((t+1)/(t+2))...((n-1)/n)，連乘消去後等於t/n；合併考量下，在t < k時t被選進池內且不被替換掉的機率得證為(k/t)(t/n)等於k/n
t <= k 一開始就在池內的元素
因為一開始已在池內，因此需計算k+1...n過程t都不被替換掉的機率；假設i=k+1...n，第i筆發生替換事件的機率為k/i，而替換掉池內t的機率為1/k，可得(k/i)(1/k)等於1/i為t被替換掉的機率，進而知道t不被替換掉的機率為1-(1/i)等於(i-1)/i；直到處理完第n筆都替換不掉t的機率因此為(k/(k+1))((k+1)/(k+2))...((n-1)/n)，連乘消去後得k/n得證
