2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think you mean something other than $\frac{1}{n} \sum_t X_t$. $\endgroup$ Jan 27, 2010 at 13:41

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user2282
    Jan 27, 2010 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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