发帖
雷达卡
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
提升卡
置顶卡
沉默卡
变色卡
抢沙发
千斤顶
显身卡
京公网安备 11010802022788号
