Example 7.14 shows that random walk on a Cayley graph does not necessarily have the property that $E_{v}T_{w}$ is the same for all edges $(v,w)$. It is natural to consider some stronger symmetry condition which does imply this property. Call a graph arc-transitive if for each $4$-tuple of vertices $(v_{1},w_{1},v_{2},w_{2})$ such that $(v_{1},w_{1})$ and $(v_{2},w_{2})$ are edges, there exists an automorphism $\gamma$ such that $\gamma(v_{1})=w_{1},\gamma(v_{2})=w_{2}$. Arc-transitivity is stronger than vertex-transitivity, and immediately implies that $E_{v}T_{w}$ is constant over edges $(v,w)$.

On a $n$-vertex arc-transitive graph,

(i) $E_{v}T_{w}=n-1$ for each edge $(v,w)$.

(ii) $E_{v}T_{w}\geq n-2+d(v,w)$ for all $w\neq v$.

Proof. (i) follows from $E_{v}T^{+}_{v}=n$. For (ii), write $N(w)$ for the set of neighbors of $w$. Then

$E_{v}T_{w}=E_{v}T_{N(w)}+(n-1)$ |

and $T_{N(w)}\geq d(v,N(w))=d(v,w)-1$.

In particular, $\min_{w\neq v}E_{v}T_{w}=n-1$, which gives the following bounds on mean cover time $EC$. The first assertion uses Matthews method for expectations (Chapter 2 yyy) and the second follows from Theorem 7.9.

On a $n$-vertex arc-transitive graph, $EC\geq(n-1)h_{n-1}$. And if $\tau_{0}/n\rightarrow 1$ and $\tau_{2}=o(n/\log n)$ then

$\frac{C-\tau_{0}\log n}{\tau_{0}}\ \stackrel{d}{\rightarrow}\ \eta$ | (7.26) |

Note that the lower bound $(n-1)h_{n-1}$ is attained on the complete graph. It is not known whether this exact lower bound remains true for vertex-transitive graphs, but this would be a consequence of Chapter 6 Open Problem yyy. Note also that by xxx the hypothesis $\tau_{0}/n\rightarrow 1$ can only hold if the degrees tend to infinity.

Corollary 7.20 provides easily-checkable conditions for the distributional limit for cover times, in examples with ample symmetry, such as the card-shuffling examples in the next section. Note that

$(\ref{Cext8})\mbox{ and }\tau_{0}=n\left(1+\frac{b+o(1)}{\log n}\right)\mbox{ % imply }\frac{C-n\log n-bn}{n}\ \stackrel{d}{\rightarrow}\ \eta.$ |

Thus on the $d$-cube (Chapter 5 yyy) $\tau_{0}=n\left(1+\frac{1+o(1)}{d}\right)=n\left(1+\frac{\log 2+o(1)}{\log n}\right)$ and so

$\frac{C-n\log n-n\log 2}{n}\ \stackrel{d}{\rightarrow}\ \eta.$ |

These examples are formally random flights on the permutation group, though we shall describe them informally as models for random shuffles of a $m$-card deck. Write $X_{t}$ for the configuration of the deck after $t$ shuffles, and write $Y_{t}=f_{1}(X_{t})$ for the position of card $1$ after $t$ shuffles. In most examples (and all those we discuss) $Y_{t}$ is itself a Markov chain on $\{1,2,\ldots,m\}$. Example 7.21, mentioned in Chapter 1 xxx, has become the prototype for use of group representation methods.

Card-shuffling via random transpositions.

The model is

Make two independent uniform choices of cards, and interchange the positions of the two cards.

With chance $1/m$ the same card is chosen twice, so the “interchange” has no effect. This model was studied by Diaconis and Shahshahani [120], and more concisely in the book Diaconis [123] Chapter 3D. The chain $Y_{t}$ has transition probabilities

$\displaystyle i\rightarrow j$ | probability | $\displaystyle 2/m^{2},\ j\neq i$ | ||

$\displaystyle i\rightarrow i$ | probability | $\displaystyle 1-\frac{2(m-1)}{m^{2}}$ |

This is essentially random walk on the complete $m$-graph (precisely: the continuized chains are deterministic time-changes of each other) and it is easy to deduce that $(Y_{t})$ has relaxation time $m/2$. So by the contraction principle xxx the card-shuffling process has $\tau_{2}\geq m/2$, and group representation methods show

$\tau_{2}=m/2.$ | (7.27) |

