13.2 Infinite graphs

We assume the reader has some acquaintance with classical theory (e.g., [133] Chapter 5) for a countable-state irreducible Markov chain, which emphasizes the trichotomy transient or null-recurrent or positive-recurrent. We use the phrase general chain to refer to the case of an arbitrary irreducible transition matrix ${\bf P}$, without any reversibility assumption.

Recall from Chapter 3 section 2 the identification, in the finite-state setting, of reversible chains and random walks on weighted graphs. Given a reversible chain we defined edge-weights $w_{ij}=\pi_{i}p_{ij}=\pi_{j}p_{ji}$; conversely, given edge-weights we defined random walk as the reversible chain

$$p_{vx}=w_{vx}/w_{v};\ w_{v}=\sum_{x}w_{vx}.$$

(13.19)

In the infinite setting it is convenient (for reasons explained below) to take the “weighted graph” viewpoint. Thus the setting of this section is that we are given a connected weighted graph satisfying

$$w_{v}\equiv\sum_{x}w_{vx}<\infty\ \forall x,\ \ \ \sum_{v}w_{v}=\infty$$

(13.20)

and we study the associated random walk $(X_{t})$, i.e., the discrete-time chain with $p_{vx}=w_{vx}/w_{v}$. So in the unweighted setting ($w_{e}\equiv 1$), we have nearest-neighbor random walk on a locally finite, infinite graph.

To explain why we adopt this set-up, say $\pi$ is invariant for ${\bf P}$ if

$$\sum_{i}\pi_{i}p_{ij}=\pi_{j}\ \forall j;\ \ \pi_{j}>0\ \forall j.$$

Consider asymmetric random walk on $Z$, say

$$p_{i,i+1}=2/3,\ p_{i,i-1}=1/3;\ -\infty<i<\infty.$$

(13.21)

One easily verifies that each of the two measures $\pi_{i}=1$ and $\pi_{i}=2^{i}$ is invariant. Such nonuniqueness makes it awkward to seek to define reversibility of ${\bf P}$ via the detailed balance equations

$$\pi_{i}p_{ij}=\pi_{j}p_{ji}\ \forall i,j$$

(13.22)

without a prior definition of $\pi$. Stating definitions via weighted graphs avoids this difficulty.

The second assumption in (13.20), that $\sum_{v}w_{v}=\infty$, excludes the positive-recurrent case (see Theorem 13.4 below); because in that case the questions one asks, such as whether the relaxation time $\tau_{2}$ is finite, can be analyzed by the same techniques as in the finite-state setting.

Our intuitive interpretation of “reversible” in Chapter 3 was “a movie of the chain looks the same run forwards or run backwards”. But the chain corresponding to the weighted graph with weights $w_{i,i+1}=2^{i}$, which is the chain (13.21) with $\pi_{i}=2^{i}$, has a particle moving towards $+\infty$ and so certainly doesn’t satisfy this intuitive notion. On the other hand, a probabilistic interpretation of an infinite invariant measure $\pi$ is that if we start at time $0$ with independent Poisson($\pi_{v}$) numbers of particles at vertices $v$, and let the particles move independently according to ${\bf P}$, then the particle process is stationary in time. So the detailed balance equations (13.22) correspond to the intuitive “movie” notion of reversible for the infinite particle process, rather than for a single chain.

The next Theorem summarizes parts of the standard theory of general chains (e.g., [133] Chapter 5). Write $\rho_{v}:=P_{v}(T^{+}_{v}<\infty)$ and let $N_{v}(\infty)$ be the total number of visits (including time 0) to $v$.

Specializing to random walk on a weighted graph, the measure $(w_{v})$ is invariant, and the second assumption in (13.20) implies that the walk cannot be positive-recurrent. By a natural abuse of language we call the weighted graph recurrent or transient. Because $E_{v}N_{v}(\infty)=\sum_{t}p^{(t)}_{vv}$, Theorem 13.4 contains the “classical” method to establish transience or recurrence by considering the $t\rightarrow\infty$ behavior of $p^{(t)}_{vv}$. This method works easily for random walk on $Z^{d}$ (section 13.2.4).

