×

zbMATH — the first resource for mathematics

Random walks on finite groups. (English) Zbl 1049.60006
Kesten, Harry (ed.), Probability on discrete structures. Berlin: Springer (ISBN 3-540-00845-4/hbk). Encycl. Math. Sci. 110(1), 263-346 (2004).
The author presents a survey on random walks on finite groups, an area of research which was very active during the last decade. In fact, the emphasis of this article is laid on quantitative results, in particular on rates of convergence to uniform distribution. Of course, in a survey most proofs have to be omitted, the author explains the results and their importance by concrete examples, the most prominent are card shuffling problems.
The paper is divided into ten sections. The titles may serve as a list of contents: Introduction; Background and notations (including general Markov chain techniques); Shuffling cards and cut-off phenomenon; Probabilistic methods; Spectrum and singular values (eigenvalue bounds for general Markov chains and in particular for random walks); Eigenvalue bounds using paths (i.e., paths in the corresponding Caley graph); Volume growth conditions; Representation theory for finite groups (and rates for convergence to the uniform distribution); comparsion techniques (comparsion of two random walks via corresponding Dirichlet forms).
An introduction to this field and a first survey reflecting the investigations up to 1988 is found in the stimulating booklet of P. Diaconis [“Group representations in probability and statistics” (1988; Zbl 0695.60012)]. In the present survey the list of references contains 146 items, showing the activity of the research field. It should be noted that many important contributions of the last decade are due to the author and to P. Diaconis.
For the entire collection see [Zbl 1025.60001].

MSC:
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
60G50 Sums of independent random variables; random walks
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J27 Continuous-time Markov processes on discrete state spaces
PDF BibTeX XML Cite