Резервуарна вибірка обирає k елементів рівномірно випадково з потоку, довжина якого N вам наперед невідома, за один прохід і з пам'яттю O(k).

Алгоритм R

• Покладіть перші k елементів у резервуар.
• Для кожного наступного елемента i > k оберіть випадкове ціле j у діапазоні 1…i. Якщо j ≤ k, замініть слот j елементом i; інакше відкиньте його.

Отже, елемент i потрапляє у резервуар з імовірністю рівно k/i.

Чому це рівномірно

Елемент i доживає до кінця, якщо його обрано на кроці i (ймовірність k/i) і потім жодного разу не витіснено. Імовірність не бути витісненим на пізнішому кроці m дорівнює 1 − 1/m. Перемноження дає

(k/i) · ∏(m=i+1..N) (1 − 1/m) = (k/i)·(i/N) = k/N

тож кожен елемент потрапляє у вибірку з однаковою імовірністю k/N. Гістограма праворуч — це емпірична частота включення кожного елемента за багато прогонів; вона збігається до пласкої пунктирної лінії на рівні k/N.