CURVATURE, CONCENTRATION AND ERROR ESTIMATES FOR MARKOV CHAIN MONTE CARLO

• 成果类型: Article
• 署名作者: Joulin, Alderic; Ollivier, Yann
• 署名单位: Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National des Sciences Appliquees de Toulouse; Ecole Normale Superieure de Lyon (ENS de LYON)
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/10-AOP541
• 发表日期: 2010
• 页码: 2418-2442
• 关键词: information inequalities; deviation inequality; CONVERGENCE

摘要

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.