1 Events and Probability 1
1.1 Application: Verifying Polynomial Identities 1
1.2 Axioms of Probability 3
1.3 Application: Verifying Matrix Multiplication 8
1.4 Application: A Randomized Min-Cut Algorithm 12
1.5 Exercises 14
2 Discrete Random Variables and Expectation 20
2.1 Random Variables and Expectation 20
2.1.1 Linearity of Expectations 22
2.1.2 Jensen's Inequality 23
2.2 The Bernoulli and Binomial Random Variables 25
2.3 Conditional Expectation 26
2.4 The Geometric Distribution 30
2.4.1 Example: Coupon Collector's Problem 32
2.5 Application: The Expected Run-Time of Quicksort 34
2.6 Exercises 38
3 Moments and Deviations 44
3.1 Markov's Inequality 44
3.2 Variance and Moments of a Random Variable 45
3.2.1 Example: Variance of a Binomial Random Variable 48
3.3 Chebyshev's Inequality 48
3.3.1 Example: Coupon Collector's Problem 50
3.4 Application: A Randomized Algorithm for Computing the Median 52
3.4.1 The Algorithm 53
3.4.2 Analysis of the Algorithm 54
3.5 Exercises 57
4 Chernoff Bounds 61
4.1 Moment Generating Functions 61
4.2 Deriving and Applying Chernoff Bounds 63
4.2.1 Chernoff Bounds for the Sum of Poisson Trials 63
4.2.2 Example: Coin Flips 67
4.2.3 Application: Estimating a Parameter 67
4.3 Better Bounds for Some Special Cases 69
4.4 Application: Set Balancing 71
4.5 Application: Packet Routing in Sparse Networks 72
4.5.1 Permutation Routing on the Hypercube 73
4.5.2 Permutation Routing on the Butterfly 78
4.6 Exercises 83
5 Balls, Bins, and Random Graphs 90
5.1 Example: The Birthday Paradox 90
5.2 Balls into Bins 92
5.2.1 The Balls-and-Bins Model 92
5.2.2 Application: Bucket Sort 93
5.3 The Poisson Distribution 94
5.3.1 Limit of the Binomial Distribution 98
5.4 The Poisson Approximation 99
5.4.1 Example: Coupon Collector's Problem, Revisited 104
5.5 Application: Hashing 106
5.5.1 Chain Hashing 106
5.5.2 Hashing: Bit Strings 108
5.5.3 Bloom Filters 109
5.5.4 Breaking Symmetry 112
5.6 Random Graphs 112
5.6.1 Random Graph Models 112
5.6.2 Application: Hamiltonian Cycles in Random Graphs 113
5.7 Exercises 118
5.8 An Exploratory Assignment 124
6 The Probabilistic Method 126
6.1 The Basic Counting Argument 126
6.2 The Expectation Argument 128
6.2.1 Application: Finding a Large Cut 129
6.2.2 Application: Maximum Satisfiability 130
6.3 Derandomization Using Conditional Expectations 131
6.4 Sample and Modify 133
6.4.1 Application: Independent Sets 133
6.4.2 Application: Graphs with Large Girth 134
6.5 The Second Moment Method 134
6.5.1 Application: Threshold Behavior in Random Graphs 135
6.6 The Conditional Expectation Inequality 136
6.7 The Lovasz Local Lemma 138
6.7.1 Application: Edge-Disjoint Paths 141
6.7.2 Application: Satisfiability 142
6.8 Explicit Constructions Using the Local Lemma 142
6.8.1 Application: A Satisfiability Algorithm 143
6.9 Lovasz Local Lemma: The General Case 146
6.10 Exercises 148
7 Markov Chains and Random Walks 153
7.1 Markov Chains: Definitions and Representations 153
7.1.1 Application: A Randomized Algorithm for 2-Satisfiability 156
7.1.2 Application: A Randomized Algorithm for 3-Satisfiability 159
7.2 Classification of States 163
7.2.1 Example: The Gambler's Ruin 166
7.3 Stationary Distributions 167
7.3.1 Example: A Simple Queue 173
7.4 Random Walks on Undirected Graphs 174
7.4.1 Application: An s-t Connectiviry Algorithm 176
7.5 Parrondo's Paradox 177
7.6 Exercises 182
8 Continuous Distributions and the Poisson Process 188
8.1 Continuous Random Variables 188
8.1.1 Probability Distributions in R 188
8.1.2 Joint Distributions and Conditional Probability 191
8.2 The Uniform Distribution 193
8.2.1 Additional Properties of the Uniform Distribution 194
8.3 The Exponential Distribution 196
8.3.1 Additional Properties of the Exponential Distribution 197
8.3.2 Example: Balls and Bins with Feedback 199
8.4 The Poisson Process 201
8.4.1 Interarrival Distribution 204
8.4.2 Combining and Splitting Poisson Processes 205
8.4.3 Conditional Arrival Time Distribution 207
8.5 Continuous Time Markov Processes 210
8.6 Example: Markovian Queues 212
8.6.1 M/M/1 Queue in Equilibrium 213
8.6.2 M/M/1/K Queue in Equilibrium 216
8.6.3 The Number of Customers in an M/M/∞ Queue 216
8.7 Exercises 219
9 Entropy, Randomness, and Information 225
9.1 The Entropy Function 225
9.2 Entropy and Binomial Coefficients 228
9.3 Entropy: A Measure of Randomness 230
9.4 Compression 234
9.5 Coding: Shannon's Theorem 237
9.6 Exercises 245
10 The Monte Carlo Method 252
10.1 The Monte Carlo Method 252
10.2 Application: The DNF Counting Problem 255
10.2.1 The Naive Approach 255
10.2.2 A Fully Polynomial Randomized Scheme for DNF Counting 257
10.3 From Approximate Sampling to Approximate Counting 259
10.4 The Markov Chain Monte Carlo Method 263
10.4.1 The Metropolis Algorithm 265
10.5 Exercises 267
10.6 An Exploratory Assignment on Minimum Spanning Trees 270
11 Coupling of Markov Chains 271
11.1 Variation Distance and Mixing Time 271
11.2 Coupling 274
11.2.1 Example: Shuffling Cards 275
11.2.2 Example: Random Walks on the Hypercube 276
11.2.3 Example: Independent Sets of Fixed Size 277
11.3 Application: Variation Distance Is Nonincreasing 278
11.4 Geometric Convergence 281
11.5 Application: Approximately Sampling Proper Colorings 282
11.6 Path Coupling 286
11.7 Exercises 289
12 Martingales 295
12.1 Martingales 295
12.2 Stopping Times 297
12.2.1 Example: A Ballot Theorem 299
12.3 Wald's Equation 300
12.4 Tail Inequalities for Martingales 303
12.5 Applications of the Azuma-Hoeffding Inequality 305
12.5.1 General Formalization 305
12.5.2 Application: Pattern Matching 307
12.5.3 Application: Balls and Bins 308
12.5.4 Application: Chromatic Number 308
12.6 Exercises 309
13 Pairwise Independence and Universal Hash Functions 314
13.1 Pairwise Independence 314
13.1.1 Example: A Construction of Pairwise Independent Bits 315
13.1.2 Application: Derandomizing an Algorithm for Large Cuts 316
13.1.3 Example: Constructing Pairwise Independent Values Moduloa Prime 317
13.2 Chebyshev's Inequality for Pairwise Independent Variables 318
13.2.1 Application: Sampling Using Fewer Random Bits 319
13.3 Families of Universal Hash Functions 321
13.3.1 Example: A 2-Universal Family of Hash Functions 323
13.3.2 Example: A Strongly 2-Universal Family of Hash Functions 324
13.3.3 Application: Perfect Hashing 326
13.4 Application: Finding Heavy Hitters in Data Streams 328
13.5 Exercises 333
14 Balanced Allocations 336
14.1 The Power of Two Choices 336
14.1.1 The Upper Bound 336
14.2 Two Choices: The Lower Bound 341
14.3 Applications of the Power of Two Choices 344
14.3.1 Hashing 344
14.3.2 Dynamic Resource Allocation 345
14.4 Exercises 345
Further Reading 349
Index 350