7 Symmetric Graphs and Chains (January 31, 1994)

7.3 Distance-regular graphs

A graph is called distance-transitive if for each 44-tuple v1,w1,v2,w2v_{1},w_{1},v_{2},w_{2} with d(v1,w1)=d(v2,w2)d(v_{1},w_{1})=d(v_{2},w_{2}) there exists an automorphism γ\gamma such that γ(v1)=w1,γ(v2)=w2\gamma(v_{1})=w_{1},\gamma(v_{2})=w_{2}. Associated with such a graph of diameter Δ\Delta are the intersection numbers (ai,bi,ci;0iΔ)(a_{i},b_{i},c_{i};0\leq i\leq\Delta) defined as follows. For each ii choose (v,w)(v,w) with d(v,w)=id(v,w)=i, and define

ci= number of neighbors of ww at distance\displaystyle c_{i}=\mbox{ number of neighbors of $w$ at distance } i-1\displaystyle i-1 from v\displaystyle\mbox{ from }v
ai= number of neighbors of ww at distance\displaystyle a_{i}=\mbox{ number of neighbors of $w$ at distance } i\displaystyle i from v\displaystyle\mbox{ from }v
bi= number of neighbors of ww at distance\displaystyle b_{i}=\mbox{ number of neighbors of $w$ at distance } i+1\displaystyle i+1 from v.\displaystyle\mbox{ from }v.

The distance-transitive property ensures that (ai,bi,ci)(a_{i},b_{i},c_{i}) does not depend on the choice of (v,w)(v,w). A graph for which such intersection numbers exist is called distance-regular, and distance-regularity turns out to be strictly weaker than distance-transitivity. An encyclopedic treatment of such graphs has been given by Brouwer et al [71]. The bottom line is that there is almost a complete characterization (i.e. list of families and sporadic examples) of distance-regular graphs. Anticipating a future completion of the characterization, one could seek to prove inequalities for random walks on distance-regular graphs by simply doing explicit calculations with all the examples, but (to quote Biggs [49]) “this would certainly not find a place in The Erdos Book of ideal proofs”. Instead, we shall just mention some properties of random walk which follow easily from the definitions.

Consider random walk (Xt)(X_{t}) on a distance-regular graph started at v0v_{0}, and define Dt=d(v0,Xt)D_{t}=d(v_{0},X_{t}). Then (Dt)(D_{t}) is itself a Markov chain on states {0,1,,Δ}\{0,1,\ldots,\Delta\}, and is in fact the birth-and-death chain with transition probabilities

pi,i-1=ci/r,  pi,i=ai/r,  pi,i+1=bi/r.p_{i,i-1}=c_{i}/r,\ p_{i,i}=a_{i}/r,\ p_{i,i+1}=b_{i}/r.

xxx b-and-d with holds

Finding exact tt-step transition probabilities is tantamount to finding the orthogonal polynomials associated with the distance-regular graph – references to the latter topic can be found in [71], but we shall not pursue it.

7.3.1 Exact formulas

A large number of exact formulas can be derived by combining the standard results for birth-and-death chains in Chapter 5 section yyy with the standard renewal-theoretic identities of Chapter 2 section yyy. We present only the basic ones.

Fix a state 𝟎{\bf 0} in a distance-regular graph. Let nin_{i} be the number of states at distance ii from 𝟎{\bf 0}. The number of edges with one end at distance ii and the other at distance i+1i+1 is nibi=ni+1ci+1n_{i}b_{i}=n_{i+1}c_{i+1}, leading to the formula

ni=j=1ibj-1cj; 0iΔ.n_{i}=\prod_{j=1}^{i}\frac{b_{j-1}}{c_{j}};\ 0\leq i\leq\Delta.

The chain DtD_{t} has stationary distribution

ρi=ni/n=n-1j=1ibj-1cj; 0iΔ.\rho_{i}=n_{i}/n=n^{-1}\prod_{j=1}^{i}\frac{b_{j-1}}{c_{j}};\ 0\leq i\leq\Delta.

Switching to the notation of Chapter 5 yyy, the chain DtD_{t} is random walk on a weighted linear graph, where the weight wiw_{i} on edge (i-1,i)(i-1,i) is

wi=ni-1bi-12n=nici2n, 1iΔw_{i}=\frac{n_{i-1}b_{i-1}}{2n}=\frac{n_{i}c_{i}}{2n},\ 1\leq i\leq\Delta

and total weight w=1w=1. This graph may have self-loops, but they don’t affect the formulas. Clearly hitting times on the graph are related to hitting times of (Dt)(D_{t}) by

EvTx=h(d(v,x)) , where h(i)E~iT0E_{v}T_{x}=h(d(v,x))\mbox{ , where }h(i)\equiv\tilde{E}_{i}T_{0} (7.31)

and where we write ~\tilde{\ } to refer to expectations for DtD_{t}. Clearly h()h(\cdot) is strictly increasing. Chapter 5 yyy gives the formula

h(i)=i+2j=1ii=j+1Δwiwj-1.h(i)=i+2\sum_{j=1}^{i}\sum_{i=j+1}^{\Delta}w_{i}w_{j}^{-1}. (7.32)

And Chapter 5 yyy gives the last equality in

τ0=EπT𝟎=E~ρT0=12i=1Δwi-1(jiρj)2.\tau_{0}=E_{\pi}T_{\bf 0}=\tilde{E}_{\rho}T_{0}=\frac{1}{2}\sum_{i=1}^{\Delta}% w^{-1}_{i}(\sum_{j\geq i}\rho_{j})^{2}. (7.33)

