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