Probabilistic Methods

Below are lecture notes from my Spring 2025 course on Probabilistic Methods.  Source material include The Probabilistic Method by Noga Alon and Joel Spencer as well as online materials from Yufei Zhao and Luke Postle. Beware: there may be many typos!

1. Basics 

2. Linearity of Expectation 

   • Turan Theory

3. Alterations 

4. Second Moment Methods 

   • Chernoff Bounds

   • Rodl Nibble 

5. Lovasz Local Lemma 

   • Moser--Tardos Algorithm 

6. Correlation Inequalities 

7. Martingales and Tight Concentrations 

   • McDiarmid and Talagrand Inequalities

8. The Poisson Paradigm 

9. Codes, Games, and Entropy: Liar games

   • Entropy and Applications

10.  Dependent Random Choice 

11. Discrepancy

    • Lower bounds