Probability and Computing: Randomized Algorithms and Probabilistic Analysis

by Michael Mitzenmacher , Eli Upfal

• ISBN13: 9780521835404
• ISBN10: 0521835402
• Format: Hardcover
• Copyright: 2005-01-31
• Publisher: Cambridge University Press

Summary

Randomization and probabilistic techniques play an important role in modern computer science, with applications ranging from combinatorial optimization and machine learning to communication networks and secure protocols. This textbook is designed to accompany a one- or two-semester course for advanced undergraduates or beginning graduate students in computer science and applied mathematics. It gives an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It assumes only an elementary background in discrete mathematics and gives a rigorous yet accessible treatment of the material, with numerous examples and applications. The first half of the book covers core material, including random sampling, expectations, Markov's inequality, Chevyshev's inequality, Chernoff bounds, balls and bins models, the probabilistic method, and Markov chains. In the second half, the authors delve into more advanced topics such as continuous probability, applications of limited independence, entropy, Markov chain Monte Carlo methods, coupling, martingales, and balanced allocations. With its comprehensive selection of topics, along with many examples and exercises, this book is an indispensable teaching tool.

Table of Contents

Preface	xiii
1 Events and Probability	1	(19)
1.1 Application: Verifying Polynomial Identities	1	(2)
1.2 Axioms of Probability	3	(5)
1.3 Application: Verifying Matrix Multiplication	8	(4)
1.4 Application: A Randomized Min-Cut Algorithm	12	(2)
1.5 Exercises	14	(6)
2 Discrete Random Variables and Expectation	20	(24)
2.1 Random Variables and Expectation	20	(5)
2.1.1 Linearity of Expectations	22	(1)
2.1.2 Jensen's Inequality	23	(2)
2.2 The Bernoulli and Binomial Random Variables	25	(1)
2.3 Conditional Expectation	26	(4)
2.4 The Geometric Distribution	30	(4)
2.4.1 Example: Coupon Collector's Problem	32	(2)
2.5 Application: The Expected Run-Time of Quicksort	34	(4)
2.6 Exercises	38	(6)
3 Moments and Deviations	44	(17)
3.1 Markov's Inequality	44	(1)
3.2 Variance and Moments of a Random Variable	45	(3)
3.2.1 Example: Variance of a Binomial Random Variable	48	(1)
3.3 Chebyshev's Inequality	48	(4)
3.3.1 Example: Coupon Collector's Problem	50	(2)
3.4 Application: A Randomized Algorithm for Computing the Median	52	(5)
3.4.1 The Algorithm	53	(1)
3.4.2 Analysis of the Algorithm	54	(3)
3.5 Exercises	57	(4)
4 Chernoff Bounds	61	(29)
4.1 Moment Generating Functions	61	(2)
4.2 Deriving and Applying Chernoff Bounds	63	(6)
4.2.1 Chernoff Bounds for the Sum of Poisson Trials	63	(4)
4.2.2 Example: Coin Flips	67	(1)
4.2.3 Application: Estimating a Parameter	67	(2)
4.3 Better Bounds for Some Special Cases	69	(2)
4.4 Application: Set Balancing	71	(1)
4.5* Application: Packet Routing in Sparse Networks	72	(11)
4.5.1 Permutation Routing on the Hypercube	73	(5)
4.5.2 Permutation Routing on the Butterfly	78	(5)
4.6 Exercises	83	(7)
5 Balls, Bins, and Random Graphs	90	(36)
5.1 Example: The Birthday Paradox	90	(2)
5.2 Balls into Bins	92	(2)
5.2.1 The Balls-and-Bins Model	92	(1)
5.2.2 Application: Bucket Sort	93	(1)
5.3 The Poisson Distribution	94	(5)
5.3.1 Limit of the Binomial Distribution	98	(1)
5.4 The Poisson Approximation	99	(7)
5.4.1* Example: Coupon Collector's Problem, Revisited	104	(2)
5.5 Application: Hashing	106	(6)
5.5.1 Chain Hashing	106	(2)
5.5.2 Hashing: Bit Strings	108	(1)
5.5.3 Bloom Filters	109	(3)
5.5.4 Breaking Symmetry	112	(1)
5.6 Random Graphs	112	(6)
5.6.1 Random Graph Models	112	(1)
5.6.2 Application: Hamiltonian Cycles in Random Graphs	113	(5)
5.7 Exercises	118	(6)
5.8 An Exploratory Assignment	124	(2)
6 The Probabilistic Method	126	(27)
6.1 The Basic Counting Argument	126	(2)
6.2 The Expectation Argument	128	(3)
6.2.1 Application: Finding a Large Cut	129	(1)
6.2.2 Application: Maximum Satisfiability	130	(1)
6.3 Derandomization Using Conditional Expectations	131	(2)
6.4 Sample and Modify	133	(1)
6.4.1 Application: Independent Sets	133	(1)
6.4.2 Application: Graphs with Large Girth	134	(1)
6.5 The Second Moment Method	134	(2)
6.5.1 Application: Threshold Behavior in Random Graphs	135	(1)
6.6 The Conditional Expectation Inequality	136	(2)
6.7 The Lovasz Local Lemma	138	(4)
6.7.1 Application: Edge-Disjoint Paths	141	(1)
6.7.2 Application: Satisfiability	142	(1)
6.8* Explicit Constructions Using the Local Lemma	142	(4)
6.8.1 Application: A Satisfiability Algorithm	143	(3)
6.9 Lovasz Local Lemma: The General Case	146	(2)
6.10 Exercises	148	(5)
7 Markov Chains and Random Walks	153	(35)
7.1 Markov Chains: Definitions and Representations	153	(10)
7.1.1 Application: A Randomized Algorithm for 2-Satisfiability	156	(3)
7.1.2 Application: A Randomized Algorithm for 3-Satisfiability	159	(4)
7.2 Classification of States	163	(4)
7.2.1 Example: The Gambler's Ruin	166	(1)
7.3 Stationary Distributions	167	(7)
7.3.1 Example: A Simple Queue	173	(1)
7.4 Random Walks on Undirected Graphs	174	(3)
7.4.1 Application: An s-t Connectivity Algorithm	176	(1)
7.5 Parrondo's Paradox	177	(5)
7.6 Exercises	182	(6)
8 Continuous Distributions and the Poisson Process	188	(37)
8.1 Continuous Random Variables	188	(5)
8.1.1 Probability Distributions in R	188	(3)
8.1.2 Joint Distributions and Conditional Probability	191	(2)
8.2 The Uniform Distribution	193	(3)
8.2.1 Additional Properties of the Uniform Distribution	194	(2)
8.3 The Exponential Distribution	196	(5)
8.3.1 Additional Properties of the Exponential Distribution	197	(2)
8.3.2* Example: Balls and Bins with Feedback	199	(2)
8.4 The Poisson Process	201	(9)
8.4.1 Interarrival Distribution	204	(1)
8.4.2 Combining and Splitting Poisson Processes	205	(2)
8.4.3 Conditional Arrival Time Distribution	207	(3)
8.5 Continuous Time Markov Processes	210	(2)
8.6 Example: Markovian Queues	212	(7)
8.6.1 M/M/1 Queue in Equilibrium	213	(3)
8.6.2 M/M/1/K Queue in Equilibrium	216	(1)
8.6.3 The Number of Customers in an M/M/infinity Queue	216	(3)
8.7 Exercises	219	(6)
9 Entropy, Randomness, and Information	225	(27)
9.1 The Entropy Function	225	(3)
9.2 Entropy and Binomial Coefficients	228	(2)
9.3 Entropy: A Measure of Randomness	230	(4)
9.4 Compression	234	(3)
9.5* Coding: Shannon's Theorem	237	(8)
9.6 Exercises	245	(7)
10 The Monte Carlo Method	252	(19)
10.1 The Monte Carlo Method	252	(3)
10.2 Application: The DNF Counting Problem	255	(4)
10.2.1 The Naive Approach	255	(2)
10.2.2 A Fully Polynomial Randomized Scheme for DNF Counting	257	(2)
10.3 From Approximate Sampling to Approximate Counting	259	(4)
10.4 The Markov Chain Monte Carlo Method	263	(4)
10.4.1 The Metropolis Algorithm	265	(2)
10.5 Exercises	267	(3)
10.6 An Exploratory Assignment on Minimum Spanning Trees	270	(1)
11* Coupling of Markov Chains	271	(24)
11.1 Variation Distance and Mixing Time	271	(3)
11.2 Coupling	274	(4)
11.2.1 Example: Shuffling Cards	275	(1)
11.2.2 Example: Random Walks on the Hypercube	276	(1)
11.2.3 Example: Independent Sets of Fixed Size	277	(1)
11.3 Application: Variation Distance Is Nonincreasing	278	(3)
11.4 Geometric Convergence	281	(1)
11.5 Application: Approximately Sampling Proper Colorings	282	(4)
11.6 Path Coupling	286	(3)
11.7 Exercises	289	(6)
12 Martingales	295	(19)
12.1 Martingales	295	(2)
12.2 Stopping Times	297	(3)
12.2.1 Example: A Ballot Theorem	299	(1)
12.3 Wald's Equation	300	(3)
12.4 Tail Inequalities for Martingales	303	(2)
12.5 Applications of the Azuma-Hoeffding Inequality	305	(4)
12.5.1 General Formalization	305	(2)
12.5.2 Application: Pattern Matching	307	(1)
12.5.3 Application: Balls and Bins	308	(1)
12.5.4 Application: Chromatic Number	308	(1)
12.6 Exercises	309	(5)
13 Pairwise Independence and Universal Hash Functions	314	(22)
13.1 Pairwise Independence	314	(4)
13.1.1 Example: A Construction of Pairwise Independent Bits	315	(1)
13.1.2 Application: Derandomizing an Algorithm for Large Cuts	316	(1)
13.1.3 Example: Constructing Pairwise Independent Values Modulo a Prime	317	(1)
13.2 Chebyshev's Inequality for Pairwise Independent Variables	318	(3)
13.2.1 Application: Sampling Using Fewer Random Bits	319	(2)
13.3 Families of Universal Hash Functions	321	(7)
13.3.1 Example: A 2-Universal Family of Hash Functions	323	(1)
13.3.2 Example: A Strongly 2-Universal Family of Hash Functions	324	(2)
13.3.3 Application: Perfect Hashing	326	(2)
13.4 Application: Finding Heavy Hitters in Data Streams	328	(5)
13.5 Exercises	333	(3)
14* Balanced Allocations	336	(13)
14.1 The Power of Two Choices	336	(5)
14.1.1 The Upper Bound	336	(5)
14.2 Two Choices: The Lower Bound	341	(3)
14.3 Applications of the Power of Two Choices	344	(1)
14.3.1 Hashing	344	(1)
14.3.2 Dynamic Resource Allocation	345	(1)
14.4 Exercises	345	(4)
Further Reading	349	(1)
Index	350