7.1 Symmetric reversible chains

Consider an irreducible transition matrix ${\bf P}=(p_{ij})$ on a finite state space $I$. A symmetry of ${\bf P}$ is a $1-1$ map $\gamma:I\rightarrow I$ such that

The set $\Gamma$ of symmetries forms a group under convolution, and in our (non-standard) terminology a symmetric Markov transition matrix is one for which $\Gamma$ acts transitively, i.e.

Such a chain need not be reversible; a symmetric reversible chain is just a chain which is both symmetric and reversible. A natural setting is where $I$ is itself a group under an operation $(i,j)\rightarrow ij$ which we write multiplicitively. If $\mu$ is a probability distribution on $I$ and $(Z_{t};t\geq 1)$ are i.i.d. $I$-valued with distribution $\mu$ then

is the symmetric Markov chain with transition probabilities

started at $x_{0}$. This chain is reversible iff

We have rather painted ourselves into a corner over terminology. The usual terminology for the process (7.1) is “random walk on the group $I$” and if (7.2) holds then it is a

Unfortunately in this phrase, both “symmetric” and “walk” conflict with our conventions, so we can’t use the phrase. Instead we will use “random flight on the group $I$” for a process (7.1), and “reversible random flight on the group $I$” when (7.2) also holds. Note that we always assume chains are irreducible, which in the case of a random flight holds iff the support of $\mu$ generates the whole group $I$. Just keep in mind that the topic of this section, symmetric reversible chains, forms a minor generalization of the processes usually described by (7.3).

On an graph $(\mbox{${\cal V}$},\mbox{${\cal E}$})$, a graph automorphism is a $1-1$ map $\gamma:\mbox{${\cal V}$}\rightarrow\mbox{${\cal V}$}$ such that

The graph is called vertex-transitive if the automorphism group acts transitively on vertices. Clearly, random walk on a (unweighted) graph is a symmetric reversible chain iff the graph is vertex-transitive. We specialize to this case in section 7.1.8. A further specialization is to random walk on a Cayley graph. If $\mbox{${\cal G}$}=(g_{i})$ is a set of generators of a group $I$, which we always assume to satisfy

then the associated Cayley graph has vertex-set $I$ and edge-set

A Cayley graph is vertex-transitive.

Finally, recall from Chapter 3 yyy that we can identify a reversible chain with a random walk on a weighted graph. With this identification, a symmetric reversible chain is one where the weighted graph is vertex-transitive, in the natural sense.

Proof. In either case the stationary distribution is uniform – under (a), by letting $t\rightarrow\infty$, and under (b) by taking $t=1$, implying $p_{ij}\equiv p_{ji}$. So by reversibility $P_{i}(X_{t}=j)=P_{j}(X_{t}=i)$ for $i\neq j$ and $t\geq 1$. But recall from Chapter 2 Lemma yyy that the generating functions $G_{ij}(z)=\sum_{t}P_{i}(X_{t}=j)z^{j}$ and $F_{ij}(z)=\sum_{t}P_{i}(T_{t}=j)z^{j}$ satisfy

For $i\neq j$ we have seen that $G_{ij}=G_{ji}$, and hence by (7.4)

which is the assertion of Lemma 7.1.

Our standing assumption is that we have an irreducible symmetric reversible $n$-state chain. The symmetry property implies that the stationary distribution $\pi$ is uniform, and also implies

But by Chapter 3 Lemma yyy, under reversibility (7.5) is equivalent to

And clearly (7.6) implies

We make frequent use of these properties. Incidently, (7.7) is in general strictly weaker than (7.6): van Slijpe [330] p. 288 gives an example with a $3$-state reversible chain.

We also have, from the definition of symmetric, that $E_{\pi}T_{i}$ is constant in $i$, and hence

So by Chapter 4 yyy

The formula for $E_{\pi}T_{i}$ in terms of the fundamental matrix (Chapter 2 yyy) can be written as

