CLRS-Lean
CLRS Fourth Edition
Chapter 5. Probabilistic Analysis and Randomized Algorithms

Imports

import CLRSLean.FourthEdition.Chapter_05.Section_05_1_Hiring_Problem
import CLRSLean.FourthEdition.Chapter_05.Section_05_2_Indicator_Random_Variables
import CLRSLean.FourthEdition.Chapter_05.Section_05_3_Randomized_Algorithms
import CLRSLean.FourthEdition.Chapter_05.Section_05_4_Probabilistic_Analysis
import CLRSLean.FourthEdition.Chapter_05.Section_05_4_Probabilistic_Analysis.OnlineHiring

Chapter 5 — Probabilistic Analysis and Randomized Algorithms

Native fourth-edition chapter guide.

Current source

This guide sources fourth-edition §5.1–§5.4 from the native section modules under CLRSLean.FourthEdition.Chapter_05. Declarations retain the CLRS.Chapter05 namespace; the legacy import CLRSLean.Chapter_05 and its Section_05_* modules forward to these sources during the compatibility period.

The hiring problem studies the expected number of times a new best candidate is hired in a random interview order. Section 5.1 proves the finite rank-symmetry calculation that the step probability is 1/(n+1), sums the indicator expectations, proves the equivalent recurrence solution, derives the logarithmic asymptotic growth of the expected number of hires, and formalizes the executable HIRE-ASSISTANT pseudocode (CLRS.Chapter05.hireAssistant) with its one-step record-counting recurrence.

Section 5.2 formalizes the indicator random variable technique and linearity of expectation with the hat-check problem (expected fixed points of a uniform random permutation of Fin n equal 1).

Section 5.3 proves the central result of CLRS §5.3: the RANDOMIZE-IN-PLACE procedure (Fisher–Yates shuffle) yields a uniform random permutation of Fin n (Lemma 5.5), modelled by an explicit choice-vector sample space and a bijection onto Equiv.Perm (Fin n).

Section 5.4 applies indicators plus independence to two classic probabilistic analyses: the birthday paradox (expected number of same-birthday pairs is k(k-1)/(2n)) and balls and bins (expected number of balls in a fixed bin is k/n). It also proves the longest streak result that the expected longest run of heads in n fair coin flips is Θ(log n) — upper bound E[L] ≤ log₂ n + 2 and lower bound E[L] ≥ log₂ n / 8 for n ≥ 16. Its on-line hiring model provides an executable threshold strategy over finite permutations, the finite success probability CLRS.Chapter05.OnlineHiring.probHireBest, its harmonic closed form (k/n)(H_{n-1} - H_{k-1}), and the asymptotic 1/e success probability for the threshold ⌊n/e⌋.

Section 5.1: proved for the finite rank-symmetry model, including CLRS.Chapter05.expectedHires_isBigTheta_log.
Section 5.2: proved for the uniform-permutation model, including CLRS.Chapter05.expectedFixedPoints_eq_one.
Section 5.3: proved for the independent-swap-choice model, including CLRS.Chapter05.randomizeInPlace_uniform (Lemma 5.5).
Section 5.4: proved for the product-uniform birthday and balls-and-bins models (CLRS.Chapter05.expectedCollisions_eq, CLRS.Chapter05.expectedBallsInBin_eq), the longest-streak Θ(log n) bounds (CLRS.Chapter05.expectedLongestStreak_le, CLRS.Chapter05.expectedLongestStreak_lowerBound), and on-line hiring, whose success probability has the harmonic closed form (CLRS.Chapter05.OnlineHiring.probHireBest_eq) and the 1/e asymptotic (CLRS.Chapter05.OnlineHiring.probHireBest_asymptotic).

Coverage boundary

The represented finite-probability developments are reused under the unchanged chapter number.

See docs/clrs-fourth-edition-map.csv for the section-level mapping and docs/migrations/clrs4.md for compatibility and deprecation policy.