zbMATH — the first resource for mathematics

Rate of convergence for shuffling cards by transpositions. (English) Zbl 0878.60043
Summary: Suppose we are given a graph with a label on each vertex and a rate assigned to each edge, and suppose that edges flip (that is, the labels at the two endpoints switch) randomly with the given rates. We consider two Markov processes on this graph: one whose states are the permutations of the \(n\) labels, and one whose states are the positions of a single label. We show that for several classes of graphs these two processes have the same spectral gap.

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60F05 Central limit and other weak theorems
Full Text: DOI
[1] Aldous, D. (1994). Unpublished manuscript.
[2] Bacher, R. (1992). Valeur propre minimale du laplacien de coxeter pour le groupe symetrique. Preprint.
[3] Diaconis, P., and Saloff-Coste, L. (1993). Comparison techniques for random walk on finite groups.Ann. Prob. 21, 2131–2156. · Zbl 0790.60011 · doi:10.1214/aop/1176989013
[4] Diaconis, P., and Shahshahani, M. (1981). Generating a random permutation with random transpositions.Z. Wahrsch. Verw. Geb. 57, 159–179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[5] Flatto, L., Odlyzko, A. M., and Wales, D. B. (1985). Random shuffles and group representations.Ann. Prob. 13, 154–178. · Zbl 0564.60007 · doi:10.1214/aop/1176993073
[6] Liggett, T. (1989). ExponentialL 2 convergence of attractive reversible nearest particle systems.Ann. Prob. 17, 403–432. · Zbl 0679.60093 · doi:10.1214/aop/1176991408
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.