Mixing times for Markov chains on graphs

開催日時
2015/01/30 金 15:30 - 17:00
場所
3号館552号室
講演者
Guan-Yu Chen
講演者所属
National Chiao Tung University
概要

The Markov chain Monte Carlo method is a frequently used technique in generating probabilities on graphs and the corresponding mixing time provides important messages to implement the sampling algorithm. From the viewpoint of operator theory and functional analysis, there are several well-developed classical tools ready to investigate the convergence of Markov chains including (local) Poincaré inequality, log-Sobolev inequality, Nash inequality, Cheeger's inequality and many others. Further, the corresponding optimal constants, say the spectral gap and log-Sobolev constant, of the above inequalities are useful in estimating the mixing times.

In this talk, we will quickly review important theoretical results of some above classical tools along with several basic examples that are critical in catching up the heuristics among them. As a precise estimate of the mixing time is mostly unavailable due to the complicated structures of graphs, we will focus on specific chains and provided sharp bounds on mixing times in any meaningful sense.

Keywords: Ergodic Markov chains, mixing times

pdf version