Mitzenmacher M., Upfal E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Cambridge: Cambridge University Press, 2005. - 366p.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.Why Randomness?
The BookApplication: Verifying Polynomial Identities
Axioms of Probability
Application: Verifying Matrix Multiplication
Application: A Randomized Min-Cut Algorithm
Exercises
Random Variables and Expectation
The Bernoulli and Binomial Random Variables
Conditional Expectation
The Geometric Distribution
Application: The Expected Run-Time of Quicksort
Exercises
Markov's Inequality
Variance and Moments of a Random Variable
Chebyshev's Inequality
Application: A Randomized Algorithm for Computing the Median
Exercises
Moment Generating Functions
Deriving and Applying Chernoff Bounds
Better Bounds for Some Special Cases
Application: Set Balancing
* Application: Packet Routing in Sparse Networks
Exercises
Example: The Birthday Paradox
Balls into Bins
The Poisson Distribution
The Poisson Approximation
Application: Hashing
Random Graphs
Exercises
An Exploratory Assignment
The Basic Counting Argument
The Expectation Argument
Derandomization Using Conditional Expectations
Sample and Modify
The Second Moment Method
The Conditional Expectation Inequality
The Lovasz Local Lemma
* Explicit Constructions Using the Local Lemma
Lovasz Local Lemma: The General Case
Exercises
Markov Chains: Definitions and Representations
Classification of States
Stationary Distributions
Random Walks on Undirected Graphs
Parrondo's Paradox
Exercises
Continuous Random Variables
The Uniform Distribution
The Exponential Distribution
The Poisson Process
Continuous Time Markov Processes
Example: Markovian Queues
Exercises
The Entropy Function
Entropy and Binomial Coefficients
Entropy: A Measure of Randomness
Compression
* Coding: Shannon's Theorem
Exercises
The Monte Carlo Method
Application: The DNF Counting Problenl
From Approximate Sampling to Approximate Counting
The Markov Chain Monte Carlo Method
Exercises
An Exploratory Assignment on Minimum Spanning Trees
Variation Distance and Mixing Time
Coupling
Application: Variation Distance Is Nonincreasing
Geometric Convergence
Application: Approximately Sampling Proper Colorings
Path Coupling
Exercises
Martingales
Stopping Times
Wald's Equation
Tail Inequalities for Martingales
Applications of the Azuma-Hoeffding Inequality
Exercises
Pairwise Independence
Chebyshev's Inequality for Pairwise Independent Variables
Families of Universal Hash Functions
Application: Finding Heavy Hitters in Data Streams
Exercises
The Power of Two Choices
Two Choices: The Lower Bound
Applications of the Power of Two Choices
Exercises
Further Reading