<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Separation Cutoffs for Random Walk on Irreducible Representations
Jason Fulman
Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532, USA
Annals of Combinatorics 14 (3) pp.319-337 September, 2010
AMS Subject Classification: 60C05, 20P05

Random walk on the irreducible representations of the symmetric and general linear groups is studied. A separation distance cutoff is proved and the exact separation distance asymptotics are determined. A key tool is a method for writing the multiplicities in the Kronecker tensor powers of a fixed representation as a sum of non-negative terms. Connections are made with the Lagrange-Sylvester interpolation approach to Markov chains.

Keywords: Markov chain, cutoff phenomenon, irreducible representation, separation distance, Lagrange-Sylvester interpolation


1. Aldous, D.: Random walks on finite groups and rapidly mixing Markov chains. In: Séminaire de Probabilités, XVII, Lecture Notes in Math. 986, pp. 243--297. Springer, Berlin (1983)

2. Aldous, D., Diaconis, P.: Shuffling cards and stopping times. Amer. Math. Monthly 93(5), 333--348 (1986).

3. Aldous, D., Diaconis, P.: Strong uniform times and finite random walks. Adv. in Appl. Math. 8(1), 69--97 (1987)

4. Andrews, G.: The Theory of Partitions. Cambridge University Press, New York (1984)

5. Bidigare, P., Hanlon, P., Rockmore, D.: A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. Duke Math. J. 99(1), 135--174 (1999)

6. Biane, P., Bougerol, P., O'Connell, N.: Littelmann paths and Brownian paths. Duke Math. J. 130(1), 127--167 (2005)

7. Brown, M.: Spectral analysis, without eigenvectors, for Markov chains. Probab. Engrg. Inform. Sci. 5(2), 131--144 (1991)

8. Chatterjee, S., Diaconis, P., Meckes, E.: Exchangeable pairs and Poisson approximation, Probab. Surv. 2, 64--106 (2005)

9. Diaconis, P.: Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward, CA (1988)

10. Diaconis, P.: The cutoff phenomenon in finite Markov chains. Proc. Natl. Acad. Sci. USA 93(4), 1659--1664 (1996)

11. Diaconis, P., Fill, J.: Strong stationary times via a new form of duality. Ann. Probab. 18(4), 1483--1522 (1990)

12. Diaconis, P., Fill, J., Pitman, J.: Analysis of top to random shuffles. Combin. Probab. Comput. 1(2), 135--155 (1992)

13. Diaconis, P., Hanlon, P.: Eigen-analysis for some examples of the Metropolis algorithm. In: Hypergeometric Functions on Domains of Positivity, Jack Polynomials, and Applications, pp. 99--117. Amer. Math. Soc., Providence, RI (1992)

14. Diaconis, P., Saloff-Coste, L.: Separation cut-offs for birth and death chains. Ann. Appl. Probab. 16(4), 2098--2122 (2006)

15. Eymard, P., Roynette, B.: Marches aléatoires sur le dual de SU(2). In: Analyse Harmonique Sur Les Groupes De Lie, pp. 108--152. Springer, Berlin (1975)

16. Feller, W.: An Introduction to Probability Theory and Its Applications, Volume 1, Second edition. John Wiley and Sons, Inc., New York (1957)

17. Fulman, J.: Stein's method and Plancherel measure of the symmetric group. Trans. Amer. Math. Soc. 357(2), 555--570 (2005)

18. Fulman, J.: Stein's method, Jack measure, and the Metropolis algorithm. J. Combin. Theory Ser. A 108(2), 275--296 (2004)

19. Fulman, J.: Card shuffling and the decomposition of tensor products. Pacific J. Math. 217(2), 247--262 (2004)

20. Fulman, J.: Stein's method and random character ratios. Trans. Amer. Math. Soc. 360(7), 3687--3730 (2008)

21. Fulman, J.: Applications of symmetric functions to cycle and increasing subsequence structure after shuffles. J. Algebraic Combin. 16(2), 165--194 (2002)

22. Fulman, J.: Convergence rates of random walk on irreducible representations of finite groups. J. Theoret. Probab. 21(1), 193--211 (2008)

23. Fulman, J.: Commutation relations and Markov chains. Probab. Theory Related Fields 144(1-2), 99--136 (2009)

24. Gantmacher, F.: The Theory of Matrices, Vol. 1. Chelsea Publishing Co., New York (1959)

25. Gnedin, A., Kerov, S.: Derangement characters of the finite general linear group. Algebr. Represent. Theory 8(2), 255--274 (2005)

26. Goupil, A., Chauve, C.: Combinatorial operators for Kronecker powers of representations of Sn. Sém. Lothar. Combin. 54, Art. B54j (2005/07)

27. Macdonald, I.G.: Symmetric Functions and Hall Polynomials, Second edition. The Clarendon Press, Oxford University Press, New York (1995)

28. Moore, C., Russell, A., Sniady, P.: On the impossibility of a quantum sieve algorithm for graph isomorphism. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 536--545. ACM, New York (2007)

29. Sagan, B.: The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions. Pacific Grove, CA (1991)

30. Saloff-Coste, L.: Random walk on finite groups. In: Probability on Discrete Structures, pp. 263--346. Springer, Berlin (2004)

31. van Lint, J., Wilson, R.: A Course in Combinatorics, Second edition. Cambridge University Press, Cambridge (2001)

32. Wilf, H.: Generatingfunctionology, Second edition. Academic Press, Inc., Boston, MA (1994)

33. Wilson, D.: Mixing times of Lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 14(1), 274--325 (2004)

34. Zelevinsky, A.: Representations of Finite Classical Groups: A Hopf Algebra Approach, LNM 869. Springer-Verlag, Berlin-New York (1981)