Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

In any case, to address your concrete question:

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?

The answer seems to be yes: try this survey paper.

share|improve this answer
    
Thank you Mark - both of your comments were correct, and the question has been fixed. As I deserve from my poor question, that survey seems to give existence of a CLT, but minimal hints of the variance or error terms. Currently reading some of the follow-ups in the bibliography. –  user2282 Jan 27 '10 at 23:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.