You are here

Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Michael Mitzenmacher and Eli Upfal
Cambridge University Press
Publication Date: 
Number of Pages: 
[Reviewed by
WIlliam Satzer
, on

The idea of randomness has become a vital part of computer science in two fundamental ways over the last twenty years.  Randomized algorithms and the probabilistic analysis of algorithms are now basic tools in the repertoire of computer scientists and applied mathematicians.  Although the literature in this area is extensive, no introductory textbook has been available up to now.

Probability and Computing: Randomized Algorithms and Probabilistic Analysis is a new textbook written for advanced undergraduates and beginning graduate students in computer science and applied mathematics.  It aims to offer an introductory approach with a rigorous application of these basic ideas to carefully selected problems in computer science.  Randomized algorithms are algorithms that use random choices during their execution.  In practice, they use a random number generator at one or more stages of the algorithm to determine what operations are executed.  Probabilistic analysis of algorithms classifies algorithms according to their computational complexity using a method that studies how the algorithms perform when their input is taken from a well-defined sample space.  This powerful technique can demonstrate why NP-hard problems can often be solved with high probability using polynomial-time algorithms.

The book is naturally divided into two parts. The first seven chapters of the book are core material, while the remaining seven chapters include a selection of more advanced topics.   The first three chapters review elementary probability theory and rely primarily on discrete probability distributions.   Here, as throughout the book, the authors choose examples well, provide complete explanations, and continually connect to the book’s overall theme.  The very first example shows how a polynomial identity can be verified at a predetermined level of certainty using random inputs.  Another early example computes the expected run-time of Quicksort.

There is a whole chapter on the method of Chernoff bounds, a powerful technique for estimating tail distributions with exponentially decreasing bounds.  I learned this technique several years ago when estimating end-to-end delays in a packet-switched network.  This is the first time I have seen a formal presentation at an introductory level.

Another early chapter takes up the balls-and-bins problem of placing m balls in n bins with each ball placed independently with a uniform random distribution.  The authors provide several applications, including a high-probability, polynomial-time algorithm for finding a Hamiltonian cycle in a random graph with sufficiently many edges (another NP-hard problem).   Further applications are to hashing (chain hashing, bit strings and Bloom filters) as well as bucket sort.

A fascinating chapter on “the probabilistic method” demonstrates a technique for establishing the existence of objects with certain properties:  the trick is to exhibit a sample space of objects in which there is a positive probability that a randomly selected object has the desired properties.   The existence proof can often be converted to a random algorithm to construct the desired object.   Then, by applying a derandomizing technique, one can sometimes create a deterministic algorithm for constructing the object.  The authors use the k-SAT satisfiability problem to illustrate the method.

The structure and pace of this book are a well matched to the intended audience.   The authors consistently maintain a good balance between theory and applications. They also provide a range of exercises ranging from fairly routine completion of arguments in the text to more extensive and challenging exploratory problems.  Good students will be challenged and yet average students will find the text very readable.  This is a very attractive textbook.

Bill Satzer ([email protected]) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.

Preface; 1. Events and probability; 2. Discrete random variables and expectation; 3. Moments and deviations; 4. Chernoff bounds; 5. Balls, bins and random graphs; 6. The probabilistic method; 7. Markov chains and random walks; 8. Continuous distributions and the Poisson process; 9. Entropy, randomness, and information; 10. The Monte Carlo method; 11. Coupling of Markov chains; 12. Martingales; 13. Pairwise independence and universal hash functions; 14. Balanced allocations; References.