Abstract
Our work is motivated by Bourque and Pevzner's (2002) simulation study of the effectiveness of the parsimony method in studying genome rearrangement, and leads to a surprising result about the random transposition walk on the group of permutations on n elements. Consider this walk in continuous time starting at the identity and let D t be the minimum number of transpositions needed to go back to the identity from the location at time t. D t undergoes a phase transition: the distance D cn /2∼u(c)n, where u is an explicit function satisfying u(c)=c/2 for c≤1 and u(c)<c/2 for c>1. In addition, we describe the fluctuations of D cn /2 about its mean in each of the three regimes (subcritical, critical and supercritical). The techniques used involve viewing the cycles in the random permutation as a coagulation-fragmentation process and relating the behavior to the Erdős-Renyi random graph model.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aldous, D.: Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Prob. 25, 812–854 (1997)
Aldous, D.: Deterministic and stochastic models for coalescence (aggregation and coagulation) : a review of the mean-field theory for probabilists. Bernoulli. 5, 3–48 (1999)
Angel, O.: Random infinite permutations and the cyclic time random walk. Pages 9–16 in Banderier and Krattenthaler (2003)
Arratia, R., Barbour, A., Tavaré, S.: Logarithmic combinatorial structures : a probabilistic approach. European Math. Society Monographs, 1. (2003)
Bafna, V., Pevzner, P.: Sorting by reversals: Genome rearrangement in plant organelles and evolutionary history of X chromosome. Mol. Biol. Evol. 12, 239–246 (1995)
Ball, F.: The threshold behaviour of epidemic models. J. Appl. Prob. 20, 227–241 (1983)
Banderier, C., Krattenthaler, C.: Proc. of the conference Discrete Random Walks. Discrete Math and Computer Science. dmtcs.loria.fr/proceedings/dmACind.html (2003)
Berestycki, N., Durrett, R.: A phase transition in the random transposition random walk. Pages 17–26 in Banderier and Krattenthaler (2003)
Bollobás, B.: The evolution of random graphs. Trans. Amer. Math. Soc. 286, 257–274 (1984)
Bollobás, B.: Random Graphs, Cambridge. University Press, 1985
Borel, E.: Sur l'emploi du théorème de Bernoulli pour faciliter le calcul d'une infinité de coefficients. Application au problème de l'attente à un guichet. C.R. Acad. Sci. Paris. 214, 452–456 (1942)
Bourque, G., Pevzner, P. A.: Genome-scale evolution: reconstructing gene orders in the ancestral species. Genome Research. 12, 26–36 (2002)
Devroye, L.: The branching process method in the Lagrange random variate generation, cgm.cs.mcgill.ca/~luc/branchingpaper.ps (1992)
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)
Durrett, R.: Probability: Theory and Examples. Edition, Duxbury Press, 1996
Durrett, R.: Probability Models for DNA Sequence Evolution. Springer-Verlag, New York, 2002
Durrett, R.: Shuffling Chromosomes. J. Theor. Prob. 16, 725–750 (2003)
Durrett, R., Nielsen, R., York, T.L.: Bayesian estimation of genomic distance. Genetics, to appear (2003)
Hannehalli, S., Pevzner, P.A.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). Proceedings of the 27th Annual Symposium on the Theory of Computing, 178–189. Full version in the Journal of the ACM. 46, 1–27 (1995)
Jacod, J., Shiryaev, A.: Limit Theorems for Stochastic Processes. Springer, New-York, 1987
Janson, S., Knuth, D. E., Luczak, T., Pittel, B.: The birth of the giant component. Rand. Struct. Algor. 4, 231–358 (1993)
Janson, S., Luczak, T., Ruczinski, A.: Random Graphs. Wiley-Interscience, New York, 2000
Luczak, T., Pittel, B., Wierman, J. C.: The structure of a random graph near the point of the phase transition. Trans. Amer. Math. Soc. 341, 721–748 (1994)
Mayer-Wolf, E., Zeitouni, O., Zerner, M.: Asymptotics of certain coagulation-fragmentation processes and invariant Poisson-Dirichlet measures. Electr. Journ. Prob. 7, 1–25 (2002)
Pevzner, P.A.: Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge, 2000
Pevzner, P.A., Tesler, G.: Genome rearrangement in mammalian evolution: lessons from human and mouse genomes. Genome Research. 13, 37–45 (2003)
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)
Pitman, J.: Coalescent random forests, J. Comb. Theory A. 85 165–193 (1999)
Pitman, J.: Poisson-Dirichlet and GEM invariant distributions for split-and-merge transformations of an interval partition. Combin. Prob. Comput. 11, 501–514 (2002)
Pitman, J.: Combinatorial stochastic processes. Lecture Notes for St. Flour Course. To appear, available at http://stat-www.berkeley.edu/users/pitman/ (2003)
Pittel, B.: On tree census and the giant component in sparse random graphs, Rand. Struct. Algor., 1, 311–342 (1990)
Ranz, J.M., Casals, F., Ruiz, A.: How malleable is the eukaryotic genome? Extreme rate of chromosomal rearrangement in the genus Drosophila. Genome Research. 11, 230–239 (2001)
Revuz, D., Yor, M.: Continuous martingales and Brownian Motion, Springer-Verlag, New York, 1999
Schramm, O.: Composition of random transpositions, Israel J. Math. to appear (2004)
Tanner, J.C.: A derivation of the Borel distribution. Biometrika 48, 222–224 (1961)
York, T.L., Durrett, R., Nielsen, R.: Bayesian estimation of inversions in the history of two chromosomes. J. Comp. Bio. 9, 808–818 (2002)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Berestycki, N., Durrett, R. A phase transition in the random transposition random walk. Probab. Theory Relat. Fields 136, 203–233 (2006). https://doi.org/10.1007/s00440-005-0479-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-005-0479-7