A phase transition in the random transposition random walk (Q2503162)

Motivated by the evolution study of the effectiveness of the parsimony method made by \textit{G. Buorque} and \textit{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 \textit{D. J. Aldous} [Bernoulli 5, No. 1, 3--48 (1999; Zbl 0930.60096)] and \textit{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.