Randomized Algorithms and Probabilistic Analysis

In most of computing you want a machine that does the same thing every time. This book is about the opposite instinct: introducing randomness on purpose, so that an algorithm becomes faster, simpler, or possible at all — and then proving, with real probability theory, that it almost never goes wrong. The trade at the center of the subject is worth stating plainly. Quicksort has a quadratic worst case, and the input that triggers it is an already-sorted array, which is the single most common shape real data arrives in. Choose the pivot at random and there is no longer any such thing as a bad input, because the algorithm's behavior no longer depends on the input's arrangement at all. The uncertainty moved out of the input, where an adversary controls it, and into the coin flips, where nobody does. That trade recurs on every scale — from a pivot choice to the hash seed that stops a denial-of-service attack to the noise that lets a census publish statistics without exposing a household. This is a complete treatment, built to serve a graduate or advanced-undergraduate course and to keep working after the course ends. The first half develops the mathematics honestly: expectation and its linearity, variance and Chebyshev, Chernoff and Hoeffding bounds derived from the moment generating function rather than quoted, martingales and Azuma for when independence fails, the probabilistic method, and the Lovász Local Lemma with the algorithmic version that makes it constructive. Those tools are then spent on the canonical algorithms — randomized quicksort, Karger's minimum cut, treaps and skip lists, fingerprinting, primality testing — and on the structures that made the subject industrially unavoidable: universal hashing, the power of two choices, Bloom filters, HyperLogLog, Count-Min, consistent hashing. The middle develops Markov chains, random walks, mixing times, expanders, and Markov chain Monte Carlo, then dimension reduction, streaming, sublinear-time algorithms, and randomized numerical linear algebra. The later chapters are written for professionals as much as for students, and they are reference material rather than lecture material: randomness engineering and the real bugs bad generators cause, the randomized machinery inside machine learning, differential privacy and its actual deployments, randomized testing and fuzzing, the probabilistic analysis of networks, derandomization, and a closing field guide of selection tables, sample-size formulas, failure-budget arithmetic, and pitfalls indexed by symptom. Every chapter carries the same four reference blocks — the guarantee stated precisely with its failure probability and cost; an index of where the analysis breaks organized by symptom; a survey of where the technique actually runs in production systems; and exercises with solutions. Research-level material is marked so that nothing unmarked depends on it. Python is the working language, with notes wherever another language changes the answer.



Al-generated content disclosure: This work was created with the help and usage of artificial intelligence. All sources are cited in the bibliography section.