Geodesic
A phase transition in the random transposition random walk
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03) (2003).

Voir la notice de l'article provenant de la source Episciences

Our work is motivated by Bourque-Pevzner's simulation study of the effectiveness of the parsimony method in studying genome rearrangement, and leads to a surprising result about the random transposition walk in continuous time on the group of permutations on $n$ elements starting from the identity. Let $D_t$ be the minimum number of transpositions needed to go back to the identity element from the location at time $t$. $D_t$ undergoes a phase transition: for $0 < c ≤ 1$, the distance $D_cn/2 ~ cn/2$, i.e., the distance increases linearly with time; for $c > 1$, $D_cn/2 ~ u(c)n$ where u is an explicit function satisfying $u(x) < x/2$. Moreover we describe the fluctuations of $D_{cn/2}$ about its mean at each of the three stages (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-Rényi random graph model. 
@article{DMTCS_2003_special_248_a23,
     author = {Berestycki, Nathanael and Durrett, Rick},
     title = {A phase transition in the random transposition random walk},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)},
     year = {2003},
     doi = {10.46298/dmtcs.3343},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3343/}
}
TY  - JOUR
AU  - Berestycki, Nathanael
AU  - Durrett, Rick
TI  - A phase transition in the random transposition random walk
JO  - Discrete mathematics & theoretical computer science
PY  - 2003
VL  - DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3343/
DO  - 10.46298/dmtcs.3343
LA  - en
ID  - DMTCS_2003_special_248_a23
ER  - 
%0 Journal Article
%A Berestycki, Nathanael
%A Durrett, Rick
%T A phase transition in the random transposition random walk
%J Discrete mathematics & theoretical computer science
%D 2003
%V DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3343/
%R 10.46298/dmtcs.3343
%G en
%F DMTCS_2003_special_248_a23
Berestycki, Nathanael; Durrett, Rick. A phase transition in the random transposition random walk. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03) (2003). doi : 10.46298/dmtcs.3343. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3343/

Cité par Sources :