The probability of long cycles in interchange processes. (English) Zbl 1269.82041

Summary: We examine the number of cycles of length \(k\) in a permutation as a function on the symmetric group. We write it explicitly as a combination of the characters of irreducible representations. This allows us to study the formation of long cycles in the interchange process, including a precise formula for the probability that the permutation is one long cycle at a given time \(t\), and estimates for the cases of shorter cycles.


82C22 Interacting particle systems in time-dependent statistical mechanics
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
43A65 Representations of groups, semigroups, etc. (aspects of abstract harmonic analysis)
20B30 Symmetric groups
Full Text: DOI arXiv Euclid


[1] G. Alon and G. Kozma, Ordering the representations of \(S_{n}\) using the interchange process , Canad. Math. Bull. 56 (2013), 13-30. · Zbl 1259.82061
[2] O. Angel, “Random infinite permutations and the cyclic time random walk” in Discrete Random Walks (Paris, 2003) , Discrete Math. Theor. Comput. Sci. Proc., AC, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003, 9-16. · Zbl 1073.60524
[3] R. Bacher, Valeur propre minimale du laplacien de Coxeter pour le groupe symétrique , J. Algebra 167 (1994), 460-472. · Zbl 0812.05028
[4] N. Berestycki, Emergence of giant cycles and slowdown transition in random transpositions and k-cycles , Electron. J. Probab. 16 (2011), 152-173. · Zbl 1228.60079
[5] N. Berestycki and R. Durrett, A phase transition in the random transposition random walk , Probab. Theory Related Fields 136 (2006), 203-233. · Zbl 1102.60005
[6] N. Berestycki and G. Kozma, Cycle structure of the interchange process and representation theory , preprint, [math.PR]. 1205.4753v1
[7] P. Caputo, T. M. Liggett, and T. Richthammer, Proof of Aldous’ spectral gap conjecture , J. Amer. Math. Soc. 23 (2010), 831-851. · Zbl 1203.60145
[8] P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions , Z. Wahrsch. Verw. Gebiete 57 (1981), 159-179. · Zbl 0485.60006
[9] N. Eriksen and A. Hultman, Estimating the expected reversal distance after a fixed number of reversals , Adv. in Appl. Math. 32 (2004), 439-453. · Zbl 1051.92029
[10] W. Fulton and J. Harris, Representation Theory: A First Course , Grad. Texts in Math. 129 , Springer, New York, 1991. · Zbl 0744.22001
[11] A. Hammond, Infinite cycles in the random stirring model on trees , preprint, [math.PR]. 1202.1319v2 · JFM 11.0570.01
[12] Alan Hammond, Sharp phase transition in the random stirring model on trees , preprint, [math.PR]. 1202.1322v2 · Zbl 1317.60130
[13] G. James and A. Kerber, The Representation Theory of the Symmetric Group , Encyclopedia Math. Appl. 16 , Addison-Wesley, Reading, Mass., 1981. · Zbl 0491.20010
[14] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing Times , Amer. Math. Soc., Providence, 2009. · Zbl 1160.60001
[15] E. Lubetzky and A. Sly, Explicit expanders with cutoff phenomena , Electron. J. Probab. 16 (2011), 419-436. · Zbl 1226.60098
[16] R. Montenegro and P. Tetali, Mathematical Aspects of Mixing Times in Markov Chains , Found. Trends Theor. Comput. Sci. 1 , NOW, Boston, 2006.
[17] B. Morris, The mixing time for simple exclusion , Ann. Appl. Probab. 16 (2006), 615-635. · Zbl 1133.60037
[18] R. I. Oliveira, Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk , to appear in Ann. Probab., preprint, [math.PR]. 1007.2669v3
[19] R. Pemantle, A shuffle that mixes sets of any fixed size much faster than it mixes the whole deck , Random Structures Algorithms 5 (1994), 609-626. · Zbl 0808.60016
[20] B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions , 2nd ed., Grad. Texts in Math. 203 , Springer, New York, 2001. · Zbl 0964.05070
[21] O. Schramm, Compositions of random transpositions , Israel J. Math. 147 (2005), 221-243. · Zbl 1130.60302
[22] B. Tóth, Improved lower bound on the thermodynamic pressure of the spin \(1/2\) Heisenberg ferromagnet , Lett. Math. Phys. 28 (1993), 75-84. · Zbl 0772.60103
[23] N. V. Tsilevich, Spectral properties of the periodic Coxeter Laplacian in the two-row ferromagnetic case (in Russian), Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 378 (2010), 111-132; English translation in J. Math. Sci. (N. Y.) 174 (2011), 58-70.
[24] D. B. Wilson, Mixing times of Lozenge tiling and card shuffling Markov chains , Ann. Appl. Probab. 14 (2004), 274-325. · Zbl 1040.60063
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.