CUED Publications database

Relative entropy and exponential deviation bounds for general markov chains

Kontoyiannis, I and Lastras-Montaño, LA and Meyn, SP (2005) Relative entropy and exponential deviation bounds for general markov chains. In: UNSPECIFIED pp. 1563-1567..

Full text not available from this repository.


We develop explicit, general bounds for the probability that the normalized partial sums 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, we obtain a general bound for the important 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. In another direction, motivated by important problems in simulation, we develop a series of bounds in a form which is particularly suited to these problems, and which apply to the more general class of "geometrically ergodic" Markov chains.

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: 27 Oct 2020 07:12
DOI: 10.1109/ISIT.2005.1523607