Chapter 7 Symmetric Graphs and Chains (January 31, 1994)

In this Chapter we show how general results in Chapters 3, 4 and 6 can sometimes be strengthened when symmetry is present. Many of the ideas are just simple observations. Since the topic has a “discrete math” flavor our default convention is to work in discrete time, though as always the continuous-time case is similar. Note that we use the word “symmetry” in the sense of spatial symmetry (which is the customary use in mathematics as a whole) and not as a synonym for time-reversibility. Note also our use of “random flight” for what is usually called “random walk” on a group.

Biggs [48] contains an introductory account of symmetry properties for graphs, but we use little more than the definitions. I have deliberately not been overly fussy about giving weakest possible hypotheses. For instance many results for symmetric reversible chains depend only of the symmetry of mean hitting times (7.7), but I haven’t spelt this out. Otherwise one can end up with more definitions than serious results! Instead, we focus on three different strengths of symmetry condition. Starting with the weakest, section 7.1 deals with symmetric reversible chains, a minor generalization of what is usually called “symmetric random walk on a finite group”. In the graph setting, this specializes to random walk on a Cayley or vertex-transitive graph. Section 7.2 deals with random walk on an arc-transitive graph, encompassing what is usually called “random walk on a finite group with steps uniform on a conjugacy class”. Section 5.16 deals with random walk on a distance-regular graph, which roughly corresponds to nearest-neighbor isotropic random walk on a discrete Gelfand pair.

This book focuses on inequalities rather than exact calculations, and the limitation of this approach is most apparent in this chapter. Group representation theory, though of course developed for non-probabilistic reasons, turns out to be very well adapted to the study of many questions concerning random walks on groups. I lack the space (and, more importantly, the knowledge) to give a worthwhile treatment here, and in any case an account which is both introductory and gets to interesting results is available in Diaconis [123]. In many concrete examples, eigenvalues are known by group representation theory, and so in particular our parameters $\tau_{2}$ and $\tau_{0}$ are known. See e.g. section 7.2.1. In studying a particular example, after investigating eigenvalues one can seek to study further properties of the chain by either

(i) continuing with calculations specific to the example; or

(ii) using general inequalities relating other aspects of the chain to $\tau_{2}$ and $\tau_{0}$.

The purpose of this Chapter is to develop option (ii). Of course, the more highly-structured the example, the more likely one can get stronger explicit results via (i). For this reason we devote more space to the weaker setting of section 7.1 than to the stronger settings of sections 7.2 and 5.16.

xxx scattering of more sophisticated math in Chapter 10.