Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Assuming only an elementary background in discrete mathematics, this textbook is an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It includes random sampling, expectations, Markov's and Chevyshev's inequalities, Chernoff bounds, balls and bins models, the probabilistic method, Markov chains, MCMC, martingales, entropy, and other topics. The book is designed to accompany a one- or two-semester course for graduate students in computer science and applied mathematics.

Michael Miztenmacher is a John L. Loeb Associate Professor in Computer Science at Harvard University. Having written nearly 100 articles on a variety of topics in computer science, his research focuses on randomized algorithms and networks. He has received an NSF CAREER Award and an Alfred P. Sloan Research Fellowship. In 2002, he shared the IEEE Information Theory Society Best Paper Award for his work on error-correcting codes.

Eli Upfal is Professor and Chair of Computer Science at Brown University. He has published more than 100 papers in refereed journals and professional conferences, and is the inventor of more than ten patents. His main research interests are randomized computation and probabilistic analysis of algorithms, with applications to optimization algorithms, communication networks, parallel and distributed computing and computational biology.