Probability and Computing Randomized Algorithms and Probabilistic AnalysisPDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 Events and Probability1

1.1 Application: Verifying Polynomial Identities1

1.2 Axioms of Probability3

1.3 Application: Verifying Matrix Multiplication8

1.4 Application: A Randomized Min-Cut Algorithm12

1.5 Exercises14

2 Discrete Random Variables and Expectation20

2.1 Random Variables and Expectation20

2.1.1 Linearity of Expectations22

2.1.2 Jensen's Inequality23

2.2 The Bernoulli and Binomial Random Variables25

2.3 Conditional Expectation26

2.4 The Geometric Distribution30

2.4.1 Example: Coupon Collector's Problem32

2.5 Application: The Expected Run-Time of Quicksort34

2.6 Exercises38

3 Moments and Deviations44

3.1 Markov's Inequality44

3.2 Variance and Moments of a Random Variable45

3.2.1 Example: Variance of a Binomial Random Variable48

3.3 Chebyshev's Inequality48

3.3.1 Example: Coupon Collector's Problem50

3.4 Application: A Randomized Algorithm for Computing the Median52

3.4.1 The Algorithm53

3.4.2 Analysis of the Algorithm54

3.5 Exercises57

4 Chernoff Bounds61

4.1 Moment Generating Functions61

4.2 Deriving and Applying Chernoff Bounds63

4.2.1 Chernoff Bounds for the Sum of Poisson Trials63

4.2.2 Example: Coin Flips67

4.2.3 Application: Estimating a Parameter67

4.3 Better Bounds for Some Special Cases69

4.4 Application: Set Balancing71

4.5 Application: Packet Routing in Sparse Networks72

4.5.1 Permutation Routing on the Hypercube73

4.5.2 Permutation Routing on the Butterfly78

4.6 Exercises83

5 Balls, Bins, and Random Graphs90

5.1 Example: The Birthday Paradox90

5.2 Balls into Bins92

5.2.1 The Balls-and-Bins Model92

5.2.2 Application: Bucket Sort93

5.3 The Poisson Distribution94

5.3.1 Limit of the Binomial Distribution98

5.4 The Poisson Approximation99

5.4.1 Example: Coupon Collector's Problem, Revisited104

5.5 Application: Hashing106

5.5.1 Chain Hashing106

5.5.2 Hashing: Bit Strings108

5.5.3 Bloom Filters109

5.5.4 Breaking Symmetry112

5.6 Random Graphs112

5.6.1 Random Graph Models112

5.6.2 Application: Hamiltonian Cycles in Random Graphs113

5.7 Exercises118

5.8 An Exploratory Assignment124

6 The Probabilistic Method126

6.1 The Basic Counting Argument126

6.2 The Expectation Argument128

6.2.1 Application: Finding a Large Cut129

6.2.2 Application: Maximum Satisfiability130

6.3 Derandomization Using Conditional Expectations131

6.4 Sample and Modify133

6.4.1 Application: Independent Sets133

6.4.2 Application: Graphs with Large Girth134

6.5 The Second Moment Method134

6.5.1 Application: Threshold Behavior in Random Graphs135

6.6 The Conditional Expectation Inequality136

6.7 The Lovasz Local Lemma138

6.7.1 Application: Edge-Disjoint Paths141

6.7.2 Application: Satisfiability142

6.8 Explicit Constructions Using the Local Lemma142

6.8.1 Application: A Satisfiability Algorithm143

6.9 Lovasz Local Lemma: The General Case146

6.10 Exercises148

7 Markov Chains and Random Walks153

7.1 Markov Chains: Definitions and Representations153

7.1.1 Application: A Randomized Algorithm for 2-Satisfiability156

7.1.2 Application: A Randomized Algorithm for 3-Satisfiability159

7.2 Classification of States163

7.2.1 Example: The Gambler's Ruin166

7.3 Stationary Distributions167

7.3.1 Example: A Simple Queue173