Some of the “electrical network” story from Chapter 3 extends immediately to the infinite setting. Recall the notion of a flow ${\bf f}$, and the net flow $f_{(x)}$ out of a vertex $x$. Say ${\bf f}$ is a unit flow from $x$ to infinity if $f_{(x)}=1$ and $f_{(v)}=0\ \forall v\neq x$. Thompson’s principle (Chapter 3 Proposition 35) extends to the infinite setting, by considering subsets $A_{n}\downarrow\phi$ (the empty set) with $A_{n}^{c}$ finite.

By analogy with the finite setting, we can regard the inf as the effective resistance between $v$ and infinity, although (see section LABEL:IEN) we shall not attempt an axiomatic treatment of infinite electrical networks.

Theorem 13.5 has the following immediate corollary: of course (a) and (b) are logically equivalent.

Thus the classical fact that $Z^{2}$ is recurrent implies that a subgraph of $Z^{2}$ is recurrent, a fact which is hard to prove by bounding $t$-step transition probabilities. In the other direction, it is possible (but not trivial) to prove that $Z^{3}$ is transient by exhibiting a flow: indeed Doyle and Snell [131] construct a transient tree-like subgraph of $Z^{3}$.

Here is a different formulation of the same idea.

Recall the mean hitting time parameter $\tau_{0}$ from Chapter 4. For a sequence of $n$-state reversible chains, consider the property

$$n^{-1}\tau_{0}(n)\mbox{ is bounded as }n\rightarrow\infty.$$

(13.23)

We assert, as a conceptual paradigm, that property (13.23) is the analog of the “transient” property for a single infinite-state chain. The connection is easy to see algebraically for symmetric chains (Chapter 7), where $\tau_{0}=E_{\pi}T_{v}$ for each $v$, so that by Chapter 2 Lemma 10

$$n^{-1}\tau_{0}=z_{vv}=\sum_{t=0}^{\infty}(p_{v}v^{(t)}-n^{-1}).$$

The boundedness (in $n$) of this sum is a natural analog of the transience condition

$$\sum_{t=0}^{\infty}p_{vv}^{(t)}<\infty$$

for a single infinite-state chain. So in principle the methods used to determine transience or recurrence in the infinite-state case ([339] Chapter 1) should be usable to determine whether property (13.23) holds for finite families, and indeed Proposition 37 of Chapter 3 provides a tool for this purpose. In practice these extremal methods haven’t yet proved very successful; early papers [85] proved (13.23) for expanders in this way, but other methods are easier (see our proof of Chapter 9 Theorem 1). There is well-developed theory ([339] section 6) which establishes recurrence for infinite planar graphs under mild assumptions. It is natural to conjecture that under similar assumptions, a planar $n$-vertex graph has $\tau_{0}=\Theta(n\log n)$, as in the case of $Z^{2}$ in Proposition 13.8 below.

We consider the lattice $Z^{d}$ as an infinite $2d$-regular unweighted graph. Write $X_{t}$ for simple random walk on $Z^{d}$, and write $\widetilde{X}_{t}$ for the continuized random walk. Of course, general random flights (i.e. “random walks”, in everyone’s terminology except ours) and their numerous variations comprise a well-studied classical topic in probability theory. See Hughes [184] for a wide-ranging intermediate-level treatment, emphasizing physics applications. Our discussion here is very narrow, relating to topics treated elsewhere in this book.

To start some calculations, for $d=1$ consider

	$\displaystyle\tilde{p}(t)$	$\displaystyle\equiv$	$\displaystyle P_{0}(\widetilde{X}_{t}=0)$
		$\displaystyle=$	$J^{+}_{t}$
			independent Poisson$(t/2)$ numbers of $+1$ and $-1$ jumps
		$\displaystyle=$	$\displaystyle\sum_{n=0}^{\infty}\left(\frac{e^{-t/2}(t/2)^{n}}{n!}\right)^{2}$
		$\displaystyle=$	$\displaystyle e^{-t}I_{0}(t)$