Approximating $\tau_{0}$ by the first few terms is what we call the local transience heuristic. See Chapter xxx for rigorous discussion.

Proof. (i) This is a specialization of Chapter 6 xxx.

(ii) For any $i,j,k$,

Averaging over $k$, the right side becomes $2\tau_{0}$.

Recall that a simple Cauchy-Schwartz argument (Chapter 3 yyy) shows that, for any reversible chain whose stationary distribution is uniform,

So by (7.5), for a symmetric reversible chain, the most likely place to be after $2t$ steps is where you started:

This type of result is nicer in continuous time, where the inequality holds for all times.

Here is our first non-trivial result, from Aldous [18].

Note that, because $\tau_{2}\leq\tau_{1}+1$ and $\tau_{0}\geq(n-1)^{2}/n$, the hypothesis “$\tau_{2}/\tau_{0}\rightarrow 0$” is weaker than either “$\tau_{2}/n\rightarrow 0$” or “$\tau_{1}/\tau_{0}\rightarrow 0$”.

Part (a) is a specialization of Chapter 3 Proposition yyy and its proof. Parts (b) and (c) use refinements of the same technique. Part (b) implies

Because this applies in many settings in this Chapter, we shall rarely need to discuss $\tau^{*}$ further.

xxx give proof

In connection with (b), note that

by definition of $\tau_{1}^{(2)}$ and vertex-transitivity. So (b) is obvious under the slightly stronger hypothesis $\tau_{1}/\tau_{0}\rightarrow 0$.

Chapter 3 Proposition yyy actually gives information on hitting times $T_{A}$ to more general subsets $A$ of vertices. Because (Chapter 3 yyy) $E_{\pi}T_{A}\geq\frac{(1-\pi(A))^{2}}{\pi(A)}$, we get (in continuous time) a quantification of the fact that $T_{A}$ has approximately exponential distribution when $|A|\ll n/\tau_{2}$ and when the chain starts with the uniform distribution:

Recall the cover time $C$ from Chapter 6. By symmetry, in our present setting $E_{i}C$ doesn’t depend on the starting place $i$, so we can write $EC$. In this section we combine results on hitting times with various forms of Matthews method to obtain asymptotics for cover times in the setting of a sequence of symmetric reversible chains. Experience, and the informal argument above (7.15), suggest the principle

The results in this chapter concerning cover times go some way towards formalizing this principle.

Proof. Using the basic form of Matthews method (Chapter 2 yyy), (a) follows from Lemma 7.2 and (b) from Theorem 7.4. To prove (c), fix a state $j$ and $\varepsilon>0$. Using (7.11) and Markov’s inequality,

So we can inductively choose $\lceil\alpha^{-1}\rceil$ vertices $i_{k}$ such that

By the extended form of Matthews method (Chapter 6 Corollary yyy)

From Chapter 4 yyy, $\tau_{1}\leq\tau_{2}(1+\log n)$ and so the hypothesis implies $\tau_{1}/\tau_{0}=O(n^{\varepsilon-\beta})$. So the asymptotic lower bound for $EC$ becomes $(1-\varepsilon)\tau_{0}(\beta-\varepsilon)\log n$, and since $\varepsilon$ is arbitrary the result follows.

Since the only natural examples with $\tau_{1}/\tau_{0}\not\rightarrow 0$ are variations of random walk on the $n$-cycle, for which $EC=\Theta(\tau_{0})$ without the “$\log n$” term, we expect a positive answer to

Here is an artificial example to illustrate the bound in (c).

Take $m_{1}=m_{1}(n),m_{2}=m_{2}(n)$ such that $m_{1}\sim n^{1-\beta},m_{1}m_{2}\sim n$. The underlying idea is to take two continuous-time random walks on the complete graphs $K_{m_{1}}$ and $K_{m_{2}}$, but with the walks run on different time scales. To set this up directly in discrete time, take state space $\{(x,y):1\leq x\leq m_{1},1\leq y\leq m_{2}\}$ and transition probabilities

