Summary
This paper studies a challenge problem posed by D. Aldous which also arises in algorithms for manipulating finite groups. The main tools used are comparison of two Markov chains on different but related state spaces and logarithmic Sobolev inequalities. As usual, the comparison argument involves some combinatorics of path.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Babai L. (1986):On the length of subgroup chains in the symmetric group Comm. Alg. 14, 1729–1736
Cameron P., Solomon R., Turull A. (1989):Chains of subgroups in symmetric groups. Jour. Alg. 127, 340–352
Celler F., Leedham-Green C., Murray S., Niemeyer A., O'Brien E. (1995):Generating random elements of finite group. Commun. Algebra23, 4931–4948
Davidov G., Sarnack P.: Forthcoming book
Diaconis P. (1982):Applications of non-commutative Fourier analysis to probability problems. Springer L.N.M. 1362, 51–100
Diaconis P. (1986):Group representations in probability and statistics. IMS, Hayward
Diaconis P., Graham R.L. (1995):On graphs and group Preprint, Dept. of Math. Harvard University
Diaconis P., Saloff-Coste L. (1993):Comparison theorems for reversible Markov chains. Ann. Appl. Prob. 3, 696–730
Diaconis P., Saloff-Coste L. (1993):Comparison techniques for random walk on finite groups. Ann. Prob. 21, 2131–2156
Diaconis P., Saloff-Coste L. (1992):Logarithmic Sobolevs inequalities and finite Markov chains. Preprint
Diaconis P., Saloff-Coste L. (1995):Walls on generating sets of groups
Diaconis P. and Stroock D. (1991):Geometric bounds for eigenvalues for Markov chains. Ann. Appl. Prob. 1, 36–61
Finkelstein L., Kantor W. (1993):Groups and computation. Amer. Math. Soc. Providence
Gluck D. (1994):Random walk and character ratios on finite groups of Lie type. Adv. Math. To appear
Gross L. (1976):Logarithmic Sobolev inequalities. Am. J. Math. 1061–1083
Hildebrand M. (1992):Generating random elements in SL n (Fq)by random transvections. J. Alg. Combinatorics 1, 133–150
Holley R., Stoock D. (1987):Logarithmic Sobolev inequalities and stochastic Ising models. J. Stat. Phys. 46, 1159–1194
Lubotzky A. Phillips R., Sarnack P. (1988):Ramanujan graphs. Combinatorica, 8, 261–277
Magaard K. (1995): Personal communication
Sinclair A. (1993):Algorithms for random generation and counting: a Markov chain approach. Birkhäuser, Boston
Suzuki M. (1982):Group theory I., Springer, New York
Author information
Authors and Affiliations
Additional information
Research partially supported by NATO grant CRG 950686