where $I_{0}(t):=\sum_{n=0}^{\infty}\frac{(t/2)^{2n}}{(n!)^{2}}$ is the modified Bessel function of the first kind of order $0$. Now ${\rm var}\ \widetilde{X}_{t}=t$, and as a consequence of the local CLT (or by quoting asymptotics of the Bessel function $I_{0}$) we have

$$\tilde{p}(t)\sim(2\pi t)^{-1/2}\mbox{ as }t\rightarrow\infty.$$

(13.24)

As discussed in Chapter 4 section 6.2 and Chapter 5 Example 17, a great advantage of working in continuous time in dimensions $d\geq 2$ is that the coordinate processes are independent copies of slowed-down one-dimensional processes, so that $\tilde{p}^{(d)}(t)\equiv P_{0}(\widetilde{X}_{t}=0)$ in dimension $d$ satisfies

$$\tilde{p}^{(d)}(t)=(\tilde{p}(t/d))^{d}=e^{-t}(I_{0}(t/d))^{d}.$$

(13.25)

In particular, from (13.24),

$$\tilde{p}^{(d)}(t)\sim({\textstyle\frac{d}{2\pi}})^{d/2}t^{-d/2}\mbox{ as }t\rightarrow\infty.$$

(13.26)

One can do a similar analysis in the discrete time case. In dimension $d=1$,

	$\displaystyle p(t)$	$\displaystyle\equiv$	$\displaystyle P_{0}(X_{t}=0)$		(13.27)
		$\displaystyle=$	$\displaystyle 2^{-t}{t\choose t/2}\ ,t\mbox{ even }$
		$\displaystyle\sim$	$t$

This agrees with (13.26) but with an extra “artificial” factor of $2$ arising from periodicity. A more tedious argument gives the analog of (13.26) in discrete time for general $d$:

$$t$$

(13.28)

From the viewpoint of classical probability, one can regard (13.26,13.28) as the special case $j=0$ of the local CLT: in continuous time in dimension $d$,

$$\sup_{j}\left|P_{0}(\widetilde{X}_{t}=j)-({\textstyle\frac{d}{2\pi}})^{d/2}t^{-d/2}\exp(-d|j|^{2}/(2t))\right|=o(t^{-d/2})\mbox{ as }t\rightarrow\infty$$

where $|j|$ denotes Euclidean norm.

The occupation time $N_{0}(t)$ satisfies $E_{0}N_{0}(t)=\int_{0}^{t}\tilde{p}(s)\ ds$ (continuous time) and $=\sum_{s=0}^{t-1}p(s)$ (discrete time). In either case, as $t\rightarrow\infty$,

	$\displaystyle(d=1)\ \ E_{0}N_{0}(t)$	$\displaystyle\sim$	$\displaystyle\sqrt{{\textstyle\frac{2}{\pi}}}\ t^{1/2}$		(13.29)
	$\displaystyle(d=2)\ \ E_{0}N_{0}(t)$	$\displaystyle\sim$	$\displaystyle{\textstyle\frac{1}{\pi}}\log t$		(13.30)
	$\displaystyle(d\geq 3)\ \ E_{0}N_{0}(t)$	$\displaystyle\rightarrow$	$\displaystyle R_{d}\equiv\int_{0}^{\infty}\tilde{p}^{(d)}(t)dt$		(13.31)
			$\displaystyle=\int_{0}^{\infty}e^{-t}(I_{0}(t/d))^{d}\ dt$

where $R_{d}<\infty$ for $d\geq 3$ by (13.26). This is the classical argument for establishing transience in $d\geq 3$ and recurrence in $d\leq 2$, by applying Theorem 13.4. Note that the return probability $\rho^{(d)}:=P_{0}(T^{+}_{0}<\infty)$ is related to $E_{0}N_{0}(\infty)$ by $E_{0}N_{0}(\infty)=\frac{1}{1-\rho^{(d)}}$; in other words

$$\rho^{(d)}=\frac{R_{d}-1}{R_{d}},\ d\geq 3.$$

