User:Erel Segal/Probability and Computing 2006

An index to:

Mitzenmacher, Michael; Upfal, Eli (2006). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 9780521835404.

1. Events and Probability

1. Application: random algorithm for Polynomial identity testing
2. Axioms of probability
3. Application: random algorithm for verifying matrix multiplication.
4. Application: random algorithm for finding a minimum cut.

2. Discrete Random Variables and Expectation

1. Random variables and expectation
   • Linearity of Expectations
   • Jensen's inequality
2. The Bernouli random variable and Binomial random variable.
3. Conditional expectation
4. The Geometric distribution
   • Example: Coupon collector's problem
5. Application: the expected run-time of quicksort

3. Moments and Deviations

1. Markov's inequality
2. Variance and moments of a random variable.
   • Example: variance of a binomial random variable
3. Chebyshev's inequality
   • Example: Coupon collector's problem
4. Application: random algorithm for computing median

4. Chernoff bounds

1. Moment-generating functions
2. Deriving and applying Chernoff bounds
   • Chernoff bound for the sum of Poisson trials
   • Example: coin flips
   • Application: parameter estimation
3. Better bounds for some special cases
4. Application: set balancing
5. Application: Routing protocol for packet-routing in sparse networks.
   • Permutation routing on a Hypercube graph network
   • Permutation routing on a Butterfly graph network

5. Balls, bins and random graphs

1. Example: the birthday paradox
2. Balls into bins
   • The balls-and-bins model
   • Application: bucket sort
3. The Poisson distribution
   • Limit of the binomial distribution
4. The Poisson approximation
   • Example: Coupon collector's problem, revisited
5. Application: Hash table
   • Chain hashing
   • Hashing: bit strings
   • Bloom filters
   • Breaking symmetry
6. Random graphs
   • Random graph models
   • Application: Hamiltonian cycles in random graphs

6. The Probabilistic method

1. The basic counting argument
2. The expectation argument
   • Application: finding a large cut
   • Application: maximum satisfiability
3. Derandomisation using conditional expectations
4. Sample and Modify
   • Application: independent sets
   • Application: graphs with large girth
5. The Second moment method
   • Application: threshold behaviour in random graphs
6. The conditional expectation inequality
7. The Lovász local lemma
   • Application: edge-disjoint paths
   • Application: Boolean satisfiability problem
8. Explicit constructions using the Local Lemma
   • Application: a satisfiability algorithm
9. Lovász local lemma: the general case

7. Markov chains and Random walks

1. Markov chains: definitions and representation
   • Application: a randomized algorithm for 2-satisfiability
   • Application: a randomized algorithm for 3-satisfiability
2. Classification of states
   • Example: the gambler's ruin
3. Stationary distributions
   • Example: a simple queue
4. Random walks on undirected graphs
   • Application: an s-t connectivity algorithm
5. Parrondo's paradox

8. Continuous distributions and the Poisson process

1. Continuous Random Variables
   • Probability distributions in R
   • Joint probability distributions and conditional probability
2. The Continuous uniform distribution
   • Additional properties of the uniform distribution
3. The Exponential distribution
   • Additional properties of the exponential distribution
   • Example: Balls into bins with feedback
4. The Poisson point process
   • Interarrival distribution
   • Combining and splitting Poisson processes
   • Conditional arrival time distribution
5. Continuous time Markov processes
6. Example: Markovian Queues
   • M/M/1 queue in equilibrium
   • M/M/1/K queue in equilibrium
   • The number of customers in an M/M/∞ queue

9. Entropy, randomness and information

1. The entropy function
2. Entropy and binomial coefficients
3. Entropy: a measure of randomness
4. coding: Shannon's theorem

10. The Monte Carlo Method

1. The Monte Carlo method; FPRAS (Fully Polynomial Randomized Approximation Scheme).
2. Application: the DNF counting problem - counting the number of satisfying assignments to a DNF formula
   • The Naive approach - might be exponential-time.
   • A FPRAS for DNF counting - always polynomial-time.
3. From approxiamte sampling to approximate counting
4. The Markov chain Monte Carlo method
   • The Metropolis–Hastings algorithm

11. Coupling of Markov chains

1. Variation distance and Mixing time
2. Coupling
   • Example: Shuffling cards
   • Example: random walks on the hypercube graphs
   • Example: independent sets of fixed size
3. Application: Variation distance is nonincreasing
4. Geometric convergence
5. Application: Approximately sampling proper colorings
6. Path coupling

12. Martingales

1. Martingales and Doob martingale
2. Stopping time
   • Example: a ballot theorem
3. Wald's equation
4. Tail inequalities for martingales
5. Applications of the Azuma-Hoeffding inequality
   • General formalization
   • Application: pattern matching
   • Application: Balls into bins
   • Application: Chromatic number

13. Pairwise independence and Universal hash function

1. Pairwise independence
   • Example: a construction of Pairwise Independent Bits
   • Application: Derandomizing of Algorithm for Large Cuts
   • Example: constructing pairwise independent values modulu a prime
2. Chebyshev's inequality for Pairwise independent variables
   • Application: sampling using fewer random bits
3. Families of Universal hash functions
   • Example: a 2-universal family of hash functions
   • Example: a strongly 2-universal family of hash functions
   • Application: perfect hashing
4. Application: finding heavy hitters in data streams

14. Balanced allocations

1. The power of two choices
   • The upper bound
2. Two choices: the lower bound
3. Applications of the power of two choices
   • Hashing
   • Dynamic resource allocation

Links

• Randomized algorithm
• Poisson distribution
• Bloom filter
• Chebyshev's inequality
• Martingale (betting system)
• Maximum cut
• Concentration inequality
• Chernoff bound
• Set balancing
• Eli Upfal