Example 7.14 shows that random walk on a Cayley graph does not necessarily have the property that is the same for all edges . It is natural to consider some stronger symmetry condition which does imply this property. Call a graph arc-transitive if for each -tuple of vertices such that and are edges, there exists an automorphism such that . Arc-transitivity is stronger than vertex-transitivity, and immediately implies that is constant over edges .
On a -vertex arc-transitive graph,
(i) for each edge .
(ii) for all .
Proof. (i) follows from . For (ii), write for the set of neighbors of . Then
and .
In particular, , which gives the following bounds on mean cover time . The first assertion uses Matthews method for expectations (Chapter 2 yyy) and the second follows from Theorem 7.9.
On a -vertex arc-transitive graph, . And if and then
(7.26) |
Note that the lower bound 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 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
Thus on the -cube (Chapter 5 yyy) and so
These examples are formally random flights on the permutation group, though we shall describe them informally as models for random shuffles of a -card deck. Write for the configuration of the deck after shuffles, and write for the position of card after shuffles. In most examples (and all those we discuss) is itself a Markov chain on . 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 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 has transition probabilities
probability | ||||
probability |
This is essentially random walk on the complete -graph (precisely: the continuized chains are deterministic time-changes of each other) and it is easy to deduce that has relaxation time . So by the contraction principle xxx the card-shuffling process has , and group representation methods show
(7.27) |
Since the chance of being in the initial state after step is and after steps in , the local transience heuristic (7.10) suggests
(7.28) |
which can be verified by group representation methods (see Flatto et al [152]). The general bound on in terms of gives only . In fact group group representation methods ([123]) show
(7.29) |
Card-shuffling via random adjacent transpositions.
The model is
With probability do nothing. Otherwise, choose one pair of adjacent cards (counting the top and bottom cards as adjacent), with probability for each pair, and interchange them.
The chain has transition probabilities
with counted modulo . This chain is (in continuous time) just a time-change of random walk on the -cycle, so has relaxation time
So by the contraction principle xxx the card-shuffling process has , and (xxx unpublished Diaconis work) in fact
A coupling argument which we shall present in Chapter xxx gives an upper bound and (xxx unpublished Diaconis work) in fact
The local transience heuristic (7.10) again suggests
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 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 ) is not arc-transitive.
Writing for distances in the graph and writing
it is easy to check that . Comparing the present chain with the “random transpositions” chain (Example 7.21), denoted by , Theorem 7.16 implies
Since we get
This is Example yyy from Chapter 5, with vertices, and is clearly arc-transitive. Consider asymptotics as for fixed. We studied mean hitting times in this example in Chapter 5. Here , so we cannot apply Corollary 7.20. For the graph is just the -cycle, treated in Chapter 6 yyy. For , Chapter 5 yyy gave
where is Euclidean distance on the torus, i.e.
So has the asymptotic upper bound . Now if we apply the subset form of Matthews method (Chapter 6 yyy) to the subset
(7.30) |
then we get a lower bound for asymptotic to
By taking slowly, this agrees with the upper bound, so we find
On the -dimensional torus with ,
Perhaps surprisingly, the case 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 – recall from Chapter 6 yyy that another example with this property, the balanced tree, is also hard. Anyway, for the case the calculations in Chapter 5 yyy gave
This leads to the upper bound in Corollary 7.25 below. For the lower bound, we repeat the argument using a subset of the form (7.30) with , and obtain a lower bound asymptotic to
The optimal choice is , leading to the lower bound below.
On the -dimensional torus ,
Lawler [222] has improved the constant in the lower bound to – see Notes. It is widely believed that the upper bound is in fact the limit.
Prove that, on the -dimensional torus ,
The usual distributional limit
certainly fails in (see Chapter 6 yyy). It has not been studied in , but the natural conjecture it that it is true for but false in . Note that (by Chapter 6 yyy) the weaker concentration result
holds for all .
In Chapter 6 we discussed upper bounds on parameters for regular graphs. One can’t essentially improve these bounds by imposing symmetry conditions, because the bounds are attained (up to constants) by the -cycles. But what if we exclude the -cycles? Example 7.14 shows that one can invent vertex-transitive graphs which mimic the -cycle, but it is not clear whether such arc-transitive graphs exist. So perhaps the next-worst arc-transitive graph is .
Is it true that, over arc-transitive graphs excluding the -cycles, , and ?
Recall that the Cayley graph associated with a set of generators of a group has edges
where we assume satisfies
(i) implies .
To ensure that the graph is arc-transitive, it is sufficient to add
the condition
(ii) for each pair in , there
exists a group automorphism such that
and
.
In words, “the stabilizer acts transitively on ”.
This is essentially the general case: see [71] Prop. A.3.1.
As a related concept, recall that elements of a group are conjugate if for some group element . 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 one can consider the uniform distribution on and then consider the random flight with step distribution . Such random flights fit into the framework of section 7.2, and Example 7.21 and the torus 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.