Textbooks sometimes give the impression that calculating $\rho^{(d)}$ is hard, but one can just calculate numerically the integral (13.31). Or see [174] for a table.

The quantity $\rho^{(d)}$ has the following sample path interpretation. Let $V_{t}$ be the number of distinct vertices visited by the walk before time $t$. Then

$$t^{-1}V_{t}\rightarrow 1-\rho^{(d)}\mbox{ a.s. },\ d\geq 3.$$

(13.32)

The proof of this result is a textbook application of the ergodic theorem for stationary processes: see [133] Theorem 6.3.1.

We now discuss how random walk on $Z^{d}$ relates to $m\rightarrow\infty$ asymptotics for random walk on the finite torus $Z^{d}_{m}$, discussed in Chapter 5. We now use superscript $\cdot^{(m)}$ to denote the length parameter. From Chapter 5 Example 17 we have

$$\tau_{2}^{(m)}=\frac{d}{1-\cos(2\pi/m)}\sim\frac{dm^{2}}{2\pi^{2}}$$

$$\tau_{1}^{(m)}=\Theta(m^{2})$$

(13.33)

where asymptotics are as $m\rightarrow\infty$ for fixed $d$. One can interpret this as a consequence of the $dN^{2}$ time rescaling in the wweak convergence of rescaled random walk to Brownian motion of the $d$-dimensional torus, for which (cf. sections 13.1.1 and 13.1.2) $\tau_{2}=2\pi^{-2}$. At (74)–(75) of Chapter 5 we saw that the eigentime identity gave an exact formula for the mean hitting time parameter $\tau_{0}^{(m)}$, whose asymptotics are, for $d\geq 3$,

$$m^{-d}\tau_{0}^{(m)}\rightarrow\hat{R}_{d}\equiv\int_{0}^{1}\ldots\int_{0}^{1}\frac{1}{{\textstyle\frac{1}{d}}\sum_{u=1}^{d}(1-\cos(2\pi x_{u}))}\ dx_{1}\ldots dx_{d}<\infty.$$

(13.34)

Here we give an independent analysis of this result, and the case $d=2$.

The $d=1$ result is from Chapter 5 (26). We now prove the other cases.

Proof. We may construct continuized random walk $\widetilde{X}^{(m)}_{t}$ on $Z^{d}_{m}$ from continuized random walk $\widetilde{X}_{t}$ on $Z^{d}$ by

$$\widetilde{X}^{(m)}_{t}=\widetilde{X}_{t}\bmod m$$

(13.38)

and then $P_{0}(\widetilde{X}^{(m)}_{t}=0)\geq P_{0}(\widetilde{X}_{t}=0)$. So

	$\displaystyle m^{-d}\tau_{0}^{(m)}$	$\displaystyle=$	$\displaystyle\int_{0}^{\infty}\left(P_{0}(\widetilde{X}^{(m)}_{t}=0)-m^{-d}\right)\ dt$		(13.39)
			(Chapter 2, Corollary 12 and (8))
		$\displaystyle=$	$\displaystyle\int_{0}^{\infty}\left(P_{0}(\widetilde{X}^{(m)}_{t}=0)-m^{-d}\right)^{+}dt\mbox{ by complete monotonicity}$
		$\displaystyle\geq$	$\displaystyle\int_{0}^{\infty}\left(P_{0}(\widetilde{X}_{t}=0)-m^{-d}\right)^{+}\ dt$
		$\displaystyle\rightarrow$	$\displaystyle\int_{0}^{\infty}P_{0}(\widetilde{X}_{t}=0)\ dt\quad=R_{d}.$

Consider the case $d\geq 3$. To complete the proof, we need the corresponding upper bound, for which it is sufficient to show

$$\int_{0}^{\infty}\left(P_{0}(\widetilde{X}_{t}^{(m)}=0)-m^{-d}-P_{0}(\widetilde{X}_{t}=0)\right)^{+}dt\rightarrow 0\mbox{ as }m\rightarrow\infty.$$

(13.40)

