7.4 Notes on Chapter 7

Diaconis [123] Chapter 3 discusses random walks on groups, emphasizing use of the upper bound lemma to establish bounds on $\tau_{1}$ and $d(t)$, and containing extensive references to previous work using group-theoretic methods. We have only mentioned reversible examples, but many natural non-reversible examples can also be handled by group representation methods. Also, in Example 7.21 and related examples, group representation methods give stronger information about $d(t)$ then we have quoted.

Elementary properties of hitting and cover times on graphs with symmetry structure have been noted by many authors, a particularly comprehensive treatment being given in the Ph.D. thesis Sbihi [306]. Less extensive treatments and specific elementary results can be found in many of the papers cited later, plus [274, 330, 331]

Section 7.1. The phrase “random flight” is classically used for $R^{d}$. I have used it (as did Takacs [319, 320]) in place of “random walk’ to emphasize it is not necessarily a nearest-neighbor random walk.

Section 7.1.3. Other elementary facts about symmetric reversible chains are

Chapter 6 yyy showed that on any regular graph, $\max_{i,j}E_{i}T_{j}\leq 3n^{2}$. On a vertex-transitive graph the constant “3” can be improved to “2”, by an unpublished argument of the author, but this is still far from the natural conjecture of $1/4$.

Section 7.1.4. Another curious result from [18]is that for a symmetric reversible chain the first passage time cannot be concentrated around its mean:

Section 7.1.5. Before Matthews method was available, a result like Corollary 7.5 (c) required a lot of work – see Aldous [14] for a result in the setting of non-reversible random flight on a group. The present version of Corollary 7.5 (c) is a slight polishing of ideas in Zuckerman [343] section 6.

The fact that (7.17) implies (7.15) is a slight variation of the usual textbook forms of the continuity theorem ([133] 2.3.4 and 2.3.11) for Fourier and Laplace transforms. By the same argument as therein, it is enough for the limit transform to be continuous at $\theta=0$, which holds in our setting.

Matthews [255, 258] introduced Proposition 7.8 and used it to obtain the limiting cover time distribution for the $d$-cube and for card-shuffling examples. Devroye and Sbihi [109] applied it to generalized hypercubes and to Example 7.28. Our implementation in Theorem 7.9 and Corollary 7.20 reduces the need for ad hoc calculations in particular examples.

Section LABEL:PC-1. Example 7.11 has been studied in the reliability literature (e.g. [212]) from the viewpoint of the exponential approximation for hitting times.

Section 7.1.7. The factor of $2$ difference between the variation and separation cutoffs which appears in Lemma 7.12 is the largest possible – see Aldous and Diaconis [8].

Section 7.1.8. xxx walk-regular example – McKay paper.

Section 7.1.9. Diaconis and Saloff-Coste [115] give many other applications of Theorem 7.16. We mention some elsewhere; others include

xxx list.

Section 7.2. The name “arc-transitive” isn’t standard: Biggs [48] writes “symmetric” and Brouwer et al [71] write “flag-transitive”. Arc-transitivity is not necessary for the property “$E_{v}T_{w}$ is constant over edges”. For instance, a graph which is vertex-transitive and edge-transitive (in the sense of undirected edges) has the property, but is not necessarily arc-transitive [182]. Gobel and Jagers [168] observed that the property

(equivalently: the effective resistance across each edge is constant) holds for arc-transitive graphs and for trees.

Section 7.2.2. Sbihi [306] and Zuckerman [343] noted that the subset version of Matthews method could be applied to the $d$-torus to give Corollaries 7.24 and 7.25.

The related topic of the time taken by random walk on the infinite lattice $Z^{d}$ to cover a ball centered at the origin has been studied independently – see Revesz [288] Chapter 22 and Lawler [222], who observed that similar arguments could be applied to the $d$-torus, improving the lower bound in Corollary 7.25. It is easy to see an informal argument suggesting that, for random walk on the $2$-torus, when $n^{\alpha}$ vertices are unvisited the set of unvisited vertices has some kind of fractal structure. No rigorous results are known, but heuristics are given in Brummelhuis and Hilhorst [75].

Section 7.3.1. Deriving these exact formulas is scarcely more than undergraduate mathematics, so I am amazed to see that research papers have continued to be published in the 1980s and 1990s claiming various special or general cases as new or noteworthy.

Section 7.3.5. In the setting of isotropic random flight (7.36) with step-length distribution $q$, it is natural to ask what conditions on $q$ and $q^{\prime}$ imply that $\tau(q)\geq\tau(q^{\prime})$ for our parameters $\tau$. For certain distributions on the $d$-cube, detailed explicit calculations by Karlin et al [207] establish an ordering of the entire eigenvalue sequences, which in particular implies this inequality for $\tau_{2}$ and $\tau_{0}$. Establishing results of this type for general Gelfand pairs seems an interesting project.

Miscellaneous. On a finite field, such as $Z_{p}$ for prime $p$, one can consider “random walks” with steps of the form $x\rightarrow\alpha x+\beta$, with a specified joint distribution for $(\alpha,\beta)$. Chung et al [92] treat one example in detail.