Probability and Computing, 2nd Edition

Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis

Greatly expanded, this new edition requires only an elementary background in discrete mathematics and offers a comprehensive introduction to the role of randomization and probabilistic techniques in modern computer science. Newly added chapters and sections cover topics including normal distributions, sample complexity, VC dimension, Rademacher complexity, power laws and related distributions, cuckoo hashing, and the Lovasz Local Lemma. Material relevant to machine learning and big data analysis enables students to learn modern techniques and applications. Among the many new exercises and examples are programming-related exercises that provide students with excellent training in solving relevant problems. This book provides an indispensable teaching tool to accompany a one- or two-semester course for advanced undergraduate students in computer science and applied mathematics.

Table of Contents

Chapter 1 Events And Probability
Chapter 2 Discrete Random Variables And Expectation
Chapter 3 Moments And Deviations
Chapter 4 Chernoff And Hoeffding Bounds
Chapter 5 Balls, Bins, And Random Graphs
Chapter 6 The Probabilistic Method
Chapter 7 Markov Chains And Random Walks
Chapter 8 Continuous Distributions And The Poisson Process
Chapter 9 The Normal Distribution
Chapter 10 Entropy, Randomness, And Information
Chapter 11 The Monte Carlo Method
Chapter 12 Coupling Of Markov Chains
Chapter 13 Martingales
Chapter 14 Sample Complexity, Vc Dimension, And Rademacher Complexity
Chapter 15 Pairwise Independence And Universal Hash Functions
Chapter 16 Power Laws And Related Distributions
Chapter 17 Balanced Allocations And Cuckoo Hashing