Math 523 - Advanced Probability

Mon,Fri 11:00-12:20 at LOW 106.

The applications of probability to many areas in Mathematics and in other fields have multiplied dramatically in recent years. Rich interactions with classical analysis have been found in the study of random fractals; researchers in Combinatorics, Theoretical CS, machine learning, high-dimensional geometry (and, of course, Statistics) increasingly need sophisticated probabilistic tools. The aim of this course is to provide such tools, while also preparing the students for more advanced courses in Probability.

The main focus will be on martingales and their applications in Discrete Mathematics and Computer Science. These include: concentration inequalities, optional stopping, maximal inequalities, L² martingales, and much more.

Homework (35%), Take-home exam (35%) [done individually, but with open books], Presentations (30%).
Students can opt to be graded solely on the HW and take-home exam, 50% each.
Group discussions on the material and HW are encouraged, yet writing up the HW must be done individually.

• Homework #1 (due April 20)
• Homework #2 (due May 11)
• Home exam (due June 9)

• Lecture #1 (Mar 30) : Definitions and Examples
• Lecture #2 (Apr 3) : Concentration: The Hoeffding-Azuma inequality
• Lecture #3 (Apr 6) : The Optional stopping Theorem
• Lecture #4 (Apr 10) : Applications of Optional stopping I
• Lecture #5 (Apr 13) : Applications of Hoeffding-Azuma
• Lecture #6 (Apr 17) : Applications of Optional stopping II
• Lecture #7 (Apr 20) : Concentration for stochastic TSP
• Lecture #8 (Apr 24) : Martingales in R^d
• Lecture #9 (Apr 27) : Optional stopping: RWs and recursive majority
• Lectures #10,11 (May 1,4) : Martingales and percolation
• Lectures #12,13 (May 8,11) : The Upcrossing Lemma

• A constructive proof of the Lovasz Local Lemma (arXiv article)
• Hoeffding's inequality for hypergeometric variables (JSTOR article, Section 6 [pp. 28-29])
• Lower bound on the size of the critical giant component (arXiv article, Theorem 2, proved in Section 5)
• Coalescence in continuous time: bound for n particles (book chapter, Section 2, Proposition 5)
• Evolving sets (book chapter, Chapter 17.4 [pp. 235-239])