CUED Publications database

Exponential bounds and stopping rules for MCMC and general Markov chains

Kontoyiannis, I and Lastras-Montão, LA and Meyn, SP (2006) Exponential bounds and stopping rules for MCMC and general Markov chains. In: UNSPECIFIED.

Full text not available from this repository.


We develop explicit, general bounds for the probability that the empirical sample averages of a function of a Markov chain on a general alphabet will exceed the steady-state mean of that function by a given amount. Our bounds combine simple information-theoretic ideas together with techniques from optimization and some fairly elementary tools from analysis. In one direction, motivated by central problems in simulation, we develop bounds for the general class of "geometrically ergodic" Markov chains. These bounds take a form that is particularly suited to simulation problems, and they naturally lead to a new class of sampling criteria. These are illustrated by several examples. In another direction, we obtain a new bound for the important special class of Doeblin chains; this bound is optimal, in the sense that in the special case of independent and identically distributed random variables it essentially reduces to the classical Hoeffding bound. Copyright 2006 ACM.

Item Type: Conference or Workshop Item (UNSPECIFIED)
Divisions: Div F > Signal Processing and Communications
Depositing User: Cron Job
Date Deposited: 08 Jan 2018 20:12
Last Modified: 17 Sep 2020 02:27
DOI: 10.1145/1190095.1190152