Curvature, concentration and error estimates for Markov chain Monte Carlo

Aldéric Joulin, Yann Ollivier

Published 2009-04-08, updated 2010-11-10Version 2

We provide explicit nonasymptotic estimates for the rate of convergence of empirical means of Markov chains, together with a Gaussian or exponential control on the deviations of empirical means. These estimates hold under a "positive curvature" assumption expressing a kind of metric ergodicity, which generalizes the Ricci curvature from differential geometry and, on finite graphs, amounts to contraction under path coupling.