Chapter 5: Probabilistic Analysis and Randomized Algorithms

The hiring problem serves as the central example: a deterministic algorithm that hires each candidate better than the current best has a worst-case cost of O(n), but by assuming a randomly ordered input and applying probabilistic analysis, the expected number of hires reduces dramatically — using indicator random variables X_i, where E[X_i] = 1/i, the expected total hires sums to the harmonic series, yielding approximately ln n and an expected cost of O(ln n). To guarantee this behavior even against adversarial inputs, the randomized variant simply permutes the input before processing, producing a uniform random permutation in Θ(n) time and decoupling performance from input order. The key mathematical engine behind these analyses is the indicator random variable — defined as 1 if an event occurs and 0 otherwise, with expectation equal to the event's probability — combined with linearity of expectation, which allows expected values to be summed even across dependent variables. These tools power analyses of several classical probability problems: the birthday paradox, where collisions become likely around k ≈ √(2n) people; the balls-and-bins coupon collector problem, where filling all bins takes approximately b ln b tosses; and coin flip streaks, where the longest run of heads in n flips is expected to be about log n. The chapter closes with the secretary problem, where skipping the first n/e candidates and then hiring the next one who surpasses all prior candidates achieves the best candidate with probability at least 1/e — illustrating how randomized strategies offer simpler design, adversarial robustness, and tractable analysis compared to deterministic worst-case or unknown average-case approaches.