We develop techniques for bounding the rate of convergence of a symmetric random walk on a finite group to the uniform distribution. The techniques gives bounds on the second largest (and other) eigenvalues in terms of the eigenvalues of a comparison chain with known eigenvalues. The techniques yield sharp rates for a host of previously intractable problems on the symmetric group.
Publié le : 1993-10-14
Classification:
Card shuffling,
reversible Markov chains,
random walk,
groups,
eigenvalues,
20B30,
60B15,
60J05,
60F99
@article{1176989013,
author = {Diaconis, Persi and Saloff-Coste, Laurent},
title = {Comparison Techniques for Random Walk on Finite Groups},
journal = {Ann. Probab.},
volume = {21},
number = {4},
year = {1993},
pages = { 2131-2156},
language = {en},
url = {http://dml.mathdoc.fr/item/1176989013}
}
Diaconis, Persi; Saloff-Coste, Laurent. Comparison Techniques for Random Walk on Finite Groups. Ann. Probab., Tome 21 (1993) no. 4, pp. 2131-2156. http://gdmltest.u-ga.fr/item/1176989013/