- Lectures
- Omar Fawzi
- Mondays 13:30-15:30
- Amphi B

- Tutorials
- Elena Krishanova and Bertrand Simon
- ??

- Probability formalism (illustrated with fingerprinting, min-cut algorithm and more)
- Concerntration bounds (Chernoff, Azuma-Hoeffding)
- Random graphs
- The probabilistic method
- Markov chains
- Continuous distributions

- [MU] Probability and Computing: Randomized Algorithms and Probabilistic Analysis
- [O'Do] Probability and Computing lecture notes.
- [Sah] Discrete mathematics and probability theory lecture notes (starting at Lecture 10).

- A final exam
- One midterm exam
- Homeworks (every 1 or 2 weeks)

Date | Topic | References |

Jan 30th | Probability spaces, events, independence, conditioning. Examples: Veryfing polynomial identities and matrix multiplication. |
Ch 1 of [MU] with slightly more formal definitions for prob space |

Feb 1st | Examples of probability spaces, Borel sets, Lebesgue measure. Random variables and expectation. Linearity of expectation. |
Beginning of ch 2 of [MU] with more formal definitions. See also lecture notes 1,2,3 from this course |

Feb 8th | Geometric and binomial distributions. Coupon collector problem. Randomized quicksort. Markov's inequality. Variance. Variance of a sum of independent random variables. Chebychev's inequality. |
Continuing ch 2 and beginning of ch 3 of [MU] |

Feb 27th | Chernoff bounds for binomial(n,1/2) and sums of independent 0,1 random variables. Sampling application of Chernoff. Load balancing (Chernoff + union bound method). |
Ch 4 of [MU]. See also [O'Do] on Chernoff bounds and load balancing. |

Mar 5th | Random processes. Balls and bins: birthday problem, maximum load (ln n)/(ln ln n) for n = m. Poisson approximation (Bin(n,c/n) similar to Poi(c)) Random graphs: isolated vertices. Branchings processes (definition and analysis of expected size of generation n). Defined conditional expectation (for discrete rvs). |
Ch 5 [MU]. Lecture notes on random graphs (also has a chapter on branching processes) |

Mar 13th |
Finished branching processes: extinction probability. The probabilistic method. Lower bound on Ramsey numbers. Using expectation argument: maximum satisfiability. Sample and modify: graphs with large girth. Lovasz local lemma: sufficient condition for a formula to be satisfiable. |
Ch 6 [MU] |

Mar 20th |
Randomized algorithms. Monte-Carlo and Las Vegas. Examples: Min-cut (contractions), Miller-Rabin primality testing and finding an assignement satisfying 7/8 clauses.
Started coninuous distributions. |
Ch 1 of [MU] for min-cut. [O'Do] for Miller Rabin |

Mar 28th |
Continuous distributions. Jointly continuous disctribution. Buffon's needle example. Minimum of n uniforms. Examples: Uniform, exponential (with memoryless property), (Multivariate) Normal distribution. Application: Johnson-Lindenstrauss for dimension reduction (without proof) |
Ch 8 of [MU] |