Reading Seminar Series

on

Markov Chains and Mixing Times

Venue: Green Room at Eurandom
15.45  - 17.30 h.

Name                                                     Date                      Title  

ABSTRACTS

I will talk about some topics from chapters 13 and 14, with particular focus on the transportation metric, path coupling, and approximate counting via Markov chains.

I will provide an introduction to the use of Markov chains in simulation known as Markov Chain Monte Carlo (MCMC). This technique is widely used in several research areas, including Statistical Physics and Bayesian statistics.  I will show the Markov chain setting behind the two main forms (the Gibbs sampler and the Metropolis-Hastings sampler) and put these methods in a wider context of simulation techniques. This presentation is partly based on Chapter 3 of the book and partly based introductory articles on MCMC.

Literature:

C. Andrieu, N. De Freitas , A. Doucet, and M.I. Jordan, An Introduction to MCMC for Machine Learning, Machine Learning 50 (2003), 5-43. G. Casella and J. Berger, Explaining the Gibbs Sampler, American Statistician 46 (1992), 167-174.
S. Chib and E. Greenberg, Understanding the Metropolis-Hastings Algorithm, American Statistician 49 (1995), 327-335
P. Diaconis, The Markov Chain Monte Carlo Revolution, Bulletin of the AMS 46 (2009), 179-205
J.S. Liu, Monte Carlo Strategies in Scientific Computing, Springer, 2001.

On this seminar we will explore the connection between mixing properties of Markov chain and spectral structure
of its transition matrix. In particular we will give upper and lower bounds on the mixing time in terms of eigenvalues.
 

In this session of the reading seminar we will discuss a number of stopping times of random walks on general graphs. We review hitting, random target, commute and cover times. We compute them on some simple graphs and in the process highlight the connections between these times.

Alessandro Zocca

In this first meeting we will present some key concepts and tools which will be used during the whole reading seminar, among them the total variation distance and its property, the coupling technique and mixing times. We will then start exploring the deep connections existing between these objects, focusing in particular on the case of Markov chains.

Last updated 24-05-12
Maintained by PK

  P.O. Box 513, 5600 MB  Eindhoven, The Netherlands
tel. +31 40 2478100  fax +31 40 2478190  
  e-mail: info@eurandom.tue.nl