Course data

Meetings: Fridays 10–12 during spring 2013 at Room MaD380

Instructor: Lasse Leskelä

Course data in Korppi: https://korppi.jyu.fi/kotka/r.jsp?course=149359

Description

This reading seminar introduces its participants to the modern approach of the theory of Markov chains. The main goal is to determine the rate of convergence of a Markov chain to its equilibrium distribution as a function of the size and geometry of the state space. We will learn methods of estimating hitting times, cover times, and convergence speeds using probabilistic coupling techniques and spectral methods. During the seminar, we will go through most parts of the book:

David A. Levin, Yuval Peres, Elizabeth L. Wilmer.
Markov Chains and Mixing Times.
American Mathematical Society 2008.
The seminar kick-off meeting takes place on 1 Feb 2013 10:15 at Room MaD380.

Schedule

  1. Fri 1 Feb.
    • Seminar kick-off.
    • Lasse Leskelä: Introduction to Markov chain mixing and coupling (Chapters 4 and 5)
  2. Fri 8 Feb.
    • Harri Varpanen: Strong stationary times (Chapter 6)

    3. There will be no meeting on Fri 15 Feb.


  3. Fri 22 Feb.
    • Pekka Aalto: Lower bounds on mixing times (Chapter 7)
  4. Fri 1 Mar.
    • Joonas Heino: Random walks on networks (Chapter 9)

    5. There will be no meeting on Fri 8 Mar.


  5. Fri 15 Mar.
    • Hans Hartikainen: Hitting times (Chapter 10)
  6. Fri 22 Mar.
    • Mikko Kuronen: Martingales (Chapter 17)
  7. Fri 5 Apr.
    • Aleksi Koskikallio: Cover times (Chapter 11)
  8. Fri 12 Apr.
    • Matti Vihola: Eigenvalues (Chapter 12)
  9. Fri 19 Apr.
    • Harri Varpanen: The cutoff phenomenon (Chapter 18)
  10. Fri 26 Apr.
    • Mikko Kuronen: Countable state space chains (Chapter 21)

    11. There will be no meeting on Fri 3 May.


  11. Fri 10 May.
    • Antti Luoto: Simulated annealing

Language

The language of the course will be English or Finnish, depending on preferences of the participants.

Evaluation

Participants may earn 1–3 credit points from the seminar. Active participation to one meeting is worth 1/6 credit points and presenting a book chapter is worth 3/4 credit points.

Prerequisites

Basic familiarity with finite Markov chains on the level of MATS255 Markov processes is highly recommended.