Probability and computing: randomized algorithms and probabilistic analysis

Description

"This textbook is designed to accompany a one- or two-semester course for advanced undergraduates or beginning graduate students in computer science and applied mathematics. It gives an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It assumes only an elementary background in discrete mathematics and gives a rigorous yet accessible treatment of the material, with numerous examples and applications."--BOOK JACKET.  Read more... 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