Probability and computing: an introduction to randomized algorithms and probabilistic analysis

Probability and Computing......Page 2
Contents......Page 5
Why Randomness?......Page 10
The Book......Page 11
Acknowledgments......Page 13
1.1. Application: Verifying Polynomial Identities......Page 14
1.2. Axioms of Probability......Page 16
1.3. Application: Verifying Matrix Multiplication......Page 21
1.4. Application: A Randomized Min-Cut Algorithm......Page 25
1.5. Exercises......Page 27
2.1. Random Variables and Expectation......Page 33
2.2. The Bernoulli and Binomial Random Variables......Page 38
2.3. Conditional Expectation......Page 39
2.4. The Geometric Distribution......Page 43
2.5. Application: The Expected Run-Time of Quicksort......Page 47
2.6. Exercises......Page 51
3.1. Markov\'s Inequality......Page 57
3.2. Variance and Moments of a Random Variable......Page 58
3.3. Chebyshev\'s Inequality......Page 61
3.4. Application: A Randomized Algorithm for Computing the Median......Page 65
3.5. Exercises......Page 70
4.1. Moment Generating Functions......Page 74
4.2. Deriving and Applying Chernoff Bounds......Page 76
4.3. Better Bounds for Some Special Cases......Page 82
4.4. Application: Set Balancing......Page 84
4.5. * Application: Packet Routing in Sparse Networks......Page 85
4.6. Exercises......Page 96
5.1. Example: The Birthday Paradox......Page 103
5.2. Balls into Bins......Page 105
5.3. The Poisson Distribution......Page 107
5.4. The Poisson Approximation......Page 112
5.5. Application: Hashing......Page 119
5.6. Random Graphs......Page 125
5.7. Exercises......Page 132
5.8. An Exploratory Assignment......Page 137
6.1. The Basic Counting Argument......Page 139
6.2. The Expectation Argument......Page 141
6.3. Derandomization Using Conditional Expectations......Page 144
6.4. Sample and Modify......Page 146
6.5. The Second Moment Method......Page 147
6.6. The Conditional Expectation Inequality......Page 149
6.7. The Lovasz Local Lemma......Page 151
6.8. * Explicit Constructions Using the Local Lemma......Page 155
6.9. Lovasz Local Lemma: The General Case......Page 159
6.10. Exercises......Page 161
7.1. Markov Chains: Definitions and Representations......Page 166
7.2. Classification of States......Page 176
7.3. Stationary Distributions......Page 180
7.4. Random Walks on Undirected Graphs......Page 187
7.5. Parrondo\'s Paradox......Page 190
7.6. Exercises......Page 195
8.1. Continuous Random Variables......Page 201
8.2. The Uniform Distribution......Page 206
8.3. The Exponential Distribution......Page 209
8.4. The Poisson Process......Page 214
8.5. Continuous Time Markov Processes......Page 223
8.6. Example: Markovian Queues......Page 225
8.7. Exercises......Page 232
9.1. The Entropy Function......Page 238
9.2. Entropy and Binomial Coefficients......Page 241
9.3. Entropy: A Measure of Randomness......Page 243
9.4. Compression......Page 247
9.5. * Coding: Shannon\'s Theorem......Page 250
9.6. Exercises......Page 258
10.1. The Monte Carlo Method......Page 265
10.2. Application: The DNF Counting Problenl......Page 268
10.3. From Approximate Sampling to Approximate Counting......Page 272
10.4. The Markov Chain Monte Carlo Method......Page 276
10.5. Exercises......Page 280
10.6. An Exploratory Assignment on Minimum Spanning Trees......Page 283
11.1. Variation Distance and Mixing Time......Page 284
11.2. Coupling......Page 287
11.3. Application: Variation Distance Is Nonincreasing......Page 291
11.4. Geometric Convergence......Page 294
11.5. Application: Approximately Sampling Proper Colorings......Page 295
11.6. Path Coupling......Page 299
11.7. Exercises......Page 302
12.1. Martingales......Page 308
12.2. Stopping Times......Page 310
12.3. Wald\'s Equation......Page 313
12.4. Tail Inequalities for Martingales......Page 316
12.5. Applications of the Azuma-Hoeffding Inequality......Page 318
12.6. Exercises......Page 322
13.1. Pairwise Independence......Page 327
13.2. Chebyshev\'s Inequality for Pairwise Independent Variables......Page 331
13.3. Families of Universal Hash Functions......Page 334
13.4. Application: Finding Heavy Hitters in Data Streams......Page 341
13.5. Exercises......Page 346
14.1. The Power of Two Choices......Page 349
14.2. Two Choices: The Lower Bound......Page 354
14.3. Applications of the Power of Two Choices......Page 357
14.4. Exercises......Page 358
Further Reading......Page 362
Index......Page 363