Probability and computing : randomized algorithms and probabilistic analysis

Mitzenmacher, Michael 1969- (author.). Upfal, Eli, 1954- (author.).

Summary: "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"--Publisher's description.

Record details

ISBN: 0521835402 (alk. paper)
ISBN: 9780521835404 (alk. paper)
Physical Description: xvi, 352 p. : ill. ; 26 cm.
print
Publisher: New York : Cambridge University Press, 2005

Content descriptions

Bibliography, etc. Note:

Includes bibliographical references (p. 349) and index.

Formatted Contents Note:

Events and probability -- Discrete random variables and expectation -- Moments and deviations -- Chernoff bounds -- Balls, bins and random graphs -- The probabilistic method -- Markov chains and random walks -- Continuous distributions and the Poisson process -- Entropy, randomness, and information -- The Monte Carlo method -- Coupling of Markov chains -- Martingales -- Pairwise independence and universal hash functions -- Balanced allocations.