A graph is called distance-transitive if for each $4$-tuple $v_{1},w_{1},v_{2},w_{2}$ with $d(v_{1},w_{1})=d(v_{2},w_{2})$ there exists an automorphism $\gamma$ such that $\gamma(v_{1})=w_{1},\gamma(v_{2})=w_{2}$. Associated with such a graph of diameter $\Delta$ are the intersection numbers $(a_{i},b_{i},c_{i};0\leq i\leq\Delta)$ defined as follows. For each $i$ choose $(v,w)$ with $d(v,w)=i$, and define

$w$ | $\displaystyle i-1$ | $\displaystyle\mbox{ from }v$ | ||

$w$ | $\displaystyle i$ | $\displaystyle\mbox{ from }v$ | ||

$w$ | $\displaystyle i+1$ | $\displaystyle\mbox{ from }v.$ |

The distance-transitive property ensures that $(a_{i},b_{i},c_{i})$ does not depend on the choice of $(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 $(X_{t})$ on a distance-regular graph started at $v_{0}$, and define $D_{t}=d(v_{0},X_{t})$. Then $(D_{t})$ is itself a Markov chain on states $\{0,1,\ldots,\Delta\}$, and is in fact the birth-and-death chain with transition probabilities

$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 $t$-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.

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

$n_{i}=\prod_{j=1}^{i}\frac{b_{j-1}}{c_{j}};\ 0\leq i\leq\Delta.$ |

The chain $D_{t}$ has stationary distribution

$\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 $D_{t}$ is random walk on a weighted linear graph, where the weight $w_{i}$ on edge $(i-1,i)$ is

$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=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

$E_{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 $D_{t}$. Clearly $h(\cdot)$ is strictly increasing. Chapter 5 yyy gives the formula

$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

$\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

$\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

$\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(\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,

c-subsets of a d-set.

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

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

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

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

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.

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

Any brief look at examples suggests

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

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

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

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML