Probability and Computing: Randomized Algorithms and Probabilistic Analysis
Publisher: Cambridge University | Pages: 368 | 2005-01-31 | ISBN [url=]0521835402[/url] | DJVU | 2 MB

Assuming only an elementary background in discrete mathematics, this textbook is an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It includes random sampling, expectations, Markov's and Chevyshev's inequalities, Chernoff bounds, balls and bins models, the probabilistic method, Markov chains, MCMC, martingales, entropy, and other topics. The book is designed to accompany a one- or two-semester course for graduate students in computer science and applied mathematics.




目录
Verifying Polynomial Identities 1
  
12 Axioms of Probability 3
  
Verifying Matrix Multiplication 8
  
A Randomized MinCut Algorithm 12
  
15 Exercises 14
  
21 Random Variables and Expectation 20
  
211 Linearity of Expectations 22
  
212 Jensens Inequality 23
  
75 Parrondos Paradox 177
  
76 Exercises 182
  
81 Continuous Random Variables 811 Probability Distributions in R 188
  
812 Joint Distributions and Conditional Probability 191
  
82 The Uniform Distribution 193
  
821 Additional Properties of the Uniform Distribution 194
  
83 The Exponential Distribution 196
  
831 Additional Properties of the Exponential Distribution 197
  
22 The Bernoulli and Binomial Random Variables 25
  
23 Conditional Expectation 26
  
24 The Geometric Distribution 30
  
Coupon Collectors Problem 32
  
The Expected RunTime of Quicksort 34
  
26 Exercises 38
  
31 Markovs Inequality 44
  
32 Variance and Moments of a Random Variable 45
  
33 Chebyshevs Inequality 48
  
Coupon Collectors Problem 50
  
A Randomized Algorithm for Computing the Median 52
  
341 The Algorithm 53
  
342 Analysis of the Algorithm 54
  
35 Exercises 57
  
41 Moment Generating Functions 61
  
421 Chernoff Bounds for the Sum ofPoisson Trials 63
  
Estimating a Parameter 67
  
43 Better Bounds for Some Special Cases 69
  
Set Balancing 71
  
Packet Routing in Sparse Networks 72
  
451 Permutation Routing on the Hypercube 73
  
452 Permutation Routing on the Butterfly 78
  
46 Exercises 83
  
The Birthday Paradox 90
  
52 Balls into Bins 521 The BallsandBins Model 92
  
Bucket Sort 93
  
53 The Poisson Distribution 94
  
531 Limit of the Binomial Distribution 98
  
54 The Poisson Approximation 99
  
Coupon Collectors Problem Revisited 104
  
Hashing 551 Chain Hashing 106
  
Bit Strings 107
  
553 Bloom Filters 109
  
554 Breaking Symmetry 111
  
56 Random Graphs 561 Random Graph Models 112
  
Hamiltonian Cycles in Random Graphs 113
  
57 Exercises 119
  
58 An Exploratory Assignment 124
  
61 The Basic Counting Argument 126
  
62 The Expectation Argument 128
  
Finding a Large Cut 129
  
Maximum Satisfiability 130
  
63 Derandomization Using Conditional Expectations 131
  
Independent Sets 133
  
65 The Second Moment Method 134
  
Threshold Behavior in Random Graphs 135
  
66 The Conditional Expectation Inequality 136
  
67 The Lovasz Local Lemma 138
  
EdgeDisjoint Paths 141
  
68 Explicit Constructions Using the Local Lemma 142
  
A Satisfiability Algorithm 143
  
The General Case 146
  
610 Exercises 148
  
Definitions and Representations 153
  
A Randomized Algorithm for 2Satisfiability 156
  
A Randomized Algorithm for 3Satisfiability 159
  
72 Classification of States 163
  
The Gamblers Ruin 166
  
73 Stationary Distributions 167
  
A Simple Queue 173
  
74 Random Walks on Undirected Graphs 174
  
An st Connectivity Algorithm 176
  
Balls and Bins with Feedback 199
  
84 The Poisson Process 201
  
841 Interarrival Distribution 204
  
842 Combining and Splitting Poisson Processes 205
  
843 Conditional Arrival Time Distribution 207
  
85 Continuous Time Markov Processes 210
  
Markovian Queues 212
  
861 MMl Queue in Equilibrium 213
  
863 The Number of Customers in an MMoo Queue 216
  
87 Exercises 219
  
91 The Entropy Function 225
  
92 Entropy and Binomial Coefficients 228
  
A Measure of Randomness 230
  
94 Compression 234
  
Shannons Theorem 237
  
96 Exercises 245
  
101 The Monte Carlo Method 252
  
1021 The Naive Approach 255
  
1022 A Fully Polynomial Randomized Scheme for DNF Counting 257
  
103 From Approximate Sampling to Approximate Counting 259
  
104 The Markov Chain Monte Carlo Method 263
  
1041 The Metropolis Algorithm 265
  
105 Exercises 267
  
106 An Exploratory Assignment on Minimum Spanning Trees 270
  
111 Variation Distance and Mixing Time 271
  
112 Coupling 274
  
Shuffling Cards 275
  
Random Walks on the Hypercube 276
  
Independent Sets of Fixed Size 277
  
Variation Distance Is Nonincreasing 278
  
114 Geometric Convergence 281
  
Approximately Sampling Proper Colorings 282
  
116 Path Coupling 286
  
117 Exercises 289
  
121 Martingales 295
  
122 Stopping Times 297
  
A Ballot Theorem 299
  
123 Walds Equation 300
  
124 Tail Inequalities for Martingales 303
  
125 Applications of the AzumaHoeffding Inequality 1251 General Formalization 305
  
Pattern Matching 307
  
Chromatic Number 308
  
126 Exercises 309
  
131 Pairwise Independence 314
  
A Construction of Pairwise Independent Bits 315
  
Derandomizing an Algorithm for Large Cuts 316
  
Constructing Pairwise Independent Values Modulo a Prime 317
  
132 Chebyshevs Inequality for Pairwise Independent Variables 318
  
Sampling Using Fewer Random Bits 319
  
133 Families of Universal Hash Functions 321
  
A 2Universal Family of Hash Functions 323
  
A Strongly 2Universal Family of Hash Functions 324
  
Perfect Hashing 326
  
Finding Heavy Hitters in Data Streams 328
  
135 Exercises 333
  
1411 The Upper Bound 336
  
The Lower Bound 341
  
1431 Hashing 344
  
144 Exercises 345
  
Further Reading 349
  
Index 350