Probability and Computing Randomized Algorithms and Probabilistic AnalysisPDF电子书下载

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