Unit 4.6 · about 4 h
118 / 324Reservoir sampling, unbiased shuffling and empirical checks
Streams do not fit in memory and shuffles must be uniform, not merely random-looking. The proof is one induction; the check is a seeded experiment you can rerun.
- implement
- measure
You can now
- Implement reservoir sampling and prove each position is kept with the claimed probability by induction.
- Implement Fisher-Yates and show every permutation is equally likely by counting \(n!\) paths.
- Test a sampler empirically with fixed seeds, trial counts, and tolerances, using pytest and Hypothesis for property and uniformity checks.
Covers
- Reservoir sampling and bounded-memory streams
- Unbiased shuffling and distribution checks
- Empirical probability checks and tolerance choice
Study, in this order
4 steps
- Randomized algorithms: Fisher-Yates, reservoir, rejectionDSA Handbook - recursion, backtracking and greedy
Fisher-Yates shuffle in linear time; Reservoir sampling with the equal-probability induction; Pitfalls: naive swap, Sattolo cycles, modulo bias, 32-bit PRNG limits
- Discrete Probability: shufflesAlgorithms lecture notes - randomized algorithms
1.6 Random Permutations (DrawLots, FisherYates, SelectionShuffle and InsertionShuffle); Exercise 10(a), NaiveShuffle on \(n = 3\)
Depth · Exercise 11, QuickShuffle, is optional depth.
- Nuts and Bolts, Exercise 4: stream samplingAlgorithms lecture notes - randomized algorithms
Exercise 4(a) and 4(b): one and \(k\) uniform samples from a stream in \(O(1)\) and \(O(k)\) space without knowing its length
- Sampling estimationMIT 6.042J - probability and randomized algorithms
Session 34: Chapter 19.4 Estimation by Random Sampling and 19.5 Confidence versus Probability
Focus on
- Reservoir induction: with one slot, the old item survives with probability \((i - 1)/i\), so each of the first \(i\) items is kept with \(1/(i - 1) \times (i - 1)/i = 1/i\).
- Fisher-Yates has exactly \(n!\) equally likely paths. CPython
random.Random.shuffleon 3.13.14 loops backwards with_randbelow, checked withinspectagainst the installed source. - Naive swap-with-any-index has \(n^n\) paths over \(n!\) permutations and is biased; the rand-below-i variant (Sattolo) yields only single cycles; a 32-bit seed cannot reach all \(52!\) orders.
- Empirical contract: sizes, seed, trials, tolerance.
random.Random(0).shuffleon 4 items, 4800 times, gives counts from 172 to 220 against 200 expected and a chi-square statistic of 22.6, under the 0.001 critical value of 49.7 at 23 degrees of freedom. The naive swap-with-any-index shuffle scores 126.7.
Reproduce closed-book
i >= k draw j = rng.randrange(i + 1) and replace slot j when j < k). With \(k = 5\) over range(100) and random.Random(0) it returns [63, 1, 2, 50, 34]. Over seeds 0 to 3999 on range(50), item 0 is kept with fraction 0.0985 against theory 0.1. Write a pytest file with a Hypothesis permutation-preservation property for your Fisher-Yates and the seeded chi-square check above; expect 2 passed.Traps
- An off-by-one in the replacement range silently biases late items. The seeded fraction-kept check against \(1/i\) catches it; eyeballing a few samples does not.
- Shuffling with a random comparator, or by sorting on random keys from a small range. A random comparator is inconsistent, so the result depends on the sort algorithm; tied keys keep input order under a stable sort. Distinct random float keys are uniform but cost \(O(n \log n)\); Fisher-Yates is \(O(n)\).
- Unseeded empirical tests that flake. Seed every RNG, record trials and tolerance, and rerun the exact command before claiming uniformity.
Practice
LeetCode 382: Linked List Random Node
Calls Solution then getRandom repeatedly on [1, 2, 3]. Implement with reservoir sampling at \(k = 1\) in \(O(1)\) extra space.
After submitting, reread the DSA Handbook reservoir section and check your replacement probability against its induction.
LeetCode 384: Shuffle an Array
Calls Solution, shuffle, reset, shuffle on [1, 2, 3]. Implement Fisher-Yates and test uniformity over fixed seeds.
After submitting, compare with the DSA Handbook Fisher-Yates section and its naive-shuffle counterexample.
Self-test
-
Prove the reservoir induction step for one slot.
Assume each of the first \(i - 1\) items is kept with \(1/(i - 1)\). Item \(i\) is kept with \(1/i\), and each old item survives with \((i - 1)/i\), giving \(1/(i - 1) \times (i - 1)/i = 1/i\). -
Why is swapping each position with any of \(n\) indices biased for \(n = 3\)?
It has \(3^3 = 27\) paths over 6 permutations, and 27 is not divisible by 6, so some permutations must get more paths than others. -
What does the Sattolo variant generate?
Only single \(n\)-cycles: each position swaps with a strictly earlier index, so fixed points and short cycles never appear. -
Your shuffle gives a chi-square of 22.6 over 24 permutations from 4800 trials. What does that show?
The counts are consistent with uniform: 23 degrees of freedom expect a statistic near 23, and the 0.001 critical value is 49.7. It does not prove uniformity; it fails to detect bias at this sample size, while the naive shuffle's 126.7 is detected.
Completion criterion
Stop when
Both problems are accepted, and your seeded reservoir and chi-square checks reproduce the stated numbers.
Mark passed, then open 5.1 Only mark this when you can do it without notes.Leads to
- 5.8 Recurrence proofs and differential validation Carry property and differential testing into recurrence validation.
- stage 04 · Classical Machine Learning Resampling and bootstrap build on this sampling discipline.
Comes after
- 4.5 Randomized correctness, expected cost and selectionVerify a randomized guarantee empirically with fixed seeds and tolerances.
Resources for this unit
- DSA Handbook - recursion, backtracking and greedy Study Part 7, Part 10 and the relevant foundations on recursion and probability. Write the state definition or greedy claim before opening code.
- MIT 6.042J - probability and randomized algorithms Use the probability, expectation and concentration readings to derive sampling probabilities and distinguish expected from high-probability guarantees.
- Algorithms lecture notes - randomized algorithms Use note 1 Discrete Probability, note 2 Nuts and Bolts (randomized quicksort, with QuickSelect in its exercises), note 4 Tail Inequalities and note 5 Hashing to derive expected costs, separate expected from high-probability guarantees, and analyze hashing behavior.
Also in this section
- AlgoMaster DSA - decomposition and greedy slice Attempt N-Queens and Gas Station cold, then implement reservoir sampling and test its output distribution over fixed-seed trials. Add another judged problem only for a diagnosed weakness.
- Algorithms - recursion, backtracking and greedy Use the recursion, backtracking, divide-and-conquer and greedy chapters for recurrence derivations, proof templates and counterexamples.