## Markov chains

 Lecturer: M. Merle Périod: Term 1 ECTS: 6 Hourly Volume: 3 hours per week

This course is an introduction to the general theory of Markov chains on a finite or countable state space. Both discrete and continuous-time settings will be studied.

These objects are perhaps the simplest models for random processes, yet they exhibit a large range of interesting properties, which explains why they are widely used for modelisation purposes.

Markov chains are also used for numerical approximations (MCMC), when trying to estimate a quantity which can be expressed through the equilibrium distribution of such a chain. Interestingly this does not require knowing the equilibrium distribution explicitely : one can simply run copies of the chain for a long enough time.

We will therefore be particularly interested in the long-run behaviour of Markov chains. After discussing invariant measures, ergodic and limit theorems, we should also touch on the concept of mixing times which addresses the question : how many steps does one need to run a Markov chain so that it is close to its equilibrium ?

We will focus some time on the study of reversible chains, for which discrete potential theory, analogous to electrical networks, can be developed.

The lecture will be based on numerous examples, including coupon collector, card shufflings, random walks on several discrete spaces (integer d-dimensional grid, discrete torus, d-dimensional hypercube, regular trees), mean-field interacting particle systems, Poisson processes, branching processes, queues.

Outline

1. Discrete-time chains : construction, transition matrix, communication classes, periodicity.
Recurrence and transience, invariant measures, ergodic theorems, convergence theorem.

2. Potential theory.
Martingales, potentials associated with a chain.
Reversible case : electrical networks analogy.

3. Mixing times. Definition. Upper bounds through coupling. Examples of cutoff phenomenon.
Reversible case : spectral methods.

4. Continuous-time chains
Construction, generator, asymptotic behaviour.
Martingales, examples of convergence towards continuous state space processes.

Bibliography:

- David ALDOUS, James A. FILL Reversible Markov Chains and Random Walks on Graphs, www.stat.berkeley.edu/~aldous/RWG/book.pdf

· Peter DOYLE, SNELL, J. LAURIE Random walks and electric networks, Mathematical Association of America (1984)

· Richard DURRETT Probability : theory and examples, Duxbury Press (1996)

- David A. LEVIN, Yuval PERES, Elisabeth L. WILMER, Markov chains and Mixing Times, www.uoregon.edu/~dlevin/MARKOV/markovmixing.pdf

- Russell LYONS, Yuval PERES, Probability on Trees and Networks, http://mypage.iu.edu/~rdlyons/prbtree/bookcr.pdf

· D.REVUZ Markov chains, North-Holland Publishing Co., Amsterdam (1984)