蓄水池抽樣是一個隨機算法系列，用于從未知大小為n的群體中選擇一個簡單的隨機樣本，不需要替換，只需一次通過這些項目。算法不知道群體的大小，而且通常大到所有n個項目都能裝進主內存。群體是隨著時間的推移而顯示給算法的，算法不能回看以前的項目。在任何時候，算法的當前狀態必須允許提取一個簡單的隨機樣本，而不需要對迄今為止看到的人口的一部分進行大小為k的替換。

假設我們看到一連串的項目，一次一個。我們想在內存中保留10個項目，并且我們想從序列中隨機選擇它們。如果我們知道項目的總數為n，并且可以任意訪問這些項目，那么解決方案很簡單：以相同的概率在1到n之間選擇10個不同的索引i，并保留第i個元素。問題是，我們并不總是事先知道確切的n。簡單。算法R一個簡單而流行但緩慢的算法，算法R，是由AlanWaterman創造的。初始化一個數組{displaystylei=k}時，算法R返回所有輸入。算法R返回所有輸入，從而為數學歸納法的證明提供了基礎。在這里，歸納假設是，一個特定的輸入被包含在存儲庫中的概率正好在(i+1){displaystyle(i+1)}第1個輸入被處理的概率為-第1個輸入被處理的概率是ki{displaystyle{frac{k}{i}}}，我們必須證明，在處理第i+1}{displaystyle(i+1)}個輸入之前，特定的輸入被包含在存儲庫中的概率為ki而我們必須證明，一個特定的輸入被包含在存儲庫中的概率是{displaystyle{frac{k}{i}}}times{left(1-{frac{1}{i+1}}}right)={frac{k}{i+1}}。.后面的結果來自于這樣的假設：整數是均勻地隨機生成的。

我們已經證明，一個新的輸入進入儲層的概率等于儲層中現有輸入被保留的概率。因此，我們根據數學歸納法的原理得出結論，算法R確實產生了一個隨機的輸入樣本。雖然概念上簡單易懂，但這個算法需要為輸入的每一項產生一個隨機數，包括被丟棄的項目。因此，該算法的漸進運行時間為O(n){displaystyleO(n)}。.如果輸入群體很大，生成這種數量的隨機性和線性運行時間會使算法變得不必要的緩慢。