To verify (13.40) without detailed calculations, we first establish a 1-dimensional bound

$$(d=1)\ \ \ \ \ \ \ \ \tilde{p}^{(m)}(t)\leq{\textstyle\frac{1}{m}}+\tilde{p}(t).$$

(13.41)

To obtain (13.41) we appeal to a coupling construction (the reflection coupling, described in continuous-space in section 13.1.3 – the discrete-space setting here is similar) which shows that continuized random walks $\widetilde{X}^{(m)},\widetilde{Y}^{(m)}$ on $Z_{m}$ with $\widetilde{X}^{(m)}_{0}=0$ and $\widetilde{Y}^{(m)}_{0}$ distributed uniformly can be coupled so that

$$\widetilde{Y}^{(m)}_{t}=0\mbox{ on the event }\{\widetilde{X}^{(m)}_{t}=0,T\leq t\}$$

where $T$ is the first time that $\widetilde{X}^{(m)}$ goes distance $\lfloor m/2\rfloor$ from $0$. And by considering the construction (13.38)

$$P(\widetilde{X}^{(m)}_{t}=0)\leq P(\widetilde{X}_{t}=0)+P(\widetilde{X}^{(m)}_{t}=0,T\leq t)$$

and (13.41) follows, since $P(\widetilde{Y}^{(m)}_{t}=0)=1/m$.

Since the $d$-dimensional probabilities relate to the 1-dimensional probabilities via $P_{0}(\widetilde{X}_{t}^{(m)}=0)=\left(\tilde{p}^{(m)}(t/d)\right)^{d}$ and similarly on the infinite lattice, we can use inequality (13.41) to bound the integrand in (13.40) as follows.

	$\displaystyle P_{0}(\widetilde{X}_{t}^{(m)}=0)-m^{-d}-P_{0}(\widetilde{X}_{t}=0)$
		$\displaystyle\leq$	$\displaystyle\left({\textstyle\frac{1}{m}}+\tilde{p}(t/d)\right)^{d}-m^{-d}-(\tilde{p}(t/d))^{d}$
		$\displaystyle=$	$\displaystyle\sum_{j=1}^{d-1}{d\choose j}(\tilde{p}(t/d))^{j}({\textstyle\frac{1}{m}})^{d-j}$
		$\displaystyle=$	$\displaystyle\frac{\tilde{p}(t/d)}{m}\sum_{j=1}^{d-1}{d\choose j}(\tilde{p}(t/d))^{j-1}({\textstyle\frac{1}{m}})^{d-1-j}$
		$\displaystyle\leq$	$\displaystyle\frac{\tilde{p}(t/d)}{m}\sum_{j=1}{d-1}{d\choose j}\left[\max((\tilde{p}(t/d))^{d-2},{\textstyle\frac{1}{m}})\right]^{d-2}$
		$\displaystyle=$	$\displaystyle(2^{d}-2)\frac{\tilde{p}(t/d)}{m}\left[\max((\tilde{p}(t/d))^{d-2},({\textstyle\frac{1}{m}})^{d-2})\right]$
		$\displaystyle\leq$	$\displaystyle(2^{d}-2)\frac{\tilde{p}(t/d)}{m}\left[(\tilde{p}(t/d))^{d-2}+{\textstyle\frac{1}{m}})^{d-2}\right]$
		$\displaystyle=$	$\displaystyle(2^{d}-2)\left[\frac{(\tilde{p}(t/d))^{d-1}}{m}+\frac{\tilde{p}(t/d)}{m^{d-1}}\right].$

The fact (13.24) that $\tilde{p}(t)=\Theta(t^{-1/2})$ for large $t$ easily implies that the integral in (13.40) over $0\leq t\leq m^{3}$ tends to zero. But by (13.33) and submultiplicativity of $\bar{d}(t)$,

$$0\leq P_{0}(\widetilde{X}_{t}^{(m)}=0)-m^{-d}\leq d(t)\leq\bar{d}(t)\leq B_{1}\exp(-{\textstyle\frac{t}{B_{2}m^{2}}})$$

(13.42)

