蓄水池抽樣（reservoir sampling）

想像物件在輸送帶上一個接一個從你面前流過，而你必須恰好保留其中一個、均勻隨機地選中——但你事先不知道總共有多少個，而且一次只能拿一個。你無法先數完再挑。蓄水池抽樣是解決這問題的優雅規則：保留一個當前的選擇，每當新物件到來時，以恰到好處的機率用它替換你的選擇，使得在任何時刻，你手上的物件都是目前所見全部物件的均勻隨機選擇。

精確地說，對於選一個物件：把第一個物件當作你的樣本；當第 t 個物件到來時（t = 2, 3, ...），以機率 1/t 用新物件替換你儲存的樣本，否則保留現有的。處理完 n 個物件後，它們每一個成為最終樣本的機率恰為 1/n。證明是乾淨的歸納：物件 t 在它到來時以機率 1/t 成為樣本，並在之後每一步 j 以機率 (1 - 1/j) = (j-1)/j 存活；把它的接受機率乘上它通過第 t+1,...,n 步的存活機率，便望遠鏡式地相消，(1/t) 乘以 (t/(t+1)) 乘以 ((t+1)/(t+2)) 乘以 ... 乘以 ((n-1)/n) = 1/n。所以全部 n 個物件等可能。若要保留大小為 k 的樣本而非 1 個，先保留前 k 個物件，接著對第 t 個物件（t > k）以機率 k/t 保留它，若保留則讓它逐出當前 k 個中均勻隨機的一個。

蓄水池抽樣之所以重要，是因為它只用一趟掃描、O(k) 記憶體就抽出一個均勻樣本，無需知道或儲存串流長度——非常適合龐大的日誌、網路封包、或大到無法放下的資料。它是經典的「線上」抽樣方法。誠實的提醒：它給出不放回的均勻樣本，並假設你能產生公正的隨機數；加權版本與放回抽樣需要不同的規則。又雖然期望行為是精確的，任何單次執行都只是一次隨機抽取，所以要估計量值你仍要合併許多樣本或使用集中界。