Rapidly Mixing Random Walks and Bounds on Characters of the Symmetric Group
Nathan Lulov
and Igor Pak
DOI: 10.1023/A:1021172928478
Abstract
We investigate mixing of random walks on S n and A n generated by permutations of a given cycle structure. The approach follows methods developed by Diaconis, which requires certain estimates on characters of the symmetric group and uses combinatorics of Young tableaux. We conclude with conjectures and open problems.
Pages: 151–163
Keywords: random walks on groups; symmetric group; Young tableaux
Full Text: PDF
References
1. D. Aldous and P. Diaconis, “Strong uniform times and finite random walks,” Advances in Applied Math. 8 (1987), 69-97.
2. D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs, monograph in preparation, 1996.
3. G. Andrews, The Theory of Partitions, Addison-Wesley, New York, 1976.
4. P. Diaconis, Group Representations in Probability and Statistics, IMS, Hayward, California, 1988.
5. P. Diaconis, “The cutoff phenomenon in finite Markov chains,” Proc. Nat. Acad. Sci. U.S.A. 93 (1996), 1659-1664.
6. P. Diaconis and M. Shahshahani, “Generating a random permutation with random transpositions,” Z. Wahr. verw. Gebiete, 57 (1981), 159-179.
7. Y. Dvir, Covering Properties of Permutation Groups, Lecture Notes in Math. 1112, Springer-Verlag, 1985.
8. S. Fomin and N. Lulov, “On the number of rim hook tableaux,” Zap. Nauchn. Sem. POMI 223 (1995), 219-226 (available also from http://www.math.lsa.umich.edu/\sim fomin/Papers/).
9. G. James and A. Kerber, “The representation theory of the symmetric group,” in Encyclopedia of Mathematics and its Applications, Vol. 16, G.-C. Rota (Ed.), Addison-Wesley, Reading, Mass. 1981.
10. M. Liebeck and A. Shalev, “Diameters of finite simple groups: Sharp bounds and applications,” Ann. of Math. 154(2) (2001), 383-406.
11. L. Lovász and P. Winkler, Mixing Times, AMS DIMACS Series, Vol. 41, pp. 189-204, 1998.
12. A. Lubotzky, Cayley Graphs: Eigenvalues, Expanders and Random Walks, LMS Lecture Note Ser., 218, Cambridge University Press, Cambridge, 1995.
13. N. Lulov, “Random Walks on the Symmetric Group Generated by Conjugacy Classes,” Ph.D. Thesis, Harvard University, 1996.
14. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, London, 1979.
15. I. Pak, “Random Walks on Permutation: Strong Uniform Time Approach,” Ph.D. Thesis, Harvard University, 1997.
16. I. Pak and V.H. Vu, “On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes,” Discrete Appl. Math. 110 (2001), 251-272.
17. Y. Roichman, “Upper bound on characters of the symmetric groups,” Invent. Math. 125 (1996), 451-485.
18. R.P. Stanley, “Factorization of permutations into n-cycles,” Discrete Math. 37 (1981), 255-262.
2. D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs, monograph in preparation, 1996.
3. G. Andrews, The Theory of Partitions, Addison-Wesley, New York, 1976.
4. P. Diaconis, Group Representations in Probability and Statistics, IMS, Hayward, California, 1988.
5. P. Diaconis, “The cutoff phenomenon in finite Markov chains,” Proc. Nat. Acad. Sci. U.S.A. 93 (1996), 1659-1664.
6. P. Diaconis and M. Shahshahani, “Generating a random permutation with random transpositions,” Z. Wahr. verw. Gebiete, 57 (1981), 159-179.
7. Y. Dvir, Covering Properties of Permutation Groups, Lecture Notes in Math. 1112, Springer-Verlag, 1985.
8. S. Fomin and N. Lulov, “On the number of rim hook tableaux,” Zap. Nauchn. Sem. POMI 223 (1995), 219-226 (available also from http://www.math.lsa.umich.edu/\sim fomin/Papers/).
9. G. James and A. Kerber, “The representation theory of the symmetric group,” in Encyclopedia of Mathematics and its Applications, Vol. 16, G.-C. Rota (Ed.), Addison-Wesley, Reading, Mass. 1981.
10. M. Liebeck and A. Shalev, “Diameters of finite simple groups: Sharp bounds and applications,” Ann. of Math. 154(2) (2001), 383-406.
11. L. Lovász and P. Winkler, Mixing Times, AMS DIMACS Series, Vol. 41, pp. 189-204, 1998.
12. A. Lubotzky, Cayley Graphs: Eigenvalues, Expanders and Random Walks, LMS Lecture Note Ser., 218, Cambridge University Press, Cambridge, 1995.
13. N. Lulov, “Random Walks on the Symmetric Group Generated by Conjugacy Classes,” Ph.D. Thesis, Harvard University, 1996.
14. I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, London, 1979.
15. I. Pak, “Random Walks on Permutation: Strong Uniform Time Approach,” Ph.D. Thesis, Harvard University, 1997.
16. I. Pak and V.H. Vu, “On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes,” Discrete Appl. Math. 110 (2001), 251-272.
17. Y. Roichman, “Upper bound on characters of the symmetric groups,” Invent. Math. 125 (1996), 451-485.
18. R.P. Stanley, “Factorization of permutations into n-cycles,” Discrete Math. 37 (1981), 255-262.