4.7 Notes on Chapter 4

Section 4.3.1. The definition of $\tau^{(2)}_{1}$ involves the idea of a stopping time $U$ such that $X_{U}$ has distribution $\pi$ and is independent of the starting position. This idea is central to the standard modern theory of Harris-recurrent Markov chains, i.e. chains on continuous space which mimic the asymptotic behavior of discrete recurrent chains, and does not require reversibility. See [133] sec. 5.6 for an introduction, and [35, 263] for more comprehensive treatments. In that field, researchers have usually been content to obtain some finite bound on $EU$, and haven’t faced up to our issue of the quantitative dependence of the bound on the underlying chain.

Separation and strong stationary times were introduced in Aldous and Diaconis [8], who gave some basic theory. These constructions can be used to bound convergence times in examples, but in practice are used in examples with much special structure, e.g. non-necessarily-symmetric random walks on groups. Examples can be found in [7, 8] and Matthews [256]. Development of theory, mostly for stochastically monotone chains on $1$-dimensional state space, is in Diaconis and Fill [112, 113], Fill [150, 151] and Matthews [260].

The recurrent balayage theorem (Chapter 1 yyy) can be combined with the mean hitting time formula to get

Curiously, this elegant result doesn’t seem to help much with the inequalities in Theorem 4.6.

What happens with the $\tau_{1}$-family of parameters for general chains remains rather obscure. Some counter-examples to equivalence, and weaker inequalities containing $\log 1/\pi_{*}$ factors, can be found in [12]. Recently, Lovasz and Winkler [240] initiated a detailed study of $\tau_{1}^{(2)}$ for general chains which promises to shed more light on this question.

Our choice of $\tau_{1}$ as the “representative” of the family of $\tau_{1}^{(i)}$’s is somewhat arbitrary. One motivation was that it gives the constant “1” in the inequality $\tau_{2}\leq\tau_{1}$. It would be interesting to know whether the constants in other basic inequalities relating the $\tau_{1}$-family to other parameters could be made “1”:

Much of recent sophisticated theory xxx refs bounds $d(t)$ by bounding $\hat{d}(t)$ and appealing to Lemma 4.7(b). But it is not clear whether there is an analog of Theorem 4.6 relating the $\hat{d}$-threshold to other quantities.

Section 4.3.2. The parts of Theorem 4.6 involving $\tau_{1}^{(1)}$ and $\tau_{1}^{(3)}$ are implicit rather than explicit in [12]. That paper had an unnecessarily complicated proof of Lemma 4.13. The proof of (4.15) in [12] gives a constant $K\approx e^{13}$. It would be interesting to obtain a smaller constant! Failing this, a small constant in the inequality $\tau_{1}^{(1)}\leq K\tau_{1}^{(3)}$ would be desirable. As a weaker result, it is easy to show

which has some relevance to later examples (yyy).

Section 4.3.3. The analog of Open Problem 4.17 in which we measure distance from stationarity by $\hat{d}$ instead of $d(t)$ is straightforward, using the “CM proxy” property of discrete time chains:

Open Problem 4.17 itself seems deeper, though the weaker form in which we require only that $\phi(t)=O(t)$ can probably be proved by translating the proof of (4.15) into discrete time and using the CM proxy property.

Section 4.3.4. The cat-and-mouse game was treated briefly in Aleliunas et al [25], who gave a bare-hands proof of a result like (4.21). Variations in which the cat is also allowed an arbitrary strategy have been called “princess and monster” games – see Isaacs [190] for results in a different setting.

Section 4.3.5. Sinclair [307] points out that “hard” results of Leighton and Rao [224] on multicommodity flow imply

This follows from Corollary 4.22 and Lemma 4.23 when $\pi$ is uniform, but Sinclair posed

Section 4.4. As an example of historical interest, before this topic became popular Fiedler [147] proved

This upper bound is sharp. On the other hand, Proposition 4.2 gave the same upper bound (up to the numerical constant) for the a priori larger quantity $\tau^{*}$, and so is essentially a stronger result.

Section 4.4.1. In the non-reversible case the definition of the maximal correlation $\rho(t)$ makes sense, and there is similar asymptotic behavior:

where $\lambda$ is the “spectral gap”. But we cannot pull back from asymptotia to the real world so easily: it is not true that $\rho(t)$ can be bounded by $K\exp(-\lambda t)$ for universal $K$. A dramatic example from Aldous [17] section 4 has for each $n$ an $n$-state chain with spectral gap bounded away from $0$ but with $\rho(n)$ also bounded away from $0$, instead of being exponentially small. So implicit claims in the literature that estimates of the spectral gap for general chains have implications for finite-time behavior should be treated with extreme skepticism.

It is not surprising that the classical Berry-Esseen Theorem for i.i.d. sums ([133] Thm. 2.4.10) has an analog for chains. Write $\sigma^{2}$ for the asymptotic variance rate in Proposition 4.29 and write $Z$ for a standard Normal r.v.

This result is usually stated for infinite-state chains satisfying various mixing conditions, which are automatically satisfied by finite chains. See e.g. Bolthausen [55]. At first sight the constant $K$ depends on the function $g$ as well as the chain, but a finiteness argument shows that the dependence on $g$ can be removed. Unfortunately the usual proofs don’t give any useful indications of how $K$ depends on the chain, and so don’t help with Open Problem 4.30.

The variance results in Proposition 4.29 are presumably classical, being straightforward consequences of the spectral representation. Their use in algorithmic settings such as Corollary 4.31 goes back at least to [16].

Section 4.4.3. Systematic study of the optimal choice of weights in the Cauchy-Schwarz argument for Theorem 4.32 may lead to improved bounds in examples. Alan Sokal has unpublished notes on this subject.

Section 4.5.1. The quantity $1/\tau_{c}$, or rather this quantity with the alternate definition of $\tau_{c}$ mentioned in the text, has been called conductance. I avoid that term, which invites unnecessary confusion with the electrical network terminology. However, the subscript $c$ can be regarded as standing for “Cheeger” or “conductance”.

In connection with Open Problem 4.38 we mention the following result. Suppose that in the definition (section 4.4.1) of the maximal correlation function $\rho(t)$ we considered only events, i.e. suppose we defined

Then $\tilde{\rho}(t)\leq\rho(t)$, but in fact the two definitions are equivalent in the sense that there is a universal function $\psi(x)\downarrow 0$ as $x\downarrow 0$ such that $\rho(t)\leq\psi(\tilde{\rho}(t))$. This is a result about “measures of dependence” which has nothing to do with Markovianness – see e.g. Bradley et al [59].

Section 4.5.2. The history of Cheeger-type inequalities up to 1987 is discussed in [223] section 6. Briefly, Cheeger [87] proved a lower bound for the eigenvalues of the Laplacian on a compact Riemannian manifold, and this idea was subsequently adapted to different settings – in particular, by Alon [29] to the relationship between eigenvalues and expansion properties of graphs. Lawler and Sokal [223], and independently Jerrum and Sinclair [309], were the first to discuss the relationship between $\tau_{c}$ and $\tau_{2}$ at the level of reversible Markov chains. Their work was modified by Diaconis and Stroock [122], whose proof we followed for Lemmas 4.39 and 4.41. The only novelty in my presentation is talking explicitly about quasistationary distributions, which makes the relationships easier to follow.

xxx give forward pointer to results of [238, 158].

Section 4.6.2. See Efron-Stein [140] for the origin of their inequality. Inequality (4.45), or rather the variant mentioned above Corollary 4.47 involving the $2n$ i.i.d. variables