7.3 Distance-regular graphs

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 $n_{i}$ be the number of states at distance $i$ from ${\bf 0}$. The number of edges with one end at distance $i$ and the other at distance $i+1$ is $n_{i}b_{i}=n_{i+1}c_{i+1}$, leading to the formula

The chain $D_{t}$ has stationary distribution

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

and total weight $w=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 $(D_{t})$ by

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

And Chapter 5 yyy gives the last equality in

Finally, Chapter 5 yyy gives

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

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

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

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 $d$-cube also was treated in Chapter 5. Closely related to the $d$-cube is a model arising in several contexts under different names,

The model has parameters $(c,d)$, where $1\leq c\leq d-1$. Formally, we have random walk on the distance-transitive graph whose vertices are the $\frac{d!}{c!(d-c)!}$ $c$-element subsets $A\subset\{1,2,\ldots,d\}$, and where $(A,A^{\prime})$ is an edge iff $|A\triangle A^{\prime}|=2$. More vividly, $d$ balls $\{1,2,\ldots,d\}$ are distributed between a left urn and a right urn, with $c$ 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 $d$-cube. See [121, 127] and [123] Chapter 3F for details on convergence to equilibrium and [109] for hitting and cover times.

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).

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.

Any brief look at examples suggests

Of course this would imply $\tau^{*}=O(n)$ and $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 $\max_{i,j}E_{i}T_{j}/(n-1)$, and found the value $195/101$ taken on the cubic graph with $102$ vertices, and outlined an argument that this may be the max over known distance-regular graphs.

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

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 $(s_{0},s_{1},\ldots,s_{\Delta})$ for the step-length $S$, and each step moves to a random vertex at distance $S$ from the previous vertex. Precisely, it is the chain with transition probabilities

The notion of isotropic random flight also makes sense in continuous space. For an isotropic random flight in $R^{d}$, the steps have some arbitrary specified random length $S$ and a direction $\theta$ which is uniform and independent of $S$. A similar definition can be made on the $d$-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.