An Easy Sanov-Type Theorem for Markov Chains? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T10:14:17Z http://mathoverflow.net/feeds/question/13105 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13105/an-easy-sanov-type-theorem-for-markov-chains An Easy Sanov-Type Theorem for Markov Chains? smalldeviations 2010-01-27T06:03:05Z 2010-02-04T16:23:34Z <p>First, the (simple!) setup:</p> <p>I have a Markov chain X <sub> t </sub> on some finite state space &Omega; with stationary distribution &pi;, and a function f from &Omega; to R. I'd like to estimate the integral of f with respect to &pi;, which I'll write E <sub> &pi; </sub> (f). There are theorems which say that</p> <p>$\frac{1}{n} \Sigma_{t=1}^{n} f(X_{t})$ converges to E <sub> &pi; </sub> (f) as n goes to infinity. </p> <p>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.</p> <p>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?</p> <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/13105/an-easy-sanov-type-theorem-for-markov-chains/13129#13129 Answer by Mark Meckes for An Easy Sanov-Type Theorem for Markov Chains? Mark Meckes 2010-01-27T14:21:10Z 2010-01-27T14:36:59Z <p>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.</p> <p>In any case, to address your concrete question:</p> <blockquote> 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? </blockquote> <p>The answer seems to be yes: try <a href="http://www.i-journals.org/ps/viewarticle.php?id=29&amp;layout=abstract" rel="nofollow">this survey paper</a>.</p> http://mathoverflow.net/questions/13105/an-easy-sanov-type-theorem-for-markov-chains/13229#13229 Answer by Douglas Zare for An Easy Sanov-Type Theorem for Markov Chains? Douglas Zare 2010-01-28T05:49:41Z 2010-01-28T05:49:41Z <p>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 <a href="http://en.wikipedia.org/wiki/Central%5Flimit%5Ftheorem#Under%5Fweak%5Fdependence" rel="nofollow">central limit theorems for weakly dependent sequences</a>, and even versions of the <a href="http://www.jstor.org/pss/3318596" rel="nofollow">Berry-Esseen theorem with weak dependence</a>. </p> <p>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. </p>