In talking about random walk on a weighted graph, we have been assuming the graph is fixed. It is conceptually only a minor modification to consider the case where the “environment” (the graph or the edge-weights) is itself first given in some specified random manner. This has been studied in several rather different contexts, and we will give a brief description of known results without going into many details.
Quantities like our mixing time parameters from Chapter 4 are now random quantities . In general we shall use boldface for quantities depending on the realization of the environment but not depending on a realization of the walk.
There is a body of work on estimating mixing times for various models of random regular graph. We shall prove two simple results which illustrate two basic techniques, and record some of the history in the Notes.
The first result is Proposition 1.2.1 of Lubotzky [243]. This illustrates the technique of proving expansion (i.e., upper-bounding the Cheeger time constant ) by direct counting arguments in the random graph.
Let be the -regular random graph on vertices with edges , where are independent uniform random permutations of . Write for the Cheeger time constant for random walk on . Then for fixed ,
Note that a realization of may be disconnected (in which case ) and have self-loops and multiple edges.
Outline of proof. Suppose a realization of the graph has the property
(13.59) |
where . Then
So we want to show that (13.59) holds with probability as . If (13.59) fails for some with , then there exists with such that
(13.60) |
(just take plus, if necessary, arbitrary extra vertices). For given and , the chance of (13.60) equals , where . So the chance that (13.59) fails is at most
So it suffices to verify . And this is a routine but tedious verification (see Notes).
Of course the bound on gives, via Cheeger’s inequality, a bound on , and thence a bound on via . But Proposition 13.11 is unsatisfactory in that these bounds get worse as increases, whereas intuitively they should get better. For bounds on which improve with we turn to the second technique, which uses the “” inequality to bound the variation threshold time . Specifically, recall (Chapter 3 Lemma 8b) that for an -state reversible chain with uniform stationary distribution, the variation distance satisfies
(13.61) |
This is simplest to use for random walk on a group, as illustrated by the following result of Roichman [296].
Fix . Given a group , let be a random set of distinct elements of , and consider random walk on the associated Cayley graph with edges . For any sequence of groups with ,
Proof. We first give a construction of the random walk jointly with the random set . Write for a set of symbols, and write . Fix and let be independent uniform on . Choose by uniform sampling without replacement from , and set . Then the process constructed via is distributed as the random walk on the random Cayley graph, started at the identity . So where is the -step transition probability in the random environment, and by (13.61) it suffices to take (for defined in the statement of the Proposition) and show
(13.62) |
To start the argument, let be the number of distinct values taken by , where we define . Fix and . Then
By considering the possible choices of ,
Since we deduce
(13.63) |
Now consider the construction of given above. We claim
(13.64) |
For if then there exists some such that for exactly one value of in . So if we condition also on , then or where and are determined by the conditioning, and then the conditional probability that is the conditional probability of taking a particular value, which is at most .
Simple random walk on the infinite regular tree is a fundamental process, already discussed in section 13.2.6. There are several natural ways to randomize the environment; we could take an infinite regular tree and attach random edge-weights; or we could consider a Galton–Watson tree, in which numbers of children are random. Let us start by considering these possibilities simultaneously. Fix a distribution where
(13.65) |
Note the may be dependent. Construct a tree via:
the root has children, and the edge to the th child has weight ; repeat recursively for each child, taking independent realizations of the distribution (13.65).
So the case gives the randomly-weighted -ary tree (precisely, the modification where the root has degree instead of ), and the case gives a Galton–Watson tree. As in Chapter 3 section 2 to each realization of a weighted graph we associate a random walk with transition probabilities proportional to edge-weights. Since random walk on the unweighted -ary tree is transient, a natural first issue is prove transience in this “random environment” setting. In terms of the electrical network analogy (see comment below Theorem 13.5), interpreting as conductance, we want to know whether the (random) resistance between and is a.s. finite. By considering the children of , it is clear that the distribution of satisfies
(13.66) |
where the are independent of each other and of , and . But is a solution of (13.66), so we need some work to actually prove that .
The resistance between and satisfies a.s..
Proof. Write for the resistance between and height (i.e. the height- vertices, all shorted together). Clearly as , and analogously to (13.66)
where the are independent of each other and of , and .
Consider first the special case . Choose such that . Suppose inductively that (which holds for since ). Then
This implies , and the induction goes through. Thus . By (13.66) satisfies , so or , and we just eliminated the possibility . So a.s..
Reducing the general case to the special case involves a comparison idea, illustrated by the figure.
Here the edge-weights are resistances. In the left network, is linked to via an arbitrary tree, and in the right network, this tree is replaced by three direct edges, each with resistance . We claim that this replacement can only increase the resistance between and . This is a nice illustration of Thompson’s principle (Chapter 3 section 7.1) which says that in a realization of either graph, writing for resistance and suming over undirected edges ,
where is a unit flow from to . Let be the minimizing flow in the right network; use to define a flow in the left network by specifying that the flow through (resp. , ) is the same in the left network and the right network. It is easy to check
and hence the resistance can indeed only be less in the left network.
In the general case, the fact implies that the number of individuals in generation tends to a.s. as . So in particular we can find distinct individuals in some generation . Retain the edges linking with these individuals, and cut all other edges within the first generations. Repeat recursively for descendants of . This procedure constructs an infinite subtree, and it suffices to show that the resistance between and in the subtree is a.s. finite. By the comparison argument above, we may replace the network linking to by three direct edges with the same (random) resistance, and similarly for each stage of the construction of the subtree; this gives another tree , and it suffices to shows its resistance is finite a.s.. But fits the special case .
It is not difficult (we won’t give details) to show that the distribution of is the unique distribution on satisfying (13.66). It does seem difficult to say anything explicit about the distribution of in Proposition 13.13. One can get a little from comparison arguments. On the binary tree (), by using the exact potential function and the exact flows from the unweighted case as “test functions” in the Dirichlet principle and Thompson’s principle, one obtains
Lyons et al [248, 245, 246], summarized in [249] Chapter 10, have studied in detail questions concerning a certain model of biased random walk on deterministic and random infinite trees. Much of their focus is on topics too sophisticated (boundary theory, dimension) to recount here, but let us give one simple result.
Consider the unweighted Galton–Watson tree with offspring distribution , i.e., the case of (13.65). Fix a parameter . In the biased random walk , from a vertex with children the walker goes to any particular child with probability , and to the parent with probability . It turns out [246] that the biased random walk is recurrent for and transient for . We will just prove one half of that result.
The biased random walk is a.s. recurrent for .
Proof. We use a “method of fictitious roots”. That is, to the root of the Galton-Watson tree we append an extra edge to a “fictitious” root , and we consider random walk on this extended tree (rooted at ). Write for the probability (conditional on the realization of the tree) that the walk started at never hits . It will suffice to prove . Fix a realization of the tree, in which has children. Then
where is the probability (on this realization) that the walk started at the ’th child of never hits . Rearrange to see . So on the random tree we have
where the are independent of each other and , and . Applying Jensen’s inequality to the concave function shows
By considering the relevant quadratic equation, one sees that for this inequality has no solution with . So , as required.
In the transient case, we expect there to exist a non-random speed such that
(13.67) |
Lyons et al [246] show that, when , (13.67) is indeed true and that for all . Moreover in the unbiased () case there is a simple formula [245]
There is apparently no such simple formula for in general. See Lyons et al [247] for several open problems in this area.
Cayley’s formula ([313] p. 25) says there are different trees on labeled vertices . Assuming each such tree to be equally likely gives one tractable definition (there are others) of random -tree . One can combine the formulas from Chapter 5 section 3 for random walks on general trees with known distributional properties of to get a variety of formulas for random walk on , an idea going back to Moon [264].
As an illustration it is known [264] that the distance between vertex and vertex in has distribution
where . Routine calculus gives
(13.68) |
Now on any -vertex tree, the mean hitting time satisfies
(13.69) |
(Chapter 5 (84)), and so
Combining with (13.68),
(13.70) |
Instead of deriving more formulas of this type for random walk on , let’s jump to the bottom line. It turns out that all the mixing and hitting time parameters of Chapter 4, and the analogous “mean cover time” parameters of Chapter 6, are of order but are random to first order: that is,
(13.71) |
for non-deterministic limits . The fact that all these parameters have the same order is of course reminiscent of the cases of the -cycle and -path (Chapter 5 Examples 7 and 8), where all the parameters are . And the sophisticated explanation is the same: one can use the weak convergence paradigm (section 13.1.1). In the present context, the random tree rescales to a limit continuum random tree , and the random walk converges (with time rescaled by and space rescaled by ) to Brownian motion on , and (analogously to section 13.1.1) the rescaled limits of the parameters are just the corresponding parameters for the Brownian motion. See the Notes for further comments.
Fix a distribution on with . For each consider the random graph , that is the graph on vertices where each possible edge has chance to be present. Attach independent random conductances, distributed as , to the edges. Aspects of this model were studied by Grimmett and Kesten [175]. As they observe, much of the behavior is intuitively rather clear, but technically difficult to prove: we shall just give the intuition.
Case (i): for fixed .
Here the number of edges at vertex is asymptotically Poisson(),
and the part of the graph within a fixed distance of vertex
is asymptotically like the first generations in the random family tree of a Galton–Watson
branching process with Poisson() offspring distribution, with independent edge-weights
attached.
This tree essentially fits the setting of Proposition 13.13,
except that the number of offspring may be zero and so the tree
may be finite, but it is not hard to show (modifying the proof of Proposition 13.13) that the resistance
in between the root and satisfies
and its distribution is characterized by the analog of (
refRdef).
The asymptotic approximation implies that, for
slowly, the resistance between vertex and
the depth- vertices of satisfies
.
We claim that the resistance between vertices
and of satisfies
The lower bound is clear by shorting, but the upper bound requires a complicated construction to connect the two sets of vertices at distances from vertices and in such a way that the effective resistance of this connecting network tends to zero.
The number of edges of the random graph is asymptotic to . So the total edge weight is asymptotic to , and by the commute interpretation of resistance the mean commute time for random walk on a realization of the graph satisfies
Case (ii): , some . Here the degree of vertex tends to , and it is easy to see that the (random) stationary probability and the (random) transition probabilities and stationary distribution the random walk satisfy
So for fixed , the -step transition probabilities satisfy as . This suggests, but it is technically hard to prove, that the (random) fundamental matrix satisfies
(13.72) |
Granted (13.72), we can apply Lemma 11 of Chapter 2 and deduce that the mean hitting times on a realization of the random graph satisfies
(13.73) |
The phrase random walk in random environment (RWRE) is mostly used to denote variations of the classical “random flight in dimensions” model. Such variations have been studied extensively in mathematical physics as well as theoretical probability, and the monograph of Hughes [184] provides thorough coverage. To give the flavor of the subject we quote one result, due to Boivin [52].
Assign random conductances to the edges of the two-dimensional lattice
, where
(i) the process is stationary ergodic.
(ii) a.s., for some constants
.
Let be the associated random walk on this weighted
graph, .
Then
where is a certain two-dimensional Normal
distribution,
and moreover this convergence holds for the conditional distribution
of given the environment, for almost all environments.