ICTS

1. Techniques in discrete probability (Elective)

Instructor: Riddhipratim Basu

Venue: Math department LH-5, IISc, Bangalore

Meeting Time: Tuesdays and Thursdays, 2:00-3:30 pm 

First Class: Thursday, 2nd August 2018

Course no: MA 394, 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. The 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 the 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:

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.

The following is the list of courses offered at IISc. For the current list see:

Core Elective Courses

Advanced Elective Courses