Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis

Citation

Mitzenmacher, M., & Upfal, E. (2017). Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd ed.). Cambridge University Press.

Chapter Summary

Each chapter is devoted to one probabilistic technique and clarifies it through the analysis of randomized algorithms or of algorithms on random inputs. Sections marked with an asterisk are advanced material, and every chapter ends with exercises. The preface divides the book into a core (Chapters 1 to 7) and a set of largely self-contained chapters (8 to 17).

Chapter 1: Events and Probability

Reviews elementary probability through applications: verifying polynomial identities, verifying matrix multiplication, a naive Bayesian classifier and a randomized min-cut algorithm. The axioms of probability are developed alongside these examples.

Chapter 2: Discrete Random Variables and Expectation

Covers random variables and expectation (including linearity of expectation and Jensen's inequality), Bernoulli and binomial variables, conditional expectation and the geometric distribution. The coupon collector's problem and the expected run-time of Quicksort are the main applications.

Chapter 3: Moments and Deviations

Introduces Markov's inequality, variance and moments, Chebyshev's inequality and the relation between median and mean. It ends with a randomized algorithm for computing the median.

Chapter 4: Chernoff and Hoeffding Bounds

Builds Chernoff bounds from moment generating functions, applies them to sums of Poisson trials, and adds sharper bounds for special cases, set balancing and the Hoeffding bound. An advanced section on permutation routing on the hypercube and butterfly networks closes the chapter. The preface notes that most of the later material needs this chapter.

Chapter 5: Balls, Bins, and Random Graphs

Starts from the birthday paradox and the balls-and-bins model, then develops the Poisson distribution and the Poisson approximation. Applications include bucket sort, chain hashing, Bloom filters and Hamiltonian cycles in random graphs. The chapter ends with an exploratory programming assignment.

Chapter 6: The Probabilistic Method

Proves existence through the basic counting argument, the expectation argument, sample-and-modify, the second moment method and the conditional expectation inequality. It then turns to derandomization using conditional expectations and to the Lovász local lemma, including the general case and the algorithmic version in advanced sections.

Chapter 7: Markov Chains and Random Walks

Defines Markov chains and uses them for randomized algorithms for 2-satisfiability and 3-satisfiability. It then classifies states, treats stationary distributions and random walks on undirected graphs (with an s–t connectivity algorithm), and ends with Parrondo's paradox.

Chapters 8–9: Continuous Distributions and the Poisson Process; The Normal Distribution

Chapter 8 moves to continuous random variables, the uniform and exponential distributions, the Poisson process, continuous-time Markov processes and Markovian queues. Chapter 9 treats the normal distribution, the central limit theorem and multivariate normals, with applications to generating normally distributed values, maximum likelihood estimates and the EM algorithm for a mixture of Gaussians.

Chapters 10–12: Entropy, Randomness, and Information; The Monte Carlo Method; Coupling of Markov Chains

Chapter 10 introduces the entropy function, compression and Shannon's coding theorem. Chapter 11 covers the Monte Carlo method, DNF counting, the step from approximate sampling to approximate counting, and Markov chain Monte Carlo with the Metropolis algorithm. Chapter 12 develops variation distance, mixing time and coupling, including path coupling and the sampling of proper colorings. The preface suggests teaching Chapters 11 and 12 together.

Chapter 13: Martingales

Defines martingales and stopping times, proves Wald's equation, and derives tail inequalities, notably the Azuma–Hoeffding inequality, with applications to pattern matching, balls and bins and chromatic number.

Chapter 14: Sample Complexity, VC Dimension, and Rademacher Complexity

New in the second edition. It sets up the learning setting and VC dimension, then the ε-net and ε-sample theorems, with PAC learning, agnostic learning and data mining as applications, and finishes with Rademacher complexity.

Chapters 15–17: Pairwise Independence and Universal Hash Functions; Power Laws and Related Distributions; Balanced Allocations and Cuckoo Hashing

Chapter 15 treats pairwise independence, derandomization, universal families of hash functions, perfect hashing and heavy hitters in data streams. Chapter 16 (new in this edition) covers power laws, Zipf's law, preferential attachment and related distributions such as the lognormal. Chapter 17 covers the power of two choices and cuckoo hashing, with deletions, failures and variants.

Key Concepts

Chapters 1–3: Elementary tools

• Linearity of expectation: the expectation of a sum is the sum of expectations, whether or not the variables are independent.
• Markov's and Chebyshev's inequalities: the first tail bounds, using the mean and then the variance.

Chapters 4–7: Core techniques

• Chernoff bound: an exponentially small tail bound for sums of independent trials, obtained via moment generating functions.
• Balls and bins: the model behind the birthday paradox, hashing and load questions.
• Probabilistic method: showing that an object exists by showing that a random one has the required property with positive probability.
• Stationary distribution: the long-run behavior of a Markov chain.

Chapters 8–14: Further topics

• Poisson process: random arrivals in continuous time, the basis for queueing examples.
• Entropy: a measure of randomness tied to compression and coding.
• Coupling and mixing time: tools for showing that a Markov chain approaches its stationary distribution quickly.
• Azuma–Hoeffding inequality: concentration for martingales.
• VC dimension: a measure of the capacity of a class of sets, behind sample-size bounds.

Chapters 15–17: Hashing and data structures

• Universal hash family: hash functions that need little randomness yet have provable collision guarantees.
• Power of two choices: choosing the less loaded of two random bins sharply reduces the maximum load.

Critical Analysis

Strengths

• Technique-centered organization. The preface states that the emphasis is on probabilistic techniques and paradigms rather than particular applications, with one method per chapter and examples drawn largely from networking.
• Rigorous throughout. With few exceptions, claims come with full proofs, a choice the preface defends by arguing that sound use of heuristic methods such as Monte Carlo requires a firm grasp of the underlying theory.
• Clear signposting. The first seven chapters are identified as core, advanced sections are starred, later chapters are described as largely self-contained, and the preface suggests alternative chapter orders.
• Updated for data-driven work. The second edition adds chapters on the normal distribution, power laws and sample complexity, and a section on cuckoo hashing, in response to massive data sets and machine learning.
• Exercises and projects. Each chapter has exercises, and Chapters 5 and 11 include exploratory programming assignments.

Limitations

• Mostly theoretical exercises. The preface says most exercises are theoretical, with only some programming, so readers wanting implementation practice must supply it.
• Heuristic methods are excluded by design. Because the book restricts itself to rigorously analyzable methods, practical Monte Carlo heuristics are covered only through their mathematical foundations.
• Few pointers to the original literature. The authors chose not to cite original papers, offering a short list of background books under Further Reading instead.
• Preface not fully updated. The preface to the first edition still says the book has fourteen chapters, although this edition has seventeen.

Where It Fits in the Course

Within the algorithms course list, this is the specialist text on randomization and probabilistic analysis. Introduction to Algorithms, Algorithm Design Manual, Algorithms Illuminated and Algorithms Unlocked teach general design and analysis; Mitzenmacher and Upfal concentrate on the probability behind randomized algorithms, so it follows a general algorithms course rather than replacing one.

Approximation Algorithms by Vazirani and The Design of Approximation Algorithms by Williamson and Shmoys cover a neighboring graduate topic. Readers who meet randomized methods there may find the tail bounds and the probabilistic method of Chapters 4 and 6 here a useful background.

How to Use This Book

The book is written for advanced undergraduates and beginning graduate students in computer science and applied mathematics. The preface assumes only basic familiarity with probability, as in a discrete mathematics course for computer scientists, and a willingness to read full proofs.

A one-semester plan: read Chapters 1 to 7 as the core, moving quickly through Chapters 1 to 3 if probability is familiar, and skipping starred sections on a first pass. From the later chapters choose by interest: Chapters 8 and 10 for continuous probability and entropy, Chapters 11 and 12 together for Monte Carlo methods and coupling, Chapter 13 for martingales, Chapter 15 for derandomization and hashing, Chapter 14 for learning theory. Chapter 4 is a prerequisite for most later material.

Work the exercises with pencil in hand, since the proofs are the point, and do the two exploratory assignments in Chapters 5 and 11 to see the bounds in practice. For a second pass on hashing, read Sections 5.5, 15.3 and Chapter 17 together.