Since the chance of being in the initial state after $1$ step is $1/m$ and after $2$ steps in $O(1/m^{2})$, the local transience heuristic (7.10) suggests

$\tau_{0}=m!(1+1/m+O(1/m^{2}))$ | (7.28) |

which can be verified by group representation methods (see Flatto et al [152]). The general bound on $\tau_{1}$ in terms of $\tau_{2}$ gives only $\tau_{1}=O(\tau_{2}\log m!)=O(m^{2}\log m)$. In fact group group representation methods ([123]) show

$\mbox{ there is a variation cutoff at }\frac{1}{2}m\log m.$ | (7.29) |

Card-shuffling via random adjacent transpositions.

The model is

With probability $1/(m+1)$ do nothing. Otherwise, choose one pair of adjacent cards (counting the top and bottom cards as adjacent), with probability $1/(m+1)$ for each pair, and interchange them.

The chain $Y_{t}$ has transition probabilities

$\displaystyle i\rightarrow$ | $\displaystyle i+1$ | $\displaystyle\mbox{ probability }1/(m+1)$ | ||

$\displaystyle i\rightarrow$ | $\displaystyle i-1$ | $\displaystyle\mbox{ probability }1/(m+1)$ | ||

$\displaystyle i\rightarrow$ | $\displaystyle i$ | $\displaystyle\mbox{ probability }(m-1)/(m+1)$ |

with $i\pm 1$ counted modulo $m$. This chain is (in continuous time) just a time-change of random walk on the $m$-cycle, so has relaxation time

$a(m)\equiv\frac{m+1}{2}\frac{1}{1-\cos(2\pi/m)}\sim\frac{m^{3}}{4\pi^{2}}.$ |

So by the contraction principle xxx the card-shuffling process has $\tau_{2}\geq a(m)$, and (xxx unpublished Diaconis work) in fact

$\tau_{2}=a(m)\sim m^{3}/4\pi^{2}.$ |

A coupling argument which we shall present in Chapter xxx gives an upper bound $\tau_{1}=O(m^{3}\log m)$ and (xxx unpublished Diaconis work) in fact

$\tau_{1}=\Theta(m^{3}\log m).$ |

The local transience heuristic (7.10) again suggests

$\tau_{0}=m!(1+1/m+O(1/m^{2}))$ |

but this has not been studied rigorously.

Many variants of these examples have been studied, and we will mention a generalization of Examples 7.21 and 7.22 in Chapter xxx. Here is another example, from Diaconis and Saloff-Coste [115], which illustrates the use of comparison arguments.

A slow card-shuffling scheme.

The model is: with probability $1/3$ each, either

(i) interchange the top two cards

(ii) move the top card to the bottom

(iii) move the bottom card to the top.

This process is random walk on a certain Cayley graph, which
(for $m\geq 3$) is not arc-transitive.
Writing $d$ for distances in the graph and writing

$\beta=\max(d(\sigma,\mbox{id}):\sigma\mbox{ a transposition }),$ |

it is easy to check that $\beta\leq 3m$. Comparing the present chain with the “random transpositions” chain (Example 7.21), denoted by $\tilde{\ }$, Theorem 7.16 implies

$\frac{\tau_{2}}{\tilde{\tau_{2}}}\leq 3\beta^{2}.$ |

Since $\tilde{\tau_{2}}=m/2$ we get

$\tau_{2}\leq\frac{27m^{3}}{2}.$ |

This is Example yyy from Chapter 5, with $n=N^{d}$ vertices, and is clearly arc-transitive. Consider asymptotics as $N\rightarrow\infty$ for $d$ fixed. We studied mean hitting times in this example in Chapter 5. Here $\tau_{0}/n\not\rightarrow 1$, so we cannot apply Corollary 7.20. For $d=1$ the graph is just the $d$-cycle, treated in Chapter 6 yyy. For $d\geq 3$, Chapter 5 yyy gave

$E_{0}T_{i}\sim nR_{d}\mbox{ as }N\rightarrow\infty,\ |i|\rightarrow\infty$ |

where $|i|$ is Euclidean distance on the torus, i.e.

$|(i_{1},\ldots,i_{d})|^{2}=\sum_{u=1}^{d}(\min(i_{u},N-i_{u}))^{2}.$ |

So $EC$ has the asymptotic upper bound $R_{d}n\log n$. Now if we apply the subset form of Matthews method (Chapter 6 yyy) to the subset

$A=\{(j_{1}m,\ldots,j_{d}m):1\leq j_{i}\leq\frac{N}{m}\}$ | (7.30) |

