Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Probability and Computing: Randomized Algorithms and Probabilistic Analysis

by Michael Mitzenmacher, Eli Upfal
     
 

View All Available Formats & Editions

ISBN-10: 0521835402

ISBN-13: 9780521835404

Pub. Date: 12/15/2004

Publisher: Cambridge University Press

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,

Overview

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.

Product Details

ISBN-13:
9780521835404
Publisher:
Cambridge University Press
Publication date:
12/15/2004
Edition description:
New Edition
Pages:
352
Sales rank:
897,735
Product dimensions:
7.01(w) x 10.00(h) x 0.87(d)

Table of Contents

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.

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >