"Greatly expanded, this new edition requires only an elementary background in discrete mathematics and offers a comprehensive introduction to the role of randomization and probabilistic techniques in modern computer science. Newly added chapters and sections cover topics including normal distributions, sample complexity, VC dimension, Rademacher complexity, power laws and related distributions, cuckoo hashing, and the Lovasz Local Lemma. Material relevant to machine learning and big data analysis enables students to learn modern techniques and applications. Among the many new exercises and examples are programming-related exercises that provide students with excellent training in solving relevant problems. This book provides an indispensable teaching tool to accompany a one- or two-semester course for advanced undergraduate students in computer science and applied mathematics"-- Provided by publisher

upload/bibliotik/0_Other/2/2017 Michael Mitzenmacher - Probability and Computing[2ndED]_Rxl.pdf

upload/motw_shc_2025_10/shc/Probability and Computing_ Rand - Michael Mitzenmacher.pdf

motw/Probability and Computing_ Rand - Michael Mitzenmacher.pdf

nexusstc/Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis/fa736966d7eda7ccce4f40918b559ecc.pdf

lgli/Cambridge.University.Press.Probability.and.Computing.2nd.Edition.110715488X.pdf

lgrsnf/Cambridge.University.Press.Probability.and.Computing.2nd.Edition.110715488X.pdf

zlib/Computers/Programming/Michael Mitzenmacher, Eli Upfal/Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis_3343685.pdf

Michael Mitzenmacher and Eli Upfal

RCOG Press

Second edition, Cambridge United Kingdom ; New York NY USA, 2017

United Kingdom and Ireland, United Kingdom

0

lg2101827

producers:
Acrobat Distiller 10.1.10 (Windows)

{"edition":"2","isbns":["110715488X","1316651126","9781107154889","9781316651124"],"last_page":484,"publisher":"Cambridge University Press"}

Memory of the World Librarian: Slowrotation

