Preface to the Second Edition Preface to the First Edition
1 Events and probability 2 Discrete random variables and expectations 3 Moments and deviations 4 Chernoff and Hoeffding bounds 5 Balls, bins, and random graphs 6 The probabilistic method 7 Markov chains and random walks 8 Continuous distributions and the Polsson process 9 The normal distribution 10 Entropy, randomness, and information 11 The Monte Carlo method 12 Coupling of Markov chains 13 Martingales 14 Sample complexity, VC dimension, and Rademacher complexity 15 Pairwise independence and universal hash functions 16 Power laws and related distributions 17 Balanced allocations and cuckoo hashing
Further Reading Index
Note: Asterisks indicate advanced material for this chapter