13.4 Notes on Chapter 13

Section 13.1. Rigorous setup for discrete-time continuous-space Markov chains is given concisely in Durrett [133] section 5.6 and in detail in Meyn and Tweedie [263]. For the more sophisticated continuous-time setting see e.g. Rogers and Williams [295]. Aldous et al [10] prove some of the Chapter 4 mixing time inequalities in the discrete-time continuous-space setting.

The central limit theorem (for sums of functions of a Markov chain) does not automatically extend from the finite-space setting (Chapter 2 Theorem 17) to the continuous-space setting: regularity conditions are required. See [263] Chapter 17. But a remarkable result of Kipnis - Varadhan [217] shows that for stationary reversible chains the central limit theorem remains true under very weak hypotheses.

Sections 13.1.1 - 13.1.3. The eigenvalue analysis is classical. The reflection coupling goes back to folklore; see e.g. Lindvall [234] Chapter 6 for applications to multidimensional diffusions and Matthews [259] for Brownian motion in a polyhedron. Burdzy and Kendall [82] give a careful study of coupling for Brownian motion in a triangle. Chen [89] surveys use of coupling to estimate spectral gaps for diffusions on manifolds.

Here is a more concise though less explicit expression for $\bar{d}(t)$ at (13.6) (and hence for $G(t)$at (13.1)). Consider Brownian motions $B^{\circ}$ on the circle started at $0$ and at $1/2$. At any time $t$, the former distribution dominates the latter on the interval $(-1/4,1/4)$ only, and so

where $Z$ has Normal$(0,1)$ law. We quoted this expression in the analysis of Chapter 5 Example 7

Section 13.1.5. Janvresse [195], Porod [285] and Rosenthal [298] study mixing times for other flights on matrix groups involving rotations and reflections; Porod [284] also discusses more general Lie groups.

Section 13.1.6. The mathematical theory has mostly been developed for classes of nested fractals, of which the Sierpinski gasket is the simplest. See Barlow [40], Lindstrøm [233], Barlow [41] for successively more detailed treatments. Closely related is Brownian motion on the continuum random tree, mentioned in section 13.3.4.

One-dimensional diffusions. The continuous-space analog of a birth-and-death process is a one-dimensional diffusion $(X_{t})$, described by a stochastic differential equation

where $B_{t}$ is standard Brownian motion and $\mu(\cdot)$ and $\sigma(\cdot)$ are suitably regular specified functions. See Karlin and Taylor [209] for non-technical introduction. Theoretical treatments standardize (via a one-to-one transformation $R\to R$) to the case $\mu(\cdot)=0$, though for our purposes the standardization to $\sigma(\cdot)=1$ is perhaps more natural. In this case, if the formula

can give a density function $f(x)$ then $f$ is the stationary density. Such diffusions relate to two of our topics.

(i) For MCMC, to estimate a density $f(x)\propto\exp(-H(x))$, one can in principle simulate the diffusion with $\sigma(x)=1$ and $\mu(x)=-H^{\prime}(x)/2$. This idea was used in Chapter MCMC section 5.

(ii) Techniques for bounding the relaxation time for one-dimensional diffusions parallel techniques for birth-and-death chains [90].

Section 13.2. We again refer to Woess [339] for systematic treatment of random walks on infinite graphs.

Our general theme of using the infinite case to obtain limits for finite chains goes back at least to [14], in the case of $Z^{d}$; similar ideas occur in the study of interacting particle systems, relating properties of finite and infinite-site models.

Section 13.2.2. There is a remarkable connection between recurrence of reversible chains and a topic in Bayesian statistics: see Eaton [138]. Properties of random walk on fractal-like infinite subsets of $Z^{d}$ are studied by Telcs [322, 323].

Section 13.2.9. One view of $(Y_{t})$ is as one of several “toy models” for the notion of random walk on fractional-dimensional lattice. Also, when we seek to study complicated variations of random walk, it is often simpler to use the hierarchical lattice than $Z^{d}$ itself. See for instance the sophisticated study of self-avoiding walks by Brydges et al [76]; it would be interesting to see whether direct combinatorial methods could reproduce their results.

Section 13.2.10. Another class of sequences could be defined as follows. There are certain continuous-time, continuous-space reversible processes on compact spaces which “hit points” and for which $\tau_{0}<\infty$; for example