where $B_{1},B_{2}$ depend only on $d$. This easily implies that the integral in (13.40) over $m^{3}\leq t<\infty$ tends to zero, completing the proof of (13.37).

In the case $d=2$, we fix $b>0$ and truncate the integral in (13.39) at $bm^{2}$ to get

	$\displaystyle m^{-2}\tau_{0}^{(m)}$	$\displaystyle\geq$	$\displaystyle-b+\int_{0}^{bm^{2}}P_{0}(\widetilde{X}_{t}=0)\ dt$
		$\displaystyle=$	$\displaystyle-b+(1+o(1)){\textstyle\frac{2}{\pi}}\log(bm^{2})\mbox{ by }(\ref{d2N})$
		$\displaystyle=$	$\displaystyle(1+o(1)){\textstyle\frac{2}{\pi}}\log m.$

Therefore

$$\tau_{0}^{(m)}\geq(1+o(1)){\textstyle\frac{2}{\pi}}m^{2}\log m.$$

For the corresponding upper bound, since $\int_{0}^{m^{2}}P_{0}(\widetilde{X}_{t}=0)dt\sim{\textstyle\frac{2}{\pi}}\log m$ by (13.30), and $m^{-2}\tau_{0}^{(m)}=\int_{0}^{\infty}\left(P_{0}(\widetilde{X}^{(m)}_{t}=0)-m^{-2}\right)\ dt$ , it suffices to show that

$$\int_{0}^{\infty}\left(P_{0}(\widetilde{X}_{t}^{(m)}=0)-m^{-2}-P_{0}(\widetilde{X}_{t}=0)\right)^{+}\ dt$$

$$+\int_{m^{2}}^{\infty}\left(P_{0}(\widetilde{X}_{t}^{(m)}=0)-m^{-2}\right)^{+}dt=o(\log N).$$

(13.43)

To bound the first of these two integrals, we observe from (13.41) that $P_{0}(\widetilde{X}^{(m)}_{t}=0)\leq(m^{-1}+\tilde{p}(t/2))^{2}$, and so the integrand is bounded by ${\textstyle\frac{2}{m}}\tilde{p}(t/2)$. Using (13.24), the first integral is $O(1)=o(\log m)$. To analyze the second integral in (13.43) we consider separately the ranges $m^{2}\leq t\leq m^{2}\log^{3/2}m$ and $m^{2}\log^{3/2}m\leq t<\infty$. Over the first range, we again use (13.41) to bound the integrand by ${\textstyle\frac{2}{m}}\tilde{p}(t/2)+(\tilde{p}(t/2))^{2}$. Again using (13.24), the integral is bounded by

$$(1+o(1))\frac{2}{\pi^{1/2}m}\int_{m^{2}}^{m^{2}\log^{3/2}m}t^{-1/2}dt\ +\ (1+o(1))\pi^{-1}\int_{m^{2}}^{m^{2}\log^{3/2}m}t^{-1}dt$$

$$=\Theta(\log^{3/4}m)+\Theta(\log\log m)=o(\log m).$$

To bound the integral over the second range, we use (13.42) and find

	$\displaystyle\int_{m^{2}\log^{3/2}m}^{\infty}\left(P_{0}(\widetilde{X}^{(m)}_{t}=0)-m^{-2}\right)dt$	$\displaystyle\leq$	$\displaystyle B_{1}B_{2}m^{2}\exp(-{\textstyle\frac{\log^{3/2}m}{B_{2}}})$
		$\displaystyle=$	$\displaystyle o(1)=o(\log m).$

$\Box$

Fix $r\geq 3$ and write ${\bf T}^{r}$ for the infinite tree of degree $r$. We picture ${\bf T}^{r}$ as a “family tree”, where the root $\phi$ has $r$ children, and each other vertex has one parent and $r-1$ children. Being a vertex-transitive graph (recall Chapter 7 section 1.1; for $r$ even, ${\bf T}^{r}$ is the Cayley graph of the free group on $r/2$ generators), one can study many more general “random flights” on ${\bf T}^{r}$ (see Notes), but we shall consider only the simple random walk $(X_{t})$.

We can get some information about the walk without resorting to calculations. The “depth” process $d(X_{t},\phi)$ is clearly the “reflecting asymmetric random walk” on $Z^{+}:=\{0,1,2,\ldots\}$ with

$$p_{0,1}=1;\ p_{i,i-1}=1/r;\ p_{i,i+1}=(r-1)/r,\ i\geq 1.$$

By comparison with asymmetric random walk on all $Z$, which has drift $(r-2)/r$, we see that

$$t^{-1}d(X_{t},\phi)\rightarrow\frac{r-2}{r}\mbox{ a.s. as }t\rightarrow\infty.$$

(13.44)

In particular, the number of returns to $\phi$ is finite and so the walk is transient. Now consider the return probability $\rho=P_{\phi}(T^{+}_{\phi}<\infty)$ and note that (by considering the first step) $\rho=P_{\phi}(T_{c}<\infty)$ where $c$ is a child of $\phi$. Considering the first two steps, we obtain the equation $\rho=\frac{1}{r}+\frac{r-1}{r}\rho^{2}$, and since by transience $\rho<1$, we see that

$$\rho:=P_{\phi}(T^{+}_{\phi}<\infty)=P_{\phi}(T_{c}<\infty)=\frac{1}{r-1}.$$

(13.45)

So

$$E_{\phi}N_{\phi}(\infty)=\frac{1}{1-\rho}=\frac{r-1}{r-2}.$$

(13.46)

As at (13.32), $\rho$ has a sample path interpretation: the number $V_{t}$ of distinct vertices visited by the walk before time $t$ satisfies

$$t^{-1}V_{t}\rightarrow 1-\rho={\textstyle\frac{r-2}{r-1}}\mbox{ a.s. as }t\rightarrow\infty.$$

By transience, amongst the children of $\phi$ there is some vertex $L_{1}$ which is visited last by the walk; then amongst the children of $L_{1}$ there is some vertex $L_{2}$ which is visited last by the walk; and so on, to define a “path to infinity” $\phi=L_{0},L_{1},L_{2},\ldots$. By symmetry, given $L_{1},L_{2},\ldots,L_{i-1}$ the conditional distribution of $L_{i}$ is uniform over the children of $L_{i-1}$, so in the natural sense we can describe $(L_{i})$ as the uniform random path to infinity.

While the general qualitative behavior of random walk on ${\bf T}^{r}$ is clear from the arguments above, more precise quantitative estimates are most naturally obtained via generating function arguments. For any state $i$ of a Markov chain, the generating functions $G_{i}(z):=\sum_{t=0}^{\infty}P_{i}(X_{t}=i)z^{t}$ and $F_{i}(z):=\sum_{t=1}^{\infty}P_{i}(T^{+}_{i}=t)z^{t}$ are related by

$$G_{i}=1+F_{i}G_{i}$$

(13.47)

(this is a small variation on Chapter 2 Lemma 19). Consider simple symmetric reflecting random walk on $Z^{+}$. Clearly

$$G_{0}(z)=\sum_{t=0}^{\infty}{2t\choose t}2^{-2t}z^{2t}=(1-z^{2})^{-1/2},$$

the latter identity being the series expansion of $(1-x)^{-1/2}$. So by (13.47)

$$F_{0}(z):=\sum_{t=0\mbox{ or }1}^{\infty}P_{0}(T^{+}_{0}=2t)z^{2t}=1-(1-z^{2})^{1/2}.$$

Consider an excursion of length $2t$, that is, a path $(0=i_{0},i_{1},\ldots,i_{2t-1},i_{2t}=0)$ with $i_{j}>0,1\leq j\leq 2t-1$. This excursion has chance $2^{1-2t}$ for the symmetric walk on $Z^{+}$, and has chance $((r-1)/r)^{t-1}(1/r)^{t}$ for the asymmetric walk $d(X_{t},\phi)$. So

