# Stopping rules for Markov Chains

The following is a quote from Lifting Markov Chains to Speed up Mixing, by Chen, Lovasz, and Pak:

...Thus we have described a (randomized) stopping rule that, for any starting node, stops in an expected number $O(\sqrt{n})$ steps, and the probability of stopping at each node is at least 1/2 its stationary probability. By standard results (see e.g. [9]), this implies that the mixing time is $O(\sqrt{n})$.

My question: I would like a precise reference for this fact, especially one which has a proof I can read. The reference [9] is Mixing Times by Lovasz and Winkler, and I was unable to find this statement in there.

Moreover, there is some ambiguity of what a mixing time of means; what I want it to mean in this case is that except from the eigenvalue at $1$, every other eigenvalue of the chain has modulus at most $1-c/\sqrt{n}$ for some constant $c>0$.

Can someone provide a precise reference?

-

## 2 Answers

The condition means that the separation distance is smaller than 1/2. The conclusion depends on the definition of the mixing time. For example, if the mixing time is the expected time for the optimal strong uniform stopping rule (as e.g. in my thesis), then this holds. If the mixing time is the convergence in $\ell_\infty$ distance, then this is "almost true", up to a log factor. The Lovasz-Winkler paper we mentioned proves several equivalent (and non-equivalent) definitions of mixing times which the reader might find useful. For classical results on the separation distance, see this paper by Aldous and Diaconis.

-

We know that (on page 12) the mixing time is $$\mathcal{H} = \max_{i} \ \max_{j}(H(i,j)-H(\pi,j))$$

It seems that $H(i,j) = O(\sqrt{n})$.

-
PEV: I would appreciate if you could make precise the ways in which your post is relevant to the question asked. –  Did May 28 '11 at 10:05