User:Erel Segal/Probability and Computing 2006

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: paramerter 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 Poission 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