Emergence of Giant Cycles and Slowdown Transition in Random Transpositions and k-Cycles

Nathanael Berestycki (University of Cambridge)

Abstract


Consider the random walk on the permutation group obtained when the step distribution is uniform on a given conjugacy class. It is shown that there is a critical time at which two phase transitions occur simultaneously. On the one hand, the random walk slows down abruptly: the acceleration (i.e., the second time derivative of the distance) drops from $0$ to $-\infty$ at this time as $n\to\infty$. On the other hand, the largest cycle size changes from microscopic to giant. The proof of this last result is considerably simpler and holds more generally than in a previous result of Oded Schramm for random transpositions. It turns out that in the case of random $k$-cycles, this critical time is proportional to $1/[k(k-1)]$, whereas the mixing time is known to be proportional to $1/k$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 152-173

Publication Date: January 12, 2011

DOI: 10.1214/EJP.v16-850

References

  1. Angel, Omer. Random infinite permutations and the cyclic time random walk. Discrete random walks (Paris, 2003), 9--16 (electronic), Discrete Math. Theor. Comput. Sci. Proc., AC, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003. MR2042369 (2005e:60096)
  2. Berestycki, Nathanaël. The hyperbolic geometry of random transpositions. Ann. Probab. 34 (2006), no. 2, 429--467. MR2223947 (2007h:60039)
  3. Berestycki, Nathanaël; Durrett, Rick. A phase transition in the random transposition random walk. Probab. Theory Related Fields 136 (2006), no. 2, 203--233. MR2240787 (2007i:60009)
  4. N. Berestycki, O. Schramm, and O. Zeitouni. Mixing times of random $k$-cycles and coagulation-fragmentation chains. Ann. Probab., to appear.
  5. Bollobás, Béla. Random graphs.Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. xvi+447 pp. ISBN: 0-12-111755-3; 0-12-111756-1 MR0809996 (87f:05152)
  6. Borgs, Christian; Chayes, Jennifer T.; van der Hofstad, Remco; Slade, Gordon; Spencer, Joel. Random subgraphs of finite graphs. III. The phase transition for the $n$-cube. Combinatorica 26 (2006), no. 4, 395--410. MR2260845 (2007k:05194)
  7. Buchanan, H. E.; Hildebrandt, T. H. Note on the convergence of a sequence of functions of a certain type. Ann. of Math. (2) 9 (1908), no. 3, 123--126. MR1502360
  8. Diaconis, Persi. Group representations in probability and statistics.Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. vi+198 pp. ISBN: 0-940600-14-5 MR0964069 (90a:60001)
  9. P. Diaconis and M. Shahshahani. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete, 57(2):159--179, 1981.
  10. Durrett, Rick. Random graph dynamics.Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2007. x+212 pp. ISBN: 978-0-521-86656-9; 0-521-86656-1 MR2271734 (2008c:05167)
  11. Karoński, M.; Łuczak, T. Random hypergraphs. Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 283--293, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996. MR1395864 (97m:05232)
  12. Karoński, Michał; Łuczak, Tomasz. The number of connected sparsely edged uniform hypergraphs. Discrete Math. 171 (1997), no. 1-3, 153--167. MR1454447 (98g:05072)
  13. M. Karonski and T.Luczak. The phase transition in a random hypergraph. J. Comput. Appl. Math., 142(1):125--135, 2002. Probabilistic methods in combinatorics and combinatorial optimization.
  14. Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times.With a chapter by James G. Propp and David B. Wilson.American Mathematical Society, Providence, RI, 2009. xviii+371 pp. ISBN: 978-0-8218-4739-8 MR2466937 (2010c:60209)
  15. Molloy, Michael; Reed, Bruce. A critical point for random graphs with a given degree sequence.Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, "Random Graphs '93'' (Poznań, 1993). Random Structures Algorithms 6 (1995), no. 2-3, 161--179. MR1370952 (97a:05191)
  16. Molloy, Michael; Reed, Bruce. The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput. 7 (1998), no. 3, 295--305. MR1664335 (2000c:05130)
  17. Roussel, Sandrine. Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique.(French) [Cutoff phenomenon for certain random walks on the symmetric group] Colloq. Math. 86 (2000), no. 1, 111--135. MR1799892 (2001m:60019)
  18. Saloff-Coste, Laurent. Random walks on finite groups. Probability on discrete structures, 263--346, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023654 (2004k:60133)
  19. Schramm, Oded. Compositions of random transpositions. Israel J. Math. 147 (2005), 221--243. MR2166362 (2006h:60024)
  20. Tóth, Bálint. Improved lower bound on the thermodynamic pressure of the spin $1/2$ Heisenberg ferromagnet. Lett. Math. Phys. 28 (1993), no. 1, 75--84. MR1224836 (94h:82062)
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.