## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Book Description

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.

1. Cover
2. Title
4. Contents
5. Preface
6. 1 Events and Probability
7. 2 Discrete Random Variables and Expectation
1. 2.1 Random Variables and Expectation
2. 2.2 The Bernoulli and Binomial Random Variables
3. 2.3 Conditional Expectation
4. 2.4 The Geometric Distribution
5. 2.5 Application: The Expected Run-Time of Quicksort
6. 2.6 Exercises
8. 3 Moments and Deviations
1. 3.1 Markov’s Inequality
2. 3.2 Variance and Moments of a Random Variable
3. 3.3 Chebyshev’s Inequality
4. 3.4 Application: A Randomized Algorithm for Computing the Median
5. 3.5 Exercises
9. 4 Chernoff Bounds
1. 4.1 Moment Generating Functions
2. 4.2 Deriving and Applying Chernoff Bounds
3. 4.3 Better Bounds for Some Special Cases
4. 4.4 Application: Set Balancing
5. 4.5* Application: Packet Routing in Sparse Networks
6. 4.5.1 Permutation Routing on the Hypercube
7. 4.6 Exercises
10. 5 Balls, Bins, and Random Graphs
1. 5.1 Example: The Birthday Paradox
2. 5.2 Balls into Bins
3. 5.3 The Poisson Distribution
4. 5.4 The Poisson Approximation
5. 5.5 Application: Hashing
6. 5.6 Random Graphs
7. 5.7 Exercises
8. 5.8 An Exploratory Assignment
11. 6 The Probabilistic Method
1. 6.1 The Basic Counting Argument
2. 6.2 The Expectation Argument
3. 6.3 Derandomization Using Conditional Expectations
4. 6.4 Sample and Modify
5. 6.5 The Second Moment Method
6. 6.6 The Conditional Expectation Inequality
7. 6.7 The Lovasz Local Lemma
8. 6.8* Explicit Constructions Using the Local Lemma
9. 6.9 Lovasz Local Lemma: The General Case
10. 6.10 Exercises
12. 7 Markov Chains and Random Walks
1. 7.1 Markov Chains: Definitions and Representations
2. 7.2 Classification of States
3. 7.3 Stationary Distributions
4. 7.4 Random Walks on Undirected Graphs
6. 7.6 Exercises
13. 8 Continuous Distributions and the Poisson Process
1. 8.1 Continuous Random Variables
2. 8.2 The Uniform Distribution
3. 8.3 The Exponential Distribution
4. 8.4 The Poisson Process
5. 8.5 Continuous Time Markov Processes
6. 8.6 Example: Markovian Queues
7. 8.7 Exercises
14. 9 Entropy, Randomness, and Information
15. 10 The Monte Carlo Method
1. 10.1 The Monte Carlo Method
2. 10.2 Application: The DNF Counting Problem
3. 10.3 From Approximate Sampling to Approximate Counting
4. 10.4 The Markov Chain Monte Carlo Method
5. 10.5 Exercises
6. 10.6 An Exploratory Assignment on Minimum Spanning Trees
16. 11* Coupling of Markov Chains
1. 11.1 Variation Distance and Mixing Time
2. 11.2 Coupling
3. 11.3 Application: Variation Distance Is Nonincreasing
4. 11.4 Geometric Convergence
5. 11.5 Application: Approximately Sampling Proper Colorings
6. 11.6 Path Coupling
7. 11.7 Exercises
17. 12 Martingales
1. 12.1 Martingales
2. 12.2 Stopping Times
3. 12.3 Wald’s Equation
4. 12.4 Tail Inequalities for Martingales
5. 12.5 Applications of the Azuma-Hoeffding Inequality
6. 12.6 Exercises
18. 13 Pairwise Independence and Universal Hash Functions
1. 13.1 Pairwise Independence
2. 13.2 Chebyshev’s Inequality for Pairwise Independent Variables
3. 13.3 Families of Universal Hash Functions
4. 13.5 Exercises
19. 14* Balanced Allocations
1. 14.1 The Power of Two Choices
2. 14.2 Two Choices: The Lower Bound
3. 14.3 Applications of the Power of Two Choices
4. 14.4 Exercises