7.4 Random Walks on Undirected Graphs174

7.4.1 Application: An s-t Connectiviry Algorithm176

7.5 Parrondo's Paradox177

7.6 Exercises182

8 Continuous Distributions and the Poisson Process188

8.1 Continuous Random Variables188

8.1.1 Probability Distributions in R188

8.1.2 Joint Distributions and Conditional Probability191

8.2 The Uniform Distribution193

8.2.1 Additional Properties of the Uniform Distribution194

8.3 The Exponential Distribution196

8.3.1 Additional Properties of the Exponential Distribution197

8.3.2 Example: Balls and Bins with Feedback199

8.4 The Poisson Process201

8.4.1 Interarrival Distribution204

8.4.2 Combining and Splitting Poisson Processes205

8.4.3 Conditional Arrival Time Distribution207

8.5 Continuous Time Markov Processes210

8.6 Example: Markovian Queues212

8.6.1 M/M/1 Queue in Equilibrium213

8.6.2 M/M/1/K Queue in Equilibrium216

8.6.3 The Number of Customers in an M/M/∞ Queue216

8.7 Exercises219

9 Entropy, Randomness, and Information225

9.1 The Entropy Function225

9.2 Entropy and Binomial Coefficients228

9.3 Entropy: A Measure of Randomness230

9.4 Compression234

9.5 Coding: Shannon's Theorem237

9.6 Exercises245

10 The Monte Carlo Method252

10.1 The Monte Carlo Method252

10.2 Application: The DNF Counting Problem255

10.2.1 The Naive Approach255

10.2.2 A Fully Polynomial Randomized Scheme for DNF Counting257

10.3 From Approximate Sampling to Approximate Counting259

10.4 The Markov Chain Monte Carlo Method263

10.4.1 The Metropolis Algorithm265

10.5 Exercises267

10.6 An Exploratory Assignment on Minimum Spanning Trees270

11 Coupling of Markov Chains271

11.1 Variation Distance and Mixing Time271

11.2 Coupling274

11.2.1 Example: Shuffling Cards275

11.2.2 Example: Random Walks on the Hypercube276

11.2.3 Example: Independent Sets of Fixed Size277

11.3 Application: Variation Distance Is Nonincreasing278

11.4 Geometric Convergence281

11.5 Application: Approximately Sampling Proper Colorings282

11.6 Path Coupling286

11.7 Exercises289

12 Martingales295

12.1 Martingales295

12.2 Stopping Times297

12.2.1 Example: A Ballot Theorem299

12.3 Wald's Equation300

12.4 Tail Inequalities for Martingales303

12.5 Applications of the Azuma-Hoeffding Inequality305

12.5.1 General Formalization305

12.5.2 Application: Pattern Matching307

12.5.3 Application: Balls and Bins308

12.5.4 Application: Chromatic Number308

12.6 Exercises309

13 Pairwise Independence and Universal Hash Functions314

13.1 Pairwise Independence314

13.1.1 Example: A Construction of Pairwise Independent Bits315

13.1.2 Application: Derandomizing an Algorithm for Large Cuts316

13.1.3 Example: Constructing Pairwise Independent Values Moduloa Prime317

13.2 Chebyshev's Inequality for Pairwise Independent Variables318

13.2.1 Application: Sampling Using Fewer Random Bits319

13.3 Families of Universal Hash Functions321

13.3.1 Example: A 2-Universal Family of Hash Functions323

13.3.2 Example: A Strongly 2-Universal Family of Hash Functions324

13.3.3 Application: Perfect Hashing326

13.4 Application: Finding Heavy Hitters in Data Streams328

13.5 Exercises333

14 Balanced Allocations336

14.1 The Power of Two Choices336

14.1.1 The Upper Bound336

14.2 Two Choices: The Lower Bound341

14.3 Applications of the Power of Two Choices344

14.3.1 Hashing344

14.3.2 Dynamic Resource Allocation345

14.4 Exercises345

Further Reading349

Index350