Markov Chains

This is an elective course for second year M. Math students.

The following syllabus (prone to changes and not strictly same as the official syllabus) is only indicative of the topics to be covered. The topics covered so-far in the class have been coloured in green.

Class Timings : Tue : 11.10 - 12.10, 4.45 - 5.45. Wed,Thu : 2 - 3. Venue : Physics Lab. Tuesday afternoon class timings will be decided based on Student colloquium.

Syllabus : Review of Basic probability. Discrete-time, Countable State Markov Chains. Examples, Classification of States, Stationary Distribution. Random walk on Graphs and Groups. Stopping Times, Strong Markov Property. Hitting times. Absorption times. Recurrence and transience. Invariant measures. Convergence to equilibrium. Markov chain mixing, Coupling methods. Lyapunov's function, Foster's theorem and Pakes' Lemma. Absorption and Fundamental matrices. Eigenvalues and Markov chains. Spectral gap bounds, Relaxation time, Dirichlet Form, Bottleneck Ratio.

Possible Additional Topics : Markov Chain Monte-Carlo, Harmonic functions and Martingales, Strong Stationary times, Card-shuffling, Lower bounds. Poisson Processes, Continuous time Markov Chains, Birth-and-death processes.

Prerequisites : Basic probability (For ex., Familiarity with the material in Chapter 1 of Bremaud's book) , analysis, graph theory, matrix theory and a little Measure theory. We shall use a little group theory in some of the examples.

References :

1) Markov Chains and Mixing Times. David A. Levin, Yuval Peres and Elizabeth L. Wilmer.

2) Markov Chains : Gibbs Fields, Monte Carlo Simulation and Queues. Pierre Bremaud.

3) Markov Chains. James R. Norris.

4) Finite Markov Chains and Algorithmic Applications. Olle Haggstrom.

5) Markov Chains Richard Weber.

Assignments : See the attached files below.

Assignment 5 : Exercises from Chapter 5 of Bremaud and exercises given in the class.

Assignment 6 : Exercises from Chapter 12 of Levin-Peres-Wilmer and exercises given in the class.

Grading :

Assignments (to be solved in class) / Presentation : 30.

Mid-semester : 20.

End-semester : 50.

For exam schedule, see here.