(i) Brownian motion on the circle (section 13.1.1)

(ii) Brownian motion on certain fractals (section 13.1.6)

(iii) Brownian motion on the continuum random tree (section 13.3.4).

So for a sequence of finite-state chains one can define the property

as the finite analog of “diffusions which hit points”. This property holds for the discrete approximations to the examples above: (i) random walk on the $n$-cycle

(i) random walk on graphs approximating fractals (section 13.1.6)

(iii) random walk on random $n$-vertex trees (section 13.3.4).

Equivalence (13.58) is hard to find in textbooks. The property “trivial boundary” is equivalent to “no non-constant bounded harmonic functions” ([339] Corollary 24.13), which is equivalent ([328] Theorem 6.5.1) to existence of successful shift-coupling of two versions of the chain started at arbitrary points. The property (13.58) is equivalent ([328] Theorem 4.9.4) to existence of successful couplings. In the setting of interest to us (continuized chains on countable space), existence of a shift-coupling (a priori weaker than existence of a coupling) for the discrete-time chain implies existence of a coupling for the continuous-time chain, by using independence of jump chain and hold times.

Section 13.3. Grimmett [177] surveys “random graphical networks” from a somewhat different viewpoint, emphasising connections with statistical physics models.

Section 13.3.1. More precise variants of Proposition 3.35 were developed in the 1970s, e.g. [281, 94]. Lubotzky [243], who attributes this method of proof of Proposition 13.11 to Sarnak [305], asserts the result for $k\geq 5$ but our own calculations give only $k\geq 7$. Note that Proposition 13.11 uses the permutation model of a $2k$-regular random graph. In the alternative uniform model we put $2k$ balls labeled $1$, $2k$ balls labeled $2$, $\ldots\ldots$ and $2k$ balls labeled $n$ into a box; then draw without replacement two balls at a time, and put an edge between the two vertices. In both models the graphs may be improper (multiple edges or self-loops) and unconnected, but are in fact proper with probability $\Omega(1)$ and connected with probability $1-o(1)$ as $n\to\infty$ for fixed $k$. Behavior of $\tau_{c}$ in the uniform model is implicitly studied in Bollobás [54]. The $L^{2}$ ideas underlying the proof of Proposition 13.12 were used by Broder and Shamir [66], Friedman [156] and Kahn and Szemerédi [155] in the setting of the permutation model of random $r$-regular graphs. One result is that $\beta\equiv\max(\lambda_{2},-\lambda_{n})=O(\frac{2\sqrt{2r-1}}{r})$ with probability $1-o(1)$. Further results in the “random Cayley graph” spirit of Proposition 13.12 can be found in [27, 130, 271].

Section 13.3.2. The monograph of Lyons and Peres [249] contains many more results concerning random walks on infinite deterministic and Galton–Watson trees. A challenging open problem noted in [247] is to prove that ${\bf R}$ has absolutely continuous distribution when $\xi$ is non-constant. The method of fictitious roots used in Proposition 13.14 is also an ingredient in the analysis of cover times on trees [21].

Section 13.3.4. Moon [264] gives further results in the spirit of (13.70), e.g. for variances of hitting times. The fact that random walk on ${\bf T}_{n}$ rescales to Brownian motion on a “continuum random tree” ${\bf T}_{\infty}$ was outlined in Aldous [22] section 5 and proved in Krebs [218]. While this makes the “order $n^{3/2}$” property (13.71) of the parameters essentially obvious, it is still difficult to get explicit information about the limit distributions $\mbox{\boldmath$\tau$}^{(\infty)}$. What’s known [22] is

(a) $E\mbox{\boldmath$\tau$}^{(\infty)}_{0}=\sqrt{\pi/2}$, as suggested by (13.70);

(b) $\mbox{\boldmath$\tau$}^{(\infty)*}=\frac{8}{3}\sqrt{2\pi}$, from (13.69) and the known asymptotics for the diameter of ${\bf T}_{n}$;

(c) The “cover and return” time $C_{n}^{+}$ appearing in Chapter 6 satisfies $n^{-3/2}EC_{n}^{+}\to 6\sqrt{2\pi}$, modulo some technical issues.

Section 13.3.5. Grimmett and Kesten [175] present their results in terms of resistances, without explicitly mentioning random walk, so that results like (13.73) are only implicit in their work.