Hypergroup deformations and Markov chains

Persi Diaconis and Phil Hanlon in their interesting paper⁽⁴⁾ give the rates of convergence of some Metropolis Markov chains on the cubeZ ^d (2). Markov chains on finite groups that are actually random walks are easier to analyze because the machinery of harmonic analysis is available. Unfortunately, Metropolis Markov chains are, in general, not random walks on group structure. In attempting to understand Diaconis and Hanlon's work, the authors were led to the idea of a hypergroup deformation of a finite groupG, i.e., a continuous family of hypergroups whose underlying space isG and whose structure is naturally related to that ofG. Such a deformation is provided forZ ^d (2), and it is shown that the Metropolis Markov chains studied by Diaconis and Hanlon can be viewed as random walks on the deformation. A direct application of the Diaconis-Shahshahani Upper Bound Lemma, which applies to random walks on hypergroups, is used to obtain the rate of convergence of the Metropolis chains starting at any point. When the Markov chains start at 0, a result in Diaconis and Hanlon⁽⁴⁾ is obtained with exactly the same rate of convergence. These results are extended toZ ^d (3).Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.