Cover 1
Half title 3
Title 5
Copyright 6
Dedication 7
Contents 9
Preface to the Second Edition 17
Preface to the First Edition 19
1 Events and Probability 23
1.1 Application: Verifying Polynomial Identities 23
1.2 Axioms of Probability 25
1.3 Application: Verifying Matrix Multiplication 30
1.4 Application: Naïve Bayesian Classifier 34
1.5 Application: A Randomized Min-Cut Algorithm 37
1.6 Exercises 39
2 Discrete Random Variables and Expectation 45
2.1 Random Variables and Expectation 45
2.1.1 Linearity of Expectations 47
2.1.2 Jensen's Inequality 48
2.2 The Bernoulli and Binomial Random Variables 49
2.3 Conditional Expectation 51
2.4 The Geometric Distribution 55
2.4.1 Example: Coupon Collector's Problem 57
2.5 Application: The Expected Run-Time of Quicksort 59
2.6 Exercises 62
3 Moments and Deviations 69
3.1 Markov's Inequality 69
3.2 Variance and Moments of a Random Variable 70
3.2.1 Example: Variance of a Binomial Random Variable 73
3.3 Chebyshev's Inequality 73
3.3.1 Example: Coupon Collector's Problem 75
3.4 Median and Mean 77
3.5 Application: A Randomized Algorithm for Computing the Median 79
3.5.1 The Algorithm 80
3.5.2 Analysis of the Algorithm 81
3.6 Exercises 84
4 Chernoff and Hoeffding Bounds 88
4.1 Moment Generating Functions 88
4.2 Deriving and Applying Chernoff Bounds 90
4.2.1 Chernoff Bounds for the Sum of Poisson Trials 90
4.2.2 Example: Coin Flips 94
4.2.3 Application: Estimating a Parameter 94
4.3 Better Bounds for Some Special Cases 95
4.4 Application: Set Balancing 98
4.5 The Hoeffding Bound 99
4.6* Application: Packet Routing in Sparse Networks 101
4.6.1 Permutation Routing on the Hypercube 102
4.6.2 Permutation Routing on the Butterfly 107
4.7 Exercises 112
5 Balls, Bins, and Random Graphs 119
5.1 Example: The Birthday Paradox 119
5.2 Balls into Bins 121
5.2.1 The Balls-and-Bins Model 121
5.2.2 Application: Bucket Sort 123
5.3 The Poisson Distribution 123
5.3.1 Limit of the Binomial Distribution 127
5.4 The Poisson Approximation 129
5.4.1* Example: Coupon Collector's Problem, Revisited 133
5.5 Application: Hashing 135
5.5.1 Chain Hashing 135
5.5.2 Hashing: Bit Strings 136
5.5.3 Bloom Filters 138
5.5.4 Breaking Symmetry 140
5.6 Random Graphs 141
5.6.1 Random Graph Models 141
5.6.2 Application: Hamiltonian Cycles in Random Graphs 143
5.7 Exercises 149
5.8 An Exploratory Assignment 155
6 The Probabilistic Method 157
6.1 The Basic Counting Argument 157
6.2 The Expectation Argument 159
6.2.1 Application: Finding a Large Cut 160
6.2.2 Application: Maximum Satisfiability 161
6.3 Derandomization Using Conditional Expectations 162
6.4 Sample and Modify 164
6.4.1 Application: Independent Sets 164
6.4.2 Application: Graphs with Large Girth 165
6.5 The Second Moment Method 165
6.5.1 Application: Threshold Behavior in Random Graphs 166
6.6 The Conditional Expectation Inequality 167
6.7 The Lovász Local Lemma 169
6.7.1 Application: Edge-Disjoint Paths 172
6.7.2 Application: Satisfiability 173
6.8* Explicit Constructions Using the Local Lemma 174
6.8.1 Application: A Satisfiability Algorithm 174
6.9 Lovász Local Lemma: The General Case 177
6.10* The Algorithmic Lovász Local Lemma 180
6.11 Exercises 184
7 Markov Chains and Random Walks 190
7.1 Markov Chains: Definitions and Representations 190
7.1.1 Application: A Randomized Algorithm for 2-Satisfiability 193
7.1.2 Application: A Randomized Algorithm for 3-Satisfiability 196
7.2 Classification of States 200
7.2.1 Example: The Gambler's Ruin 203
7.3 Stationary Distributions 204
7.3.1 Example: A Simple Queue 210
7.4 Random Walks on Undirected Graphs 211
7.4.1 Application: An s–t Connectivity Algorithm 214
7.5 Parrondo's Paradox 215
7.6 Exercises 220
8 Continuous Distributions and the Poisson Process 227
8.1 Continuous Random Variables 227
8.1.1 Probability Distributions in R 227
8.1.2 Joint Distributions and Conditional Probability 230
8.2 The Uniform Distribution 232
8.2.1 Additional Properties of the Uniform Distribution 233
8.3 The Exponential Distribution 235
8.3.1 Additional Properties of the Exponential Distribution 236
8.3.2* Example: Balls and Bins with Feedback 238
8.4 The Poisson Process 240
8.4.1 Interarrival Distribution 243
8.4.2 Combining and Splitting Poisson Processes 244
8.4.3 Conditional Arrival Time Distribution 246
8.5 Continuous Time Markov Processes 248
8.6 Example: Markovian Queues 251
8.6.1 M/M/1 Queue in Equilibrium 252
8.6.2 M/M/1/K Queue in Equilibrium 255
8.6.3 The Number of Customers in an M/M/∞ Queue 255
8.7 Exercises 258
9 The Normal Distribution 264
9.1 The Normal Distribution 264
9.1.1 The Standard Normal Distribution 264
9.1.2 The General Univariate Normal Distribution 265
9.1.3 The Moment Generating Function 268
9.2* Limit of the Binomial Distribution 269
9.3 The Central Limit Theorem 271
9.4* Multivariate Normal Distributions 274
9.4.1 Properties of the Multivariate Normal Distribution 277
9.5 Application: Generating Normally Distributed Random Values 278
9.6 Maximum Likelihood Point Estimates 280
9.7 Application: EM Algorithm For a Mixture of Gaussians 283
9.8 Exercises 287
10 Entropy, Randomness, and Information 291
10.1 The Entropy Function 291
10.2 Entropy and Binomial Coefficients 294
10.3 Entropy: A Measure of Randomness 296
10.4 Compression 300
10.5* Coding: Shannon's Theorem 303
10.6 Exercises 312
11 The Monte Carlo Method 319
11.1 The Monte Carlo Method 319
11.2 Application: The DNF Counting Problem 322
11.2.1 The Naïve Approach 322
11.2.2 A Fully Polynomial Randomized Scheme for DNF Counting 324
11.3 From Approximate Sampling to Approximate Counting 326
11.4 The Markov Chain Monte Carlo Method 330
11.4.1 The Metropolis Algorithm 332
11.5 Exercises 334
11.6 An Exploratory Assignment on Minimum Spanning Trees 337
12 Coupling of Markov Chains 339
12.1 Variation Distance and Mixing Time 339
12.2 Coupling 342
12.2.1 Example: Shuffling Cards 343
12.2.2 Example: Random Walks on the Hypercube 344
12.2.3 Example: Independent Sets of Fixed Size 345
12.3 Application: Variation Distance Is Nonincreasing 346
12.4 Geometric Convergence 349
12.5 Application: Approximately Sampling Proper Colorings 350
12.6 Path Coupling 354
12.7 Exercises 358
13 Martingales 363
13.1 Martingales 363
13.2 Stopping Times 365
13.2.1 Example: A Ballot Theorem 367
13.3 Wald's Equation 368
13.4 Tail Inequalities for Martingales 371
13.5 Applications of the Azuma–Hoeffding Inequality 373
13.5.1 General Formalization 373
13.5.2 Application: Pattern Matching 375
13.5.3 Application: Balls and Bins 376
13.5.4 Application: Chromatic Number 377
13.6 Exercises 377
14 Sample Complexity, VC Dimension, and Rademacher Complexity 383
14.1 The Learning Setting 384
14.2 VC Dimension 385
14.2.1 Additional Examples of VC Dimension 387
14.2.2 Growth Function 388
14.2.3 VC dimension component bounds 390
14.2.4 ε-nets and ε-samples 391
14.3 The ε-net Theorem 392
14.4 Application: PAC Learning 396
14.5 The ε-sample Theorem 399
14.5.1 Application: Agnostic Learning 401
14.5.2 Application: Data Mining 402
14.6 Rademacher Complexity 404
14.6.1 Rademacher Complexity and Sample Error 407
14.6.2 Estimating the Rademacher Complexity 409
14.6.3 Application: Agnostic Learning of a Binary Classification 410
14.7 Exercises 411
15 Pairwise Independence and Universal Hash Functions 414
15.1 Pairwise Independence 414
15.1.1 Example: A Construction of Pairwise Independent Bits 415
15.1.2 Application: Derandomizing an Algorithm for Large Cuts 416
15.1.3 Example: Constructing Pairwise Independent Values Modulo a Prime 417
15.2 Chebyshev's Inequality for Pairwise Independent Variables 418
15.2.1 Application: Sampling Using Fewer Random Bits 419
15.3 Universal Families of Hash Functions 421
15.3.1 Example: A 2-Universal Family of Hash Functions 423
15.3.2 Example: A Strongly 2-Universal Family of Hash Functions 424
15.3.3 Application: Perfect Hashing 426
15.4 Application: Finding Heavy Hitters in Data Streams 429
15.5 Exercises 433
16 Power Laws and Related Distributions 437
16.1 Power Law Distributions: Basic Definitions and Properties 438
16.2 Power Laws in Language 440
16.2.1 Zipf's Law and Other Examples 440
16.2.2 Languages via Optimization 441
16.2.3 Monkeys Typing Randomly 441
16.3 Preferential Attachment 442
16.3.1 A Formal Version 444
16.4 Using the Power Law in Algorithm Analysis 447
16.5 Other Related Distributions 449
16.5.1 Lognormal Distributions 449
16.5.2 Power Law with Exponential Cutoff 450
16.6 Exercises 451
17 Balanced Allocations and Cuckoo Hashing 455
17.1 The Power of Two Choices 455
17.1.1 The Upper Bound 455
17.2 Two Choices: The Lower Bound 460
17.3 Applications of the Power of Two Choices 463
17.3.1 Hashing 463
17.3.2 Dynamic Resource Allocation 464
17.4 Cuckoo Hashing 464
17.5 Extending Cuckoo Hashing 474
17.5.1 Cuckoo Hashing with Deletions 474
17.5.2 Handling Failures 475
17.5.3 More Choices and Bigger Bins 476
17.6 Exercises 478
Further Reading 485
Index 486

2017-09-04