Probabilistic Analysis and Randomized Algorithms

Some algorithms have a running time that genuinely depends on chance — either because the input itself is drawn from some distribution (the order in which trades arrive), or because the algorithm itself flips coins (randomizing quicksort's pivot choice, or a Monte Carlo estimator). Neither case is well described by "worst case" or "best case" alone, and both are handled by the same technique: write the quantity you want to bound as a sum of simple $0/1$ indicator random variables, then take the expectation of the sum using linearity of expectation — a property that needs no independence assumption whatsoever. This note develops that technique on the hiring problem, a small combinatorial example CLRS uses precisely because its answer ($O(\ln n)$ expected interviews) is both surprising and a two-line proof once the indicator-variable machinery is in place, then explains why randomized algorithms — algorithms that make random choices as part of their own logic, independent of the input's distribution — give you a probabilistic guarantee that holds regardless of what the adversary hands you.

Learning objectives. By the end of this note you should be able to: