Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Probability and computing: randomization and probabilistic techniques in algorithms and data analysis (2nd ed.)
Mitzenmacher M., Upfal E., Cambridge University Press, New York, NY, 2017. 484 pp. Type: Book (978-1-107154-88-9)
Date Reviewed: Mar 15 2018

It is one of the great paradoxes of modern science that useful computation can be done by making random choices. This insight would be impressive even if the computation in question were contrived, but in many cases probabilistic algorithms can solve important problems much faster than deterministic approaches, particularly the highly combinatoric problems that increasingly dominate decision-making.

The tradeoff is that probabilistic algorithms, unlike deterministic ones, are approximate, and people who use them want to know how approximate they are. This volume offers a systematic toolbox of mathematically rigorous techniques for analyzing such algorithms. To illustrate these techniques, it outlines a large number of applications of probabilistic computing, providing a catalog that will be of as much value as the analytic techniques that it outlines.

The first edition of this text appeared in 2005. This volume expands the original by more than 30 percent, adding six sections to existing chapters, along with three totally new chapters.

The titles of most chapters could form the outline of a general probability text: “Events and Probability”; “Discrete Random Variables and Expectation”; “Moments and Deviations”; “Ball and Bin Problems”; “Markov Chains and Random Walks” (including coupled Markov Chains); “Continuous Distributions and the Poisson Process”; “The Normal Distribution” (a new chapter); “Entropy”; and “Martingales.” But in addition to introducing their topics (succinctly, with little exposition), the chapters give examples of random algorithms and analyze them using the chapter subjects. For example, in the first chapter (on events and probabilities), five pages are devoted to the axioms of probability, while more than twice as many describe four applications (including one new to this edition). The chapter on moments and deviations adds a section on the relation of median to mean, and the chapter on the normal distribution is completely new. Other chapters discuss topics that are critical for assessing the accuracy of an algorithm, including Chernoff and Hoeffding bounds (adding the Hoeffding bound to the discussion in the first edition), the probabilistic method of proving the existence of objects (with a new section on the algorithmic Lovász local lemma), a new chapter on sample complexity, two chapters on hash functions (including new sections on cuckoo hashing), and a new chapter on power laws and related distributions. Each chapter has extensive exercises.

While the coverage is extensive, one important class of random algorithms is omitted. In these algorithms, stochastic processes iteratively explore a problem, sharing their results with one another in a common data structure that in turn guides the search of subsequent rounds of computation. New ideas in optimization [1] surveys a range of such approaches. One example is ant algorithms, in which a swarm of agents repeatedly explores a graph structure, recording its findings locally on the graph (a digital analog of ant pheromones) and in turn responding to the records left by previous agents. In practice, these “digital pheromones” converge to a solution that can surpass the solution found by any individual agent. A similar iterative approach is used in various forms of synthetic evolution, in which a population of potential solutions (“chromosomes”) is repeatedly improved based on successive rounds of computation. These techniques are currently dominated by art, and it would be very helpful if a third edition of this volume could suggest how its formal tools could be applied to this class of approach.

This text is already a classic, not only for classroom use at the upper undergraduate and graduate student level, but also as a desk reference for practicing computer scientists. The addition of topics of current interest (such as order statistics like the median, the normal distribution in view of its importance in machine learning, and the increasingly ubiquitous power laws) will ensure its continued popularity.

More reviews about this item: Goodreads

Reviewer:  H. Van Dyke Parunak Review #: CR145914 (1806-0280)
1) Corne, D.; Dorigo, M.; Glover, F. New ideas in optimization. McGraw-Hill, New York, NY, 1999.
Bookmark and Share
  Featured Reviewer  
 
Probabilistic Algorithms (Including Monte Carlo) (G.3 ... )
 
 
Probabilistic Computation (F.1.2 ... )
 
 
Content Analysis And Indexing (H.3.1 )
 
 
Modes Of Computation (F.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Probabilistic Algorithms (Including Monte Carlo)": Date

Type: Article
Jul 1 1987
A probabilistic lower bound for checking disjointness of sets
Manber U. (ed) Information Processing Letters 19(1): 51-53, 1984. Type: Article
Feb 1 1985
On iterative methods in Markov modelling
Schatte P. Journal of Information Processing and Cybernetics 23(1): 49-51, 1987. Type: Article
Oct 1 1987
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy