There is a huge research literature concerning random walks on infinite discrete groups, and more generally on infinite graphs, and the recent monograph of Woess [339] provides an in-depth treatment. This section focuses narrowly on two aspects of an issue not emphasized in [339]: what does study of random walk on infinite graphs tell us about random walks on finite graphs? One aspect of this issue is that random walks on certain specific infinite graphs may be used to get approximations or inequalities for random walks on specific finite graphs. We treat three examples.
The infinite lattice as an approximation to the discrete torus for large (section 13.2.4).
The infinite degree- tree and bounds for -regular expander graphs of large size (section 13.2.6).
The hierarchical tree as an approximation to balanced -ary trees (section 13.2.9).
The second aspect concerns properties such as transience, non-trivial boundary, and “spectral radius ”, which have been well-studied as qualitative properties which an infinite-state chain either possesses or does not possess. What are the quantitative finite-state analogs of such properties? Here actual theorems are scarce; we present conceptual discussion in sections 13.2.3 and 13.2.10 as a spur to future research.
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 , 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 ; conversely, given edge-weights we defined random walk as the reversible chain
(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
(13.20) |
and we study the associated random walk , i.e., the discrete-time chain with . So in the unweighted setting (), we have nearest-neighbor random walk on a locally finite, infinite graph.
To explain why we adopt this set-up, say is invariant for if
Consider asymmetric random walk on , say
(13.21) |
One easily verifies that each of the two measures and is invariant. Such nonuniqueness makes it awkward to seek to define reversibility of via the detailed balance equations
(13.22) |
without a prior definition of . Stating definitions via weighted graphs avoids this difficulty.
The second assumption in (13.20), that , excludes the positive-recurrent case (see Theorem 13.4 below); because in that case the questions one asks, such as whether the relaxation time 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 , which is the chain (13.21) with , has a particle moving towards and so certainly doesn’t satisfy this intuitive notion. On the other hand, a probabilistic interpretation of an infinite invariant measure is that if we start at time with independent Poisson() numbers of particles at vertices , and let the particles move independently according to , 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 and let be the total number of visits (including time 0) to .
For a general chain,
one of the following alternatives holds.
Recurrent. and and for all .
Transient. and and for all .
In the recurrent case there exists an invariant measure , unique
up to constant multiples,
and the chain is either
positive-recurrent:
and ; or
null-recurrent:
and .
In the transient and null-recurrent cases,
as
for all .
Specializing to random walk on a weighted graph, the measure 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 , Theorem 13.4 contains the “classical” method to establish transience or recurrence by considering the behavior of . This method works easily for random walk on (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 , and the net flow out of a vertex . Say is a unit flow from to infinity if and . Thompson’s principle (Chapter 3 Proposition 35) extends to the infinite setting, by considering subsets (the empty set) with finite.
Consider a weighted graph satisfying (13.20). For each ,
In particular, the random walk is transient iff for some (all) there exists a unit flow from to infinity such that .
By analogy with the finite setting, we can regard the inf as the effective resistance between 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.
(a) If a weighted graph is recurrent, then so is any subgraph.
(b) To show that a weighted graph is transient, it suffices to find
a transient subgraph.
Thus the classical fact that is recurrent implies that a subgraph of is recurrent, a fact which is hard to prove by bounding -step transition probabilities. In the other direction, it is possible (but not trivial) to prove that is transient by exhibiting a flow: indeed Doyle and Snell [131] construct a transient tree-like subgraph of .
Here is a different formulation of the same idea.
The return probability cannot increase if a new edge (not incident at ) is added, or the weight of an existing edge (not incident at ) is increased.
Recall the mean hitting time parameter from Chapter 4. For a sequence of -state reversible chains, consider the property
(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 for each , so that by Chapter 2 Lemma 10
The boundedness (in ) of this sum is a natural analog of the transience condition
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 -vertex graph has , as in the case of in Proposition 13.8 below.
We consider the lattice as an infinite -regular unweighted graph. Write for simple random walk on , and write 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 consider
independent Poisson numbers of and jumps | ||||
where is the modified Bessel function of the first kind of order . Now , and as a consequence of the local CLT (or by quoting asymptotics of the Bessel function ) we have
(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 is that the coordinate processes are independent copies of slowed-down one-dimensional processes, so that in dimension satisfies
(13.25) |
In particular, from (13.24),
(13.26) |
One can do a similar analysis in the discrete time case. In dimension ,
(13.27) | |||||
This agrees with (13.26) but with an extra “artificial” factor of arising from periodicity. A more tedious argument gives the analog of (13.26) in discrete time for general :
(13.28) |
From the viewpoint of classical probability, one can regard (13.26,13.28) as the special case of the local CLT: in continuous time in dimension ,
where denotes Euclidean norm.
The occupation time satisfies (continuous time) and (discrete time). In either case, as ,
(13.29) | |||||
(13.30) | |||||
(13.31) | |||||
where for by (13.26). This is the classical argument for establishing transience in and recurrence in , by applying Theorem 13.4. Note that the return probability is related to by ; in other words
Textbooks sometimes give the impression that calculating is hard, but one can just calculate numerically the integral (13.31). Or see [174] for a table.
The quantity has the following sample path interpretation. Let be the number of distinct vertices visited by the walk before time . Then
(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 relates to asymptotics for random walk on the finite torus , discussed in Chapter 5. We now use superscript to denote the length parameter. From Chapter 5 Example 17 we have
(13.33) |
where asymptotics are as for fixed . One can interpret this as a consequence of the time rescaling in the wweak convergence of rescaled random walk to Brownian motion of the -dimensional torus, for which (cf. sections 13.1.1 and 13.1.2) . At (74)–(75) of Chapter 5 we saw that the eigentime identity gave an exact formula for the mean hitting time parameter , whose asymptotics are, for ,
(13.34) |
Here we give an independent analysis of this result, and the case .
The result is from Chapter 5 (26). We now prove the other cases.
Proof. We may construct continuized random walk on from continuized random walk on by
(13.38) |
and then . So
(13.39) | |||||
(Chapter 2, Corollary 12 and (8)) | |||||
Consider the case . To complete the proof, we need the corresponding upper bound, for which it is sufficient to show
(13.40) |
To verify (13.40) without detailed calculations, we first establish a 1-dimensional bound
(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 on with and distributed uniformly can be coupled so that
where is the first time that goes distance from . And by considering the construction (13.38)
and (13.41) follows, since .
Since the -dimensional probabilities relate to the 1-dimensional probabilities via and similarly on the infinite lattice, we can use inequality (13.41) to bound the integrand in (13.40) as follows.
The fact (13.24) that for large easily implies that the integral in (13.40) over tends to zero. But by (13.33) and submultiplicativity of ,
(13.42) |
where depend only on . This easily implies that the integral in (13.40) over tends to zero, completing the proof of (13.37).
In the case , we fix and truncate the integral in (13.39) at to get
Therefore
For the corresponding upper bound, since by (13.30), and , it suffices to show that
(13.43) |
To bound the first of these two integrals, we observe from (13.41) that , and so the integrand is bounded by . Using (13.24), the first integral is . To analyze the second integral in (13.43) we consider separately the ranges and . Over the first range, we again use (13.41) to bound the integrand by . Again using (13.24), the integral is bounded by
To bound the integral over the second range, we use (13.42) and find
Fix and write for the infinite tree of degree . We picture as a “family tree”, where the root has children, and each other vertex has one parent and children. Being a vertex-transitive graph (recall Chapter 7 section 1.1; for even, is the Cayley graph of the free group on generators), one can study many more general “random flights” on (see Notes), but we shall consider only the simple random walk .
We can get some information about the walk without resorting to calculations. The “depth” process is clearly the “reflecting asymmetric random walk” on with
By comparison with asymmetric random walk on all , which has drift , we see that
(13.44) |
In particular, the number of returns to is finite and so the walk is transient. Now consider the return probability and note that (by considering the first step) where is a child of . Considering the first two steps, we obtain the equation , and since by transience , we see that
(13.45) |
So
(13.46) |
As at (13.32), has a sample path interpretation: the number of distinct vertices visited by the walk before time satisfies
By transience, amongst the children of there is some vertex which is visited last by the walk; then amongst the children of there is some vertex which is visited last by the walk; and so on, to define a “path to infinity” . By symmetry, given the conditional distribution of is uniform over the children of , so in the natural sense we can describe as the uniform random path to infinity.
While the general qualitative behavior of random walk on is clear from the arguments above, more precise quantitative estimates are most naturally obtained via generating function arguments. For any state of a Markov chain, the generating functions and are related by
(13.47) |
(this is a small variation on Chapter 2 Lemma 19). Consider simple symmetric reflecting random walk on . Clearly
the latter identity being the series expansion of . So by (13.47)
Consider an excursion of length , that is, a path with . This excursion has chance for the symmetric walk on , and has chance for the asymmetric walk . So
where the numerator refers to simple RW on the tree, and the denominator refers to simple symmetric reflecting RW on . So on the tree,
Then (13.47) gives an expression for which simplifies to
(13.48) |
In particular, has radius of convergence , where
(13.49) |
Without going into details, one can now use standard Tauberian arguments to show
(13.50) |
for a computable constant , and this format (for different values of and ) remains true for more general radially symmetric random flights on ([339] Theorem 19.30). One can also in principle expand (13.48) as a power series to obtain . Again we shall not give details, but according to Giacometti [164] one obtains
(13.51) | |||||
where is the generalized hypergeometric function.
Finally, the at (13.49) can be interpreted as an eigenvalue for the infinite transition matrix , so we anticipate a corresponding eigenfunction with
(13.52) |
and one can verify this holds for
(13.53) |
Fix and consider a sequence of -vertex -regular graphs with . Write for the random walk on . We can compare these random walks with the random walk on via the obvious inequality
(13.54) |
To spell this out, there is a universal cover map with and such that for each vertex of the edges at are mapped to the edges of at . Given the random walk on , the definition constructs random walk on , and (13.54) holds because .
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 , it is more natural here to deal directly with the second eigenvalue .
For random walk on -vertex -regular graphs, with fixed
and
(a)
;
(b)
;
(c)
.
Theory concerning expanders (Chapter 9 section 1) shows there exist graphs where the limits above are finite constants (depending on ), so Lemma 13.9 gives the optimal order of magnitude bound.
Proof. For (a), switch to the continuous-time walk, consider an arbitrary vertex in , and take with . Then we repeat the argument around (13.39) in the torus setting:
which is somewhat stronger than assertion (a). Next, the discrete-time spectral representation implies
Using (13.54) and (13.50), for any with even,
(13.55) |
For (b), the argument for (13.54) gives a coupling between the process started at and the process started at such that
where and denote graph distance. Fix and write . By the coupling and (13.44), as . This remains true in continuous time. Clearly , and so by definition of we have
But by counting vertices,
For these two limit results to be consistent we must have for all large , establishing (b).
For (c), fix a vertex of and use the function at (13.53) to define for all vertices of . The equality (13.52) for on the infinite tree easily implies the inequality on . Set and write for the unit function. By the Rayleigh-Ritz characterization (Chapter 4 eq. (73)), writing ,
As we have while tends to a non-zero limit, establishing (c).
Fix . There is an infinite tree (illustrated for in the figure) specified as follows. Each vertex is at some height . A vertex at height has one parent vertex at height and (if ) child vertices at height . The height- vertices are leaves, and the set of leaves has a natural labeling by finite -ary strings. The figure illustrates the binary () case, where . forms an Abelian group under entrywise addition modulo , e.g. for we have . Adopting a name used for generalizations of this construction in statistical physics, we call the hierarchical lattice and the tree the hierarchical tree.
Fix a parameter . Consider biased random walk on the tree , where from each non-leaf vertex the transition goes to the parent with probability and to each child with probability . Then consider “ watched only on ”, that is the sequence of (not-necessarily distinct) successive leaves visited by . The group is distance-transitive (for Hamming distance on ) and is a certain isotropic random flight on . A nice feature of this example is that without calculation we can see that is recurrent if and only if . For consider the path of ancestors of . The chain must spend an infinite time on that path (side-branches are finite); on that path behaves as asymmetric simple random walk on , which is recurrent if and only if ; so and thence visits infinitely often if and only if .
Another nice feature is that we can give a fairly explicit expression for the -step transition probabilities of . Writing for the maximum height reached by in an excursion from the leaves, then
where denotes hitting time for the height process. Writing for the maximum height reached in excursions,
It is clear by symmetry that the distribution of is conditionally uniform on the leaves which are descendants of the maximal-height vertex previously visited by . So for leaves with branchpoint at height ,
Since , we have found the “fairly explicit expression” promised above. A brief calculation gives the following time-asymptotics. Fix and consider with ; then
In particular,
(13.56) |
Comparing with (13.26), this gives a sense in which mimics simple random walk on , for defined above. Note that increases continuously from to as increases from to , and that is recurrent if and only if .
Though we don’t go into details, random walk on the hierarchical lattice is a natural infinite-state analog of biased random walk on the balanced finite tree (Chapter 5 section 2.1). In particular, results in the latter context showed that, writing for number of vertices, if and only if , that is if and only if . This is the condition for transience of the infinite-state walk, confirming the paradigm of section 13.2.3.
Three chapters of Woess [339] treat in detail three properties that random walk on an infinite graph may or may not possess:
transience
spectral radius
non-trivial boundary.
Can these be related to properties for sequences of finite chains? We already mentioned (section 13.2.3) that the property seems to be the analog of transience. In this speculative section we propose definitions of three other properties for sequences of finite chains, which we name
compactness
infinite-dimensionality
expander-like.
Future research will show whether these are useful definitions! Intuitively we expect that every reasonably “natural” sequence should fall into one of these three classes.
For simplicity we consider reversible random walks on Cayley graphs. It is also convenient to continuize. The resulting chains are special cases of (reversible) Lévy processes. We define the general Lévy process to be a continuous-time process with stationary independent increments on a (continuous or discrete) group. Thus the setting for the rest of this section is a sequence of reversible Lé—vy processes on finite groups of size through some subsequence. Because we work in continuous time, the eigenvalues satisfy .
(A): Compactness. Say the sequence is compact if there exists a (discrete or continuous) compact set and a reversible Lévy process on such that
(i) as ;
(ii) ; where are the eigenvalues of ;
(iii) .
These properties formalize the idea that the sequence of random walks form discrete approximations to a limit Lévy process on a compact group, at least as far as mixing times are concerned. Simple random walk on , and the limit Brownian motion on (section 13.1.2) form the obvious example. Properties (i) and (iii) imply, in particular, that
(13.57) |
One might hope that a converse is true:
Does every sequence satisfying (13.57) have a compact subsequence?
Unfortunately, we are convinced that the answer is “no”, for the following reason. Take which is compact, where the limit Lévy process has function as at (i). Now consider a product chain , where components run independently, and where has the cut-off property (Chapter 7) and . Note that by Chapter 7-1 Lemma 1 we have . If the product chain had a subsequential limit, then its total variation function at (i), say , must satisfy
But it seems intuitively clear (though we do not know a proof) that every Lévy process on a compact set has continuous . This suggests the following conjecture.
For any sequence of reversible Lévy processes satisfying (13.57),
there exists a subsequence satisfying the definition of compact
except that condition (ii) is replaced by
(iv):
Before describing the other two classes of chains, we need a definition and some motivating background. In the present setting, the property “trivial boundary” is equivalent (see Notes) to the property
(13.58) |
This suggests that an analogous finite-state property might involve whether the variation distance for nearby starts becomes small before time . Say that a sequence of subsets is an asymptotic -neighborhood if
uniformly over ; here is an arbitrary reference vertex. From Chapter 7-1 Lemma 1(b) we can deduce that, if the cut-off property holds, such a neighborhood must have size .
(B): Infinite dimensional. Say the sequence is infinite-dimensional if the following three properties hold.
(i)
(ii) The cut-off property holds
(iii) there exists some , increasing from to as increases from to , such that a maximal-size asymptotic -neighborhood has
This definition is an attempt to abstract the essential properties of random walk on the -cube (Chapter 5 Example 15), where properties (i) and (ii) were already shown. We outline below a proof of property (iii) in that example. Another fundamental example where (i) and (ii) hold is card-shuffling by random transpositions (Chapter 7 Example 18)), and we conjecture that property (iii) also holds there. Conceptually, this class infinite-dimensional of sequences is intended (cf. (13.58)) as the analog of a single random walk with trivial boundary on an infinite-dimensional graph.
Property (iii) for the -cube. Let be continuous-time random walk on the -cube, and continuous-time random walk on the -cube, where . The natural coupling shows
Take with
for some , so that
Since the variation cut-off for the -cube is at , we see that for vertices and at distance ,
So a maximal-size asymptotic -neighborhood of must be of the form . So
as required.
Finally, we want an analog of a random walk with non-trivial boundary, expressed using property (ii) below.
(C): Expander-like. Say the sequence is expander-like if
(i)
(ii) every asymptotic -neighborhood has
(iii) The cut-off property holds.
Recall from Chapter 9 section 1 that, for symmetric graphs which are -regular expanders for fixed , we have and . But it is not known whether properties (ii) and (iii) always hold in this setting.