Unit 4.5 · about 4 h
117 / 324Randomized correctness, expected cost and selection
Random pivots turn a quadratic worst case into linear expected time. The guarantee only means something if you can say what is expected, over what randomness, and with what tail.
- derive
- implement
You can now
- Distinguish Las Vegas from Monte Carlo algorithms and state what is random in each: running time versus answer.
- Derive linear expected cost for randomized selection with indicator variables or a good-pivot recurrence, naming the exact comparison event counted.
- Separate expected cost from high-probability guarantees, and write the seed and trial contract that makes an empirical check reproducible.
Covers
- Randomized correctness, expected cost and reproducible seeds
- Randomized selection and hashing behavior
- High-probability and concentration bounds
Study, in this order
3 steps
- Nuts and Bolts: randomized analysis methodAlgorithms lecture notes - randomized algorithms
2.2 Deterministic vs. Randomized Algorithms, 2.3 Back to Nuts and Bolts and 2.4 Finding All Matches; 2.6 Recursive Analysis (the good-pivot bound) and 2.7 Iterative Analysis (indicator variables); Exercise 5 on QuickSelect
Depth · Exercise 4, reservoir sampling, belongs to the next unit. Skip 2.8 Masochistic Analysis.
- Tail Inequalities: expected versus high-probabilityAlgorithms lecture notes - randomized algorithms
4.1 Markov's Inequality, 4.3 Chebyshev's Inequality, 4.5 Chernoff Bounds, and 4.7 to 4.8 Back to Treaps as the expected-versus-high-probability example
- Expectation, linearity, and deviation boundsMIT 6.042J - probability and randomized algorithms
Session 32: Chapter 18.4 Great Expectations and 18.5 Linearity of Expectation. Session 33: Chapter 19.1 Markov's Theorem, 19.2 Chebyshev's Theorem and 19.3 Properties of Variance.
Focus on
- Las Vegas: the answer is always right and the running time is random, as with random-pivot quickselect and rejection sampling. Monte Carlo: the running time is fixed and the answer may be wrong with bounded probability, as with Miller-Rabin. Fisher-Yates and reservoir sampling fit neither: they run in fixed time and their job is to produce a distribution.
- Linearity of expectation needs no independence, so indicator variables over pivot comparisons sum directly to the expected count.
- This unit owns the expected-cost derivation for random pivots. Deterministic median of medians lives in the previous unit and partition code lives in the partition unit.
- Expected cost is a mean; high-probability bounds tail risk through Markov, Chebyshev, or Chernoff. Treap depth is the worked example of the stronger claim.
Reproduce closed-book
rand10 from rand7 with a random.Random(0).randint(1, 7) stub over 20,000 calls: mean rand7 calls 2.459 against theory \(2 \times 49/40 = 2.45\). Then sum the pair indicators \(2/(\max(j, k) - \min(i, k) + 1)\) for the median of 1000 elements (\(k = 500\)): 3336.3 expected comparisons. Run random-pivot quickselect (\(n - 1\) comparisons per partition) on shuffled range(1000) for 2000 seeded trials: the mean lands within about 50 of 3336, while single runs spread with a standard deviation near 980. Record sizes, seed, trials and theory with each run.Traps
- Reading expected \(O(n)\) as fast on every run. The tail exists, so report trial counts and seeds, and never promise a single-run bound from an expectation.
- Unseeded RNG inside tests. The suite passes until it does not; seed
random.Randomexplicitly and record the seed with the expected output. - Modulo bias in hand-rolled reduction: mapping two
rand7calls mod 10 favors some digits because 49 outcomes do not split evenly, so rejection keeps 1 to 40 and redraws 41 to 49.
Practice
LeetCode 470: Implement Rand10() Using Rand7()
The examples call rand10 1, 2 and 3 times. Test with a seeded rand7 stub and count mean rand7 calls over 20,000 calls, expecting about 2.45.
After submitting, read the DSA Handbook randomized-algorithms rejection section, which works the 2.45 figure from \(2 \times 49/40\).
Erickson lecture note 2, Exercise 5: QuickSelect analysis
Parts (a) to (d): expected-time recurrence, comparison probability, subarray probability, and linear expected time for any \(n\) and \(k\).
Paper analysis, not judged code. Check part (b) against your pair-indicator sum from the reproduce step; the partition implementation belongs to the partition unit.
Self-test
-
Is quickselect Las Vegas or Monte Carlo, and what is random about it?
Las Vegas. It always returns the correct \(k\)th element; only the number of comparisons varies with the random pivot choices. -
Why does linearity of expectation apply to quickselect comparison indicators?
Expectation of a sum equals the sum of expectations with no independence requirement, so dependent comparison events still sum directly. -
What is the difference between expected treap depth and depth with high probability?
Expected depth is a mean over random priorities. The high-probability bound says all but a tiny fraction of runs stay within \(O(\log n)\), which needs a tail inequality rather than linearity alone. -
What must an empirical check of a randomized claim record?
Input sizes, seed, trial count, theory value, and tolerance. For example: 20000 trials at seed 0 give 2.459rand7calls perrand10against theory 2.45.
Completion criterion
Stop when
LC 470 is accepted with a seeded stub test, and you can derive the 2.45 figure and the linear quickselect bound without notes.
Mark passed, then open 4.6 Only mark this when you can do it without notes.Leads to
- 4.6 Reservoir sampling, unbiased shuffling and empirical checks Verify a randomized guarantee empirically with fixed seeds and tolerances.
- 2.2 Partitioning, quicksort, quickselect and top-k The partition invariant this analysis assumes.
Comes after
- 2.2 Partitioning, quicksort, quickselect and top-kExpected-cost analysis of random pivots lives there.
- 4.2 Divide and conquer, recurrences and partition-based selectionExpected-cost analysis of random pivots.
Resources for this unit
- 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
- 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.
- 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.