13 Continuous State, Infinite State and Random Environment (June 23, 2001)

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 d¯(t)\bar{d}(t) at (13.6) (and hence for G(t)G(t)at (13.1)). Consider Brownian motions BB^{\circ} on the circle started at 00 and at 1/21/2. At any time tt, the former distribution dominates the latter on the interval (-1/4,1/4)(-1/4,1/4) only, and so

d¯(t)\displaystyle\bar{d}(t) =\displaystyle= P0(Bt(-1/4,1/4))-P1/2(Bt(-1/4,1/4))\displaystyle P_{0}(B^{\circ}_{t}\in(-1/4,1/4))-P_{1/2}(B^{\circ}_{t}\in(-1/4,% 1/4))
=\displaystyle= P0(Bt(-1/4,1/4))-P0(Bt(1/4,3/4))\displaystyle P_{0}(B^{\circ}_{t}\in(-1/4,1/4))-P_{0}(B^{\circ}_{t}\in(1/4,3/4))
=\displaystyle= 2P0(Bt(-1/4,1/4))-1\displaystyle 2P_{0}(B^{\circ}_{t}\in(-1/4,1/4))\ -1
=\displaystyle= 2P((t1/2Z)mod1(-1/4,1/4))-1\displaystyle 2P((t^{1/2}Z)\bmod 1\in(-1/4,1/4))-1

where ZZ has Normal(0,1)(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 (Xt)(X_{t}), described by a stochastic differential equation


where BtB_{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 RRR\to R) to the case μ()=0\mu(\cdot)=0, though for our purposes the standardization to σ()=1\sigma(\cdot)=1 is perhaps more natural. In this case, if the formula


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

(i) For MCMC, to estimate a density f(x)exp(-H(x))f(x)\propto\exp(-H(x)), one can in principle simulate the diffusion with σ(x)=1\sigma(x)=1 and μ(x)=-H(x)/2\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 ZdZ^{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 ZdZ^{d} are studied by Telcs [322, 323].

Section 13.2.9. One view of (Yt)(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 ZdZ^{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 τ0<\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

τ0(n)/τ2(n) is bounded \tau_{0}(n)/\tau_{2}(n)\mbox{ is bounded }

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 nn-cycle

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

(iii) random walk on random nn-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 k5k\geq 5 but our own calculations give only k7k\geq 7. Note that Proposition 13.11 uses the permutation model of a 2k2k-regular random graph. In the alternative uniform model we put 2k2k balls labeled 11, 2k2k balls labeled 22, \ldots\ldots and 2k2k balls labeled nn 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 Ω(1)\Omega(1) and connected with probability 1-o(1)1-o(1) as nn\to\infty for fixed kk. Behavior of τc\tau_{c} in the uniform model is implicitly studied in Bollobás [54]. The L2L^{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 rr-regular graphs. One result is that βmax(λ2,-λn)=O(22r-1r)\beta\equiv\max(\lambda_{2},-\lambda_{n})=O(\frac{2\sqrt{2r-1}}{r}) with probability 1-o(1)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 𝐓n{\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 n3/2n^{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𝝉0()=π/2E\mbox{\boldmath$\tau$}^{(\infty)}_{0}=\sqrt{\pi/2}, as suggested by (13.70);

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

(c) The “cover and return” time Cn+C_{n}^{+} appearing in Chapter 6 satisfies n-3/2ECn+62π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.