Finally, Chapter 5 yyy gives

E~0TΔ+E~ΔT0=i=1Δ1/wi.\tilde{E}_{0}T_{\Delta}+\tilde{E}_{\Delta}T_{0}=\sum_{i=1}^{\Delta}1/w_{i}. (7.34)

Thus if the graph has the property that there exists a unique vertex 𝟎*{\bf 0}^{*} at distance Δ\Delta from 𝟎{\bf 0}, then we can pull back to the graph to get

τ*2=maxxvExTv=E𝟎T𝟎*=12i=1Δ1/wi.\frac{\tau^{*}}{2}=\max_{x\neq v}E_{x}T_{v}=E_{{\bf 0}}T_{{\bf 0}^{*}}=\frac{1% }{2}\sum_{i=1}^{\Delta}1/w_{i}. (7.35)

If the graph lacks that property, we can use (7.31) to calculate h(Δ)h(\Delta).

The general identities of Chapter 3 yyy can now be used to give formulas for quantities such as Px(Ty<Tz)P_{x}(T_{y}<T_{z}) or ExE_{x} (number of visits to yy before TzT_{z}).

7.3.2 Examples

Many treatments of random walk on sporadic examples such as regular polyhedra have been given, e.g. [225, 226, 275, 319, 320, 330, 331], so I shall not repeat them here. Of infinite families, the complete graph was discussed in Chapter 5 yyy, and the complete bipartite graph is very similar. The dd-cube also was treated in Chapter 5. Closely related to the dd-cube is a model arising in several contexts under different names,

Example 7.28

c-subsets of a d-set.

The model has parameters (c,d)(c,d), where 1cd-11\leq c\leq d-1. Formally, we have random walk on the distance-transitive graph whose vertices are the d!c!(d-c)!\frac{d!}{c!(d-c)!} cc-element subsets A{1,2,,d}A\subset\{1,2,\ldots,d\}, and where (A,A)(A,A^{\prime}) is an edge iff |AA|=2|A\triangle A^{\prime}|=2. More vividly, dd balls {1,2,,d}\{1,2,\ldots,d\} are distributed between a left urn and a right urn, with cc balls in the left urn, and at each stage one ball is picked at random from each urn, and the two picked balls are interchanged. The induced birth-and-death chain is often called the Bernouilli-Laplace diffusion model. The analysis is very similar to that of the dd-cube. See [121, 127] and [123] Chapter 3F for details on convergence to equilibrium and [109] for hitting and cover times.

7.3.3 Monotonicity properties

The one result about random walk on distance-regular graphs we wish to highlight is the monotonicity property given in Proposition 7.29 below. Part (ii) can be viewed as a strengthening of the monotonicity property for mean hitting times (by integrating over time and using the formula relating mean hitting times to the fundamental matrix).

Proposition 7.29

For random walk (Xt)(X_{t}) on a distance-regular graph in continuous time, Pv(Xt=w)=q(t,d(v,w))P_{v}(X_{t}=w)=q(t,d(v,w)), where the function dq(t,d)d\rightarrow q(t,d) satisfies

(i) dq(t,d)d\rightarrow q(t,d) in non-increasing, for fixed tt.

(ii) q(t,d)/q(t,0)q(t,d)/q(t,0) in non-decreasing in tt, for fixed dd.

xxx proof – coupling – defer to coupling Chapter ??

Proposition 7.29 is a simple example of what I call a “geometric” result about a random walk. Corollary 7.3 gave a much weaker result in a more general setting. It’s natural to ask for intermediate results, e.g.

Open Problem 7.30

Does random walk on an arc-transitive graph have some monotonicity property stronger than that of Corollary 7.3?

7.3.4 Extremal distance-regular graphs

Any brief look at examples suggests

Open Problem 7.31

Prove that, over distance-regular graphs excluding the nn-cycles, τ0=O(n)\tau_{0}=O(n).

Of course this would imply τ*=O(n)\tau^{*}=O(n) and EC=O(nlogn)EC=O(n\log n). As mentioned earlier, one can try to tackle problems like this by using the list of known distance-regular graphs in [71]. Biggs [49] considered the essentially equivalent problem of the maximum value of maxi,jEiTj/(n-1)\max_{i,j}E_{i}T_{j}/(n-1), and found the value 195/101195/101 taken on the cubic graph with 102102 vertices, and outlined an argument that this may be the max over known distance-regular graphs.

xxx in same setting is τ2=O(logn)\tau_{2}=O(\log n)?

7.3.5 Gelfand pairs and isotropic flights

On a distance-regular graph, a natural generalization of our nearest-neighbor random walks is to isotropic random flight on the graph. Here one specifies a probability distribution (s0,s1,,sΔ)(s_{0},s_{1},\ldots,s_{\Delta}) for the step-length SS, and each step moves to a random vertex at distance SS from the previous vertex. Precisely, it is the chain with transition probabilities

p(v,w)=sd(v,w)nd(v,w).p(v,w)=\frac{s_{d(v,w)}}{n_{d(v,w)}}. (7.36)

The notion of isotropic random flight also makes sense in continuous space. For an isotropic random flight in RdR^{d}, the steps have some arbitrary specified random length SS and a direction θ\theta which is uniform and independent of SS. A similar definition can be made on the dd-dimensional sphere. The abstract notion which captures distance-regular graphs and their continuous analogs is a Gelfand pair. Isotropic random flights on Gelfand pairs can be studied in great detail by analytic methods. Brief accounts can be found in Letac [227, 228] and Diaconis [123] Chapter 3F, which contains an extensive annotated bibliography.