# An Easy Sanov-Type Theorem for Markov Chains?

First, the (simple!) setup:

I have a Markov chain X t on some finite state space Ω with stationary distribution π, and a function f from Ω to R. I'd like to estimate the integral of f with respect to π, which I'll write E π (f). There are theorems which say that

$\frac{1}{n} \Sigma_{t=1}^{n} f(X_{t})$ converges to E π (f) as n goes to infinity.

Now, if the $X_{t}$ were iid, then the Berry-Esseen theorem would give error rates in terms of n and (say) the maximum value of f.

Are there similar theorems which give error rates in terms of n, the maximum value of f, and one (or several) of the frequently computed statistics of finite state Markov chains, like relaxation time, mixing time, covering time, etc?

I'm vaguely aware of Sanov-type theorems for Markov chains, which give large-deviation results, but not in terms of these sorts of quantities, and I don't see how to convert the bounds immediately. Alternatively, I'd be very happy if anyone can give a reference for places that people have actually computed the sorts of error terms that do show up in statements of Sanov's theorem for some simple random walks.

EDIT: Added Mark's comments, so that the question might actually make some sense now. In particular, fixed a missing f, and the rather more important mistake that in fact the CLT doesn't give any sort of quantitative bounds by itself.

FURTHER EDIT: I accepted D. Zare's answer, since it certainly works. If anybody is interested in this question, I have since seen a bunch of articles, the latest of which is 'Optimal Hoeffding Bounds for Discrete Reversible Markov Chains' by C. Leon, which are a bit more specialized to the Markov chain case. I have also been told that Brad Mann's thesis is worth reading on the subject, but haven't yet picked up a copy myself.

• I think you mean something other than $\frac{1}{n} \sum_t X_t$. – Steve Huntsman Jan 27 '10 at 13:41

The sequence of states of a Markov chain with a finite state space is a good example of a sequence of weakly dependent random variables. A convolution like a moving average is another. There are plenty of versions of central limit theorems for weakly dependent sequences, and even versions of the Berry-Esseen theorem with weak dependence.

The variance of the sum picks up some covariance terms (the cross terms of the second moment don't vanish, although they can be estimated in terms of the mixing time and $f_{max} - f_{min}$), and the Berry-Esseen-like bounds get a little worse.

I assume you meant $\frac{1}{n}\sum_{t=1}^n f(X_t)$ converges to $\mathrm{E}_\pi (f)$. I'll also quibble and point out that the (classical) CLT doesn't give error rates in terms of n, but the Berry-Esseen theorem does.