MA 394: Techniques in discrete probability

Credits: 3:0

Pre-requisites :

1. This course is aimed at Ph.D. students from different fields who expect to use discrete probability in their research. Graduate level measure theoretic probability will be useful, but not a requirement. I expect the course will be accessible to advanced undergraduates who have had sufficient exposure to probability.

We shall illustrate some important techniques in studying discrete random structures through a number of examples. The techniques we shall focus on will include (if time permits)

1. the probabilistic method;
2. first and second moment methods, martingale techniques for concentration inequalities;
3. coupling techniques, monotone coupling and censoring techniques;
4. correlation inequalities, FKG and BK inequalities;
5. isoperimetric inequalities, spectral gap, Poincare inequality;
6. Fourier analysis on hypercube, Hypercontractivity, noise sensitivity and sharp threshold phenomenon;
7. Stein’s method;
8. entropy and information theoretic techniques.

We shall discuss applications of these techniques in various fields such as Markov chains, percolation, interacting particle systems and random graphs.

Suggested books and references:

1. Noga Alon and Joel Spencer, The Probabilistic Method, Wiley, 2008.
2. Geoffrey Grimmett, Probability on Graphs, Cambridge University Press, 2010.
3. Ryan O'Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014.

All Courses