where $a=a(n)\uparrow\infty$ slowly. It is not hard to formalize the following analysis. Writing the chain as $(X_{t},Y_{t})$, the $Y$-component stays constant for time $\Theta(am_{1}\log m_{1})$, during which time every $x$-value is hit, because the cover time for $K_{m_{1}}$ is $\sim m_{1}\log m_{1}$. And $m_{2}\log m_{2}$ jumps of the $Y$-component are required to hit every $y$-value, so

Now $\tau_{2}\sim am_{1}\log m_{1}$, and because the mean number of returns to the starting point before the first $Y$-jump is $\sim a\log m_{1}$ we can use the local transience heuristic (7.10) to see $\tau_{0}\sim(a\log m_{1})\times n$. So $\tau_{2}/\tau_{0}\sim m_{1}/n\sim n^{-\beta}$, and the lower bound from (c) is

But this agrees with the exact limit (7.13), because $m_{2}\sim n^{\beta}$.

We now turn to sharper distributional limits for $C$. An (easy) background fact is that, for independent random variables $(Z_{i})$ with exponential, mean $\tau$, distribution,

where $\eta$ has the extreme value distribution

Now the cover time $C=\max_{i}T_{i}$ is the max of the hitting times, and with the uniform initial distribution the $T_{i}$’s have mean $\tau_{0}$. So if the $T_{i}$’s have approximately exponential distribution and are roughly independent of each other then we anticipate the limit result

Theorem 7.4 has already given us a condition for limit exponential distributions, and we shall build on this result to give (Theorem 7.9) conditions for (7.15) to hold.

The extreme value distribution (7.14) has transform

Classical probability theory (see Notes) says that to prove (7.15) it is enough to show that transforms converge, i.e. to show

But Matthews method, which previously we have used on expectations, can just as well be applied to transforms. By essentially the same argument as in Chapter 2 Theorem yyy, Matthews [258] obtained

Substituting into (7.17), and using the fact

we see that to establish (7.15) it suffices to prove that for arbitrary $j_{n}\neq i_{n}$ and for each fixed $-\infty<\theta<1$,

Proof. By hypothesis (a) and Theorem 7.4 (b,c), for arbitrary $j_{n}\neq i_{n}$ we have $P_{i_{n}}(T_{j_{n}}/\tau_{0}\in\cdot)\ \stackrel{d}{\rightarrow}\ \xi$. This implies (7.18) for $\theta\leq 0$, and also by Fatou’s lemma implies $\liminf_{n}E_{i_{n}}\exp(\theta T_{j_{n}}/\tau_{0})\geq\frac{1}{1-\theta}$for $0<\theta<1$. Thus it is sufficient to prove

The proof exploits some of our earlier general inequalities. Switch to continuous time. Fix $\beta>0$. By conditioning on the position at some fixed time $s$,

By Corollary 7.3 the max is attained by $x=i$, and so

We now apply some general inequalities. Chapter 4 yyy says $nP_{i}(X_{s}=i)\leq 1+n\exp(-s/\tau_{2})$. Writing $\alpha_{j}$ for the quasistationary distribution on $\{j\}^{c}$, Chapter 3 (yyy) implies $P_{\pi}(T_{j}>t)\leq\exp(-t/E_{\alpha_{j}}T_{j})$ and hence

But Chapter 3 Theorem yyy implies $E_{\alpha_{j}}T_{j}\leq\tau_{0}+\tau_{2}$. So setting $\beta=\theta/\tau_{0}$, these inequalities combine to give

But by hypothesis (b) we can choose $s=o(\tau_{0})=\Omega(\tau_{2}\log n)$ so that each of the first two terms in the bound tends to $1$, establishing (7.19). Finally, the effect of continuization is to change $C$ by at most $O(\sqrt{EC})$, so the asymptotics remain true in discrete time.