then we get a lower bound for $EC$ asymptotic to

$\log|A|\times nR_{d}.$ |

By taking $m=m(n)\uparrow\infty$ slowly, this agrees with the upper bound, so we find

On the $d$-dimensional torus with $d\geq 3$,

$EC\sim R_{d}n\log n.$ |

Perhaps surprisingly, the case $d=2$ turns out to be the hardest of all explicit graphs for the purposes of estimating cover times. (Recall this case is the white screen problem Chapter 1 xxx.) Loosely, the difficulty is caused by the fact that $\tau_{2}=\Theta(n\log n)$ – recall from Chapter 6 yyy that another example with this property, the balanced tree, is also hard. Anyway, for the case $d=2$ the calculations in Chapter 5 yyy gave

$E_{0}T_{i}\sim n\left(\frac{2}{\pi}\log|i|\ +O(1)\right).$ |

This leads to the upper bound in Corollary 7.25 below. For the lower bound, we repeat the $d\geq 3$ argument using a subset of the form (7.30) with $m\rightarrow\infty$, and obtain a lower bound asymptotic to

$\frac{2}{\pi}\log m\ \times\ \log(n^{2}/m^{2}).$ |

The optimal choice is $m\sim n^{1/2}$, leading to the lower bound below.

On the $2$-dimensional torus $Z^{2}_{N}$,

$\left(\frac{1}{4\pi}-o(1)\right)n\log^{2}n\leq EC\leq\left(\frac{1}{\pi}+o(1)% \right)n\log^{2}n.$ |

Lawler [222] has improved the constant in the lower bound to $\frac{1}{2\pi}$ – see Notes. It is widely believed that the upper bound is in fact the limit.

Prove that, on the $2$-dimensional torus $Z^{2}_{N}$,

$EC\sim\frac{1}{\pi}\ n\log^{2}n.$ |

The usual distributional limit

$\frac{C-\tau_{0}\log n}{\tau_{0}}\ \stackrel{d}{\rightarrow}\ \eta$ |

certainly fails in $d=1$ (see Chapter 6 yyy). It has not been studied in $d\geq 2$, but the natural conjecture it that it is true for $d\geq 3$ but false in $d=2$. Note that (by Chapter 6 yyy) the weaker concentration result

$C/EC\ \stackrel{d}{\rightarrow}\ 1$ |

holds for all $d\geq 2$.

In Chapter 6 we discussed upper bounds on parameters $\tau$ for regular graphs. One can’t essentially improve these bounds by imposing symmetry conditions, because the bounds are attained (up to constants) by the $n$-cycles. But what if we exclude the $n$-cycles? Example 7.14 shows that one can invent vertex-transitive graphs which mimic the $n$-cycle, but it is not clear whether such arc-transitive graphs exist. So perhaps the next-worst arc-transitive graph is $Z_{m}^{2}$.

Is it true that, over arc-transitive graphs excluding the $n$-cycles, $\tau^{*}=O(n\log n)$, $\tau_{2}=O(n)$ and $\frac{\tau^{*}}{2\tau_{0}}=1+o(1)$?

Recall that the Cayley graph associated with a set ${\cal G}$ of generators of a group $I$ has edges

$\{(v,vg);v\in I,g\in\mbox{${\cal G}$}\}$ |

where we assume ${\cal G}$ satisfies

(i) $g\in\mbox{${\cal G}$}$ implies $g^{-1}\in\mbox{${\cal G}$}$.

To ensure that the graph is arc-transitive, it is sufficient to add
the condition

(ii) for each pair $g_{1},g_{2}$ in ${\cal G}$, there
exists a group automorphism $\gamma$ such that
$\gamma({\rm id})={\rm id}$ and
$\gamma(g_{1})=g_{2}$.

In words, “the stabilizer acts transitively on ${\cal G}$”.
This is essentially the general case: see [71] Prop. A.3.1.

As a related concept, recall that elements $x,y$ of a group $I$ are conjugate if $x=g^{-1}yg$ for some group element $g$. This is an equivalence relation which therefore defines conjugacy classes. It is easy to check that a conjugacy class must satisfy condition (ii). Given a conjugacy class $C$ one can consider the uniform distribution $\mu_{C}$ on $C$ and then consider the random flight with step distribution $\mu_{C}$. Such random flights fit into the framework of section 7.2, and Example 7.21 and the torus $Z^{d}_{N}$ are of this form. On the other hand, Example 7.22 satisfies (i) and (ii) but are not random flights with steps uniform on a conjugacy class.

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