Relaxation time of L-reversal chains and other chromosome shuffles
Cancrini, N. ; Caputo, P. ; Martinelli, F.
Ann. Appl. Probab., Tome 16 (2006) no. 1, p. 1506-1527 / Harvested from Project Euclid
We prove tight bounds on the relaxation time of the so-called L-reversal chain, which was introduced by R. Durrett as a stochastic model for the evolution of chromosome chains. The process is described as follows. We have n distinct letters on the vertices of the n-cycle (ℤ mod n); at each step, a connected subset of the graph is chosen uniformly at random among all those of length at most L, and the current permutation is shuffled by reversing the order of the letters over that subset. We show that the relaxation time τ(n, L), defined as the inverse of the spectral gap of the associated Markov generator, satisfies $\tau (n,L)=O(n\vee \frac {n^{3}}{L^{3}})$ . Our results can be interpreted as strong evidence for a conjecture of R. Durrett predicting a similar behavior for the mixing time of the chain.
Publié le : 2006-08-14
Classification:  L-reversal chains,  random transpositions,  spectral gap,  60J27,  92D10
@article{1159804989,
     author = {Cancrini, N. and Caputo, P. and Martinelli, F.},
     title = {Relaxation time of L-reversal chains and other chromosome shuffles},
     journal = {Ann. Appl. Probab.},
     volume = {16},
     number = {1},
     year = {2006},
     pages = { 1506-1527},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1159804989}
}
Cancrini, N.; Caputo, P.; Martinelli, F. Relaxation time of L-reversal chains and other chromosome shuffles. Ann. Appl. Probab., Tome 16 (2006) no. 1, pp.  1506-1527. http://gdmltest.u-ga.fr/item/1159804989/