Remark. Presumably (c.f. Open Problem 7.6) the Theorem remains true without hypothesis (b).

In view of Chapter 6 yyy it is surprising that there is no obvious example to disprove

In our collection of examples in Chapter 5 of random walks on graphs, the examples with enough symmetry to fit into the present setting have in fact extra symmetry, enough to fit into the arc-transitive setting of section 7.2. So in a sense, working at the level of generality of symmetric reversible chains merely serves to illustrate what properties of chains depend only on this minimal level of symmetry. But let us point out a general construction. Suppose we have symmetric reversible chains $X^{(1)},\ldots,X^{(d)}$ on state spaces $I^{(1)},\ldots,I^{(d)}$. Fix constants $a_{1},\ldots,a_{d}$ with each $a_{i}>0$ and with $\sum_{i}a_{i}=1$. Then (c.f. Chapter 4 section yyy) we can define a “product chain” with state-space $I^{(1)}\times\ldots\times I^{(d)}$ and transition probabilities

This product chain is also symmetric reversible. But if the underlying chains have extra symmetry properties, these extra properties are typically lost when one passes to the product chain. Thus we have a general method of constructing symmetric reversible chains which lack extra structure. Example 7.14 below gives a case with distinct underlying components, and Example 7.11 gives a case with a non-uniform product. In general, writing $(\lambda^{(i)}_{u}:1\leq u\leq|I^{(i)}|)$ for the continuous-time eigenvalues of $X^{(i)}$, we have (Chapter 4 yyy) that the continuous-time eigenvalues of the product chain are

indexed by ${\bf u}=(u_{1},\ldots,u_{d})\in\{1,\ldots,|I^{(1)}|\}\times\ldots\times\{1,\ldots,|I^{(d)}|\}$. So in particular

and of course these parameters take the same values in discrete time.

Take $I=\{0,1\}^{d}$ and fix $0<a_{1}\leq a_{2}\leq\ldots\leq a_{d}$ with $\sum_{i}a_{i}=1$. Then the chain with transitions

is the weighted product of two-state chains. Most of the calculations for simple symmetric random walk on the $d$-cube done in Chapter 5 Example yyy extend to this example, with some increase of complexity. In particular,

In continuout time we still get the product form for the distribution at time $t$:

So in a sequence of continuous time chains with $d\rightarrow\infty$, the “separation” parameter $\tau^{(1)}_{1}$ of Chapter 3 section yyy is asymptotic to the solution $t$ of

More elaborate calculations can be done to study $\tau_{1}$ and the discrete-time version.

Chapter 2 yyy and Chapter 4 yyy discussed quantifications of notions of “time to approach stationarity” using variation distance. The emphasis in Chapter 4 yyy was on inequalities which hold up to universal constants. In the present context of symmetric reversible chains, one can seek to do sharper calculations. Thus for random walk on the $d$-cube (Chapter 5 Example yyy), with chances $1/(d+1)$ of making each possible step or staying still, writing $n=2^{d}$ and $c_{n}=\frac{1}{4}d\log d$, we have (as $n\rightarrow\infty$) not only the fact $\tau_{1}\sim c_{n}$ but also the stronger result

We call this the cutoff phenomenon, and when a sequence of chains satisfies (7.20) we say the sequence has “variation cutoff at $c_{n}$”. As mentioned at xxx, the general theory of Chapter 4 works smoothly using $\bar{d}(t)$, but in examples it is more natural to use $d(t)$, which we shall do in this chapter. Clearly, (7.20) implies the same result for $\bar{d}$ and implies $\tau_{1}\sim c_{n}$. Also, our convention in this chapter is to work in discrete time, whereas the Chapter 4 general theory worked more smoothly in continuous time. (Clearly (7.20) in discrete time implies the same result for the continuized chains, provided $c_{n}\rightarrow\infty$). Note that, in the context of symmetric reversible chains,

