×

A phase transition in the random transposition random walk. (English) Zbl 1102.60005

Motivated by the evolution study of the effectiveness of the parsimony method made by G. Buorque and P. A. Pevzner [Genome research 12, No. 1, 26–36 (2002)], the authors consider a continuous time random walk \(\{\sigma_t,\, t\geq 0\}\) on the permutation group of \(n\) elements. The random walk starts at the identity element and, at times of a rate one Poisson process, the current state of the random walk is subject to a transposition of two elements chosen uniformly at random, with replacement, from \(\{1,2,\dots,n\}\). Let \(| \sigma_t| \) be the number of cycles in the cyclic decomposition of \(\sigma_t \) and let \(D_t=n-| \sigma_t| \) be the distance of \(\sigma_t \) to the identity, i.e., the minimum number of transpositions one needs to perform on \(\sigma_t\) to go back to the identity element.
By showing that \(| \sigma_t| \) evolves according to the dynamics of a coagulation-fragmentation process studied by D. J. Aldous [Bernoulli 5, No. 1, 3–48 (1999; Zbl 0930.60096)] and J. Pitman [Comb. Probab. Comput. 11, 501–514 (2002; Zbl 1011.60051)] and relating the behavior of the random walk with some characteristics of the Erdős-Rényi random graph model, the authors investigate the asymptotic behavior of \(D_{cn},\, c\in (0,\infty)\) as \(n\to\infty\) and, moreover, describe the fluctuation of \(D_{cn}\) about its mean in each of the three regimes: subcritical, critical and supercritical.

MSC:

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, Ann. Prob., 25, 812 (1997) · Zbl 0877.60010 · doi:10.1214/aop/1024404421
[2] Aldous, Bernoulli., 5, 3 (1999) · Zbl 0930.60096 · doi:10.2307/3318611
[3] Angel, O.: Random infinite permutations and the cyclic time random walk. Pages 9-16 in Banderier and Krattenthaler (2003) · Zbl 1073.60524
[4] Arratia, R., Barbour, A., Tavaré, S.: Logarithmic combinatorial structures : a probabilistic approach. European Math. Society Monographs, 1. (2003) · Zbl 1040.60001
[5] Bafna, Mol. Biol. Evol., 12, 239 (1995)
[6] Ball, J. Appl. Prob., 20, 227 (1983) · Zbl 0519.92023 · doi:10.2307/3213797
[7] Banderier, C., Krattenthaler, C.: Proc. of the conference Discrete Random Walks. Discrete Math and Computer Science. dmtcs.loria.fr/proceedings/dmACind.html (2003) · Zbl 1031.68086
[8] Berestycki, N., Durrett, R.: A phase transition in the random transposition random walk. Pages 17-26 in Banderier and Krattenthaler (2003) · Zbl 1073.60525
[9] Bollobás, Trans. Amer. Math. Soc., 286, 257 (1984) · Zbl 0579.05046 · doi:10.2307/1999405
[10] Bollobás, B.: Random Graphs, Cambridge. University Press, 1985 · Zbl 0567.05042
[11] Borel, Application au problème de l’attente à un guichet. C.R. Acad. Sci. Paris., 214, 452 (1942) · Zbl 0026.33002
[12] Bourque, Genome Research., 12, 26 (2002)
[13] Devroye, L.: The branching process method in the Lagrange random variate generation, cgm.cs.mcgill.ca/ luc/branchingpaper.ps (1992) · Zbl 0825.65003
[14] Diaconis, P., Mayer-Wolf, E., Zeitouni, O., Zerner, M.: Uniqueness of invariant distributions for split-merge transformations and the Poisson-Dirichlet law. Ann. Prob., to appear (2003)
[15] Durrett, R.: Probability: Theory and Examples. Edition, Duxbury Press, 1996
[16] Durrett, R.: Probability Models for DNA Sequence Evolution. Springer-Verlag, New York, 2002 · Zbl 0991.92021
[17] Durrett, J. Theor. Prob., 16, 725 (2003) · Zbl 1047.92020 · doi:10.1023/A:1025676617383
[18] Durrett, R., Nielsen, R., York, T.L.: Bayesian estimation of genomic distance. Genetics, to appear (2003)
[19] Hannehalli, Proceedings of the, 27, 178 (1995)
[20] Jacod, J., Shiryaev, A.: Limit Theorems for Stochastic Processes. Springer, New-York, 1987 · Zbl 0635.60021
[21] Janson, Rand. Struct. Algor., 4, 231 (1993)
[22] Janson, S., Luczak, T., Ruczinski, A.: Random Graphs. Wiley-Interscience, New York, 2000 · Zbl 0968.05003
[23] Luczak, Trans. Amer. Math. Soc., 341, 721 (1994) · Zbl 0807.05065 · doi:10.2307/2154580
[24] Mayer-Wolf, Electr. Journ. Prob., 7, 1 (2002)
[25] Pevzner, P.A.: Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge, 2000 · Zbl 0972.92011
[26] Pevzner, Genome Research., 13, 37 (2003) · doi:10.1101/gr.757503
[27] Pitman, J.: Enumerations of trees and forests related to branching processes and random walks. Microsurveys in Discrete Probability, D. Aldous and J. Propp editors. DIMACS Ser. Discrete Math. Theoret. Comp. Sci no.41 163-180. Amer. Math. Soc. Providence RI. (1998) · Zbl 0908.05027
[28] Pitman, J., Coalescent random forests, J. Comb. Theory A., 85, 165-193 (1999) · Zbl 0918.05042
[29] Pitman, Combin. Prob. Comput., 11, 501 (2002) · Zbl 1011.60051 · doi:10.1017/S0963548302005163
[30] Pitman, J.: Combinatorial stochastic processes. Lecture Notes for St. Flour Course. To appear, available at http://stat-www.berkeley.edu/users/pitman/ (2003)
[31] Pittel, Struct. Algor.,, 1, 311 (1990) · Zbl 0747.05080
[32] Ranz, Genome Research., 11, 230 (2001) · doi:10.1101/gr.162901
[33] Revuz, D., Yor, M.: Continuous martingales and Brownian Motion, Springer-Verlag, New York, 1999 · Zbl 0917.60006
[34] Schramm, O.: Composition of random transpositions, Israel J. Math. to appear (2004)
[35] Tanner, Biometrika, 48, 222 (1961) · Zbl 0139.35101 · doi:10.2307/2333154
[36] York, J. Comp. Bio., 9, 808 (2002)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.