$$\frac{P_{\phi}(T^{+}_{\phi}=2t)}{P_{0}(T^{+}_{0}=2t)}=\frac{r}{2(r-1)}\ \left(\frac{4(r-1)}{r^{2}}\right)^{t}$$

where the numerator refers to simple RW on the tree, and the denominator refers to simple symmetric reflecting RW on $Z^{+}$. So on the tree,

$$F_{\phi}(z)=\frac{r}{2(r-1)}F_{0}\left(z\sqrt{{\textstyle\frac{4(r-1)}{r^{2}}}}\right)=\frac{r}{2(r-1)}\left(1-\left(1-\frac{4(r-1)z^{2}}{r^{2}}\right)^{1/2}\right).$$

Then (13.47) gives an expression for $G_{\phi}(z)$ which simplifies to

$$G_{\phi}(z)=\frac{2(r-1)}{r-2+\sqrt{r^{2}-4(r-1)z^{2}}}.$$

(13.48)

In particular, $G_{\phi}$ has radius of convergence $1/\beta$, where

$$\beta=2r^{-1}\sqrt{r-1}<1.$$

(13.49)

Without going into details, one can now use standard Tauberian arguments to show

$$t$$

(13.50)

for a computable constant $\alpha$, and this format (for different values of $\alpha$ and $\beta$) remains true for more general radially symmetric random flights on ${\bf T}^{r}$ ([339] Theorem 19.30). One can also in principle expand (13.48) as a power series to obtain $P_{\phi}(X_{t}=\phi)$. Again we shall not give details, but according to Giacometti [164] one obtains

	$\displaystyle P_{\phi}(X_{t}=\phi)$	$\displaystyle=$	$\displaystyle\frac{r-1}{r}\ \left(\frac{\sqrt{r-1}}{r}\right)^{t}\ \frac{\Gamma(1+t)}{\Gamma(2+t/2)\Gamma(1+t/2)}$		(13.51)
			$\displaystyle\times\ _{2}F_{1}({\textstyle\frac{t+1}{2}},1,2+{\textstyle\frac{t}{2}},{\textstyle\frac{4(r-1)}{r^{2}}}),\ t\mbox{ even}$

where $\ {}_{2}F_{1}$ is the generalized hypergeometric function.

Finally, the $\beta$ at (13.49) can be interpreted as an eigenvalue for the infinite transition matrix $(p_{ij})$, so we anticipate a corresponding eigenfunction $f_{2}$ with

$$\sum_{j}p_{ij}f_{2}(j)=\beta f_{2}(i)\ \forall i,$$

(13.52)

and one can verify this holds for

$$f_{2}(i):=(1+{\textstyle\frac{r-2}{r}}i)(r-1)^{-i/2}.$$

(13.53)

Fix $r\geq 3$ and consider a sequence $(G_{n})$ of $n$-vertex $r$-regular graphs with $n\rightarrow\infty$. Write $(X^{n}_{t})$ for the random walk on $G_{n}$. We can compare these random walks with the random walk $(X^{\infty}_{t})$ on ${\bf T}^{r}$ via the obvious inequality

$$P_{v}(X^{n}_{t}=v)\geq P_{\phi}(X^{\infty}_{t}=\phi),\ t\geq 0.$$

(13.54)

To spell this out, there is a universal cover map $\gamma:{\bf T}^{r}\rightarrow G_{n}$ with $\gamma(\phi)=v$ and such that for each vertex $w$ of ${\bf T}^{r}$ the $r$ edges at $w$ are mapped to the $r$ edges of $G_{n}$ at $\gamma(w)$. Given the random walk $X^{\infty}$ on ${\bf T}^{r}$, the definition $X^{n}_{t}=\gamma(X^{\infty}_{t})$ constructs random walk on $G_{n}$, and (13.54) holds because $\{X^{n}_{t}=v\}\supseteq\{X^{\infty}_{t}=\phi\}$.

It is easy to use (13.54) to obtain asymptotic lower bounds on the fundamental parameters discussed in Chapter 4. Instead of the relaxation time $\tau_{2}$, it is more natural here to deal directly with the second eigenvalue $\lambda_{2}$.