We also can discuss separation distance (Chapter 4 yyy) which in this context is

and introduce the analogous notion of separation threshold.

It turns out that these cut-offs automatically appear in sequences of chains defined by repeated products. An argument similar to the analysis of the $d$-cube (see [8] for a slightly different version) shows

xxx discuss upper bound lemma

xxx heuristics

xxx mention later examples

So far we have worked in the setting of symmetric reversible chains, and haven’t used any graph theory. We now specialize to the case of random walk on a vertex-transitive or Cayley graph $(\mbox{${\cal V}$},\mbox{${\cal E}$})$. As usual, we won’t write out all specializations of the previous results, but instead emphasize what extra we get from graph-theoretic arguments. Let $d$ be the degree of the graph.

Proof. The lower bounds are specializations of Lemma 7.2(i), i.e. of Chapter 6 xxx. For the upper bound in (ii),

Rearrange.

xxx mention general lower bound $\tau_{0}\geq(1-o(1))nd/(d-2)$ via tree-cover.

It is known (xxx ref) that a Cayley graph of degree $d$ is $d$-edge-connected, and so Chapter 6 Proposition yyy gives

where $\psi(d)/d\approx\sqrt{2/d}$.

Consider $Z_{m}\times Z_{2}$ with generators $(1,0),(-1,0),(0,1)$. The figure illustrates the case $m=4$.

Let’s calculate $E_{00}T_{10}$ using the resistance interpretation. Put unit voltage at $10$ and zero voltage at $00$, and let $a_{i}$ be the voltage at $i0$. By symmetry the voltage at $i1$ is $1-a_{i}$, so we get the equations

with $a_{0}=a_{m}=0$. But this is just a linear difference equation, and a brief calculation gives the solution

where $\theta=2-\sqrt{3}$. The current flow is $1+2a_{1}$, so the effective resistance is $r=(1+2a_{1})^{-1}$. The commute interpretation of resistance gives $2E_{00}T_{01}=3nr$, and so

where $n=2m$ is the number of vertices. In particular,

Using the averaging property (7.21)

Turning from hitting times to mixing times, recall the Cheeger constant

where $A$ is a proper subset of vertices and

For random walk on a Cayley graph one can use simple “averaging” ideas to bound $c(A)$. This is Proposition 7.15 below. The result in fact extends to vertex-transitive graphs by a covering graph argument - see xxx.

Consider a $n$-vertex Cayley graph with degree $d$ and generators $\mbox{${\cal G}$}=\{g_{1},\ldots,g_{d}\}$, where $g\in\mbox{${\cal G}$}$ implies $g^{-1}\in\mbox{${\cal G}$}$. Then

where $Ag=\{ag:a\in A\}$. Lower bounding the sum by its maximal term, we get

Note that $\sup_{A}\rho(A)$ is bounded by $\Delta$ but not in general by $\Delta/2$ (consider the cycle), so that (ii) implies (i) with an extra factor of $2$. Part (i) is from Aldous [16] and (ii) is from Babai [36].

Proof. (i) Fix $A$. Because

there exists some $v\in\mbox{${\cal V}$}$ such that $|A\cap Av|\leq|A|^{2}/n$, implying

We can write $v=g_{1}g_{2}\ldots g_{\delta}$ for some sequence of generators $(g_{i})$ and some $\delta\leq\Delta$, and

So there exists $g\in\mbox{${\cal G}$}$ with $|Ag\setminus A|\geq\frac{1}{\Delta}\times|A||A^{c}|/n$, and so (i) follows from (7.22). For part (ii), fix $A$ with $|A|\leq n/2$, write $\rho=\rho(A)$ and suppose

Fix $v$ with $\max_{w\in A}d(w,v)=\rho$. Since $|Ag\setminus A|<\frac{1}{4\rho}|A|$ and

we have by induction