Relaxation time of \(L\)-reversal chains and other chromosome shuffles (Q862215)

R. Durrett has used an \(L\)-reversed continuous time Markov chain to model the evolution of chromosome chains. The state space consists of the \(n!\) configurations of an \(n\)-cycle with vertices numbered \(1\) to \(n\geq 2\) and the chain is obtained by doing \(L\)-reversals at the arrival times of a Poisson process with rate \(1\). A \(L\)-reversal consists in choosing a vertex at random (with uniform distribution) and independently choosing a length \(l\) (\(1\leq l\leq L\leq n\)) at random (with uniform distribution) and reversing the order of the vertices in the segment starting at \(x\) and ending at \(x+l\) (sum taken modulo \(n\)). Durrett has conjectured that the missing time \(T(n,L)=\inf \{t>0:\| p_{t}-\nu \| _{TV}\leq 1/e\}\) (where \(p_{t}\) and \(\nu \) are, respectively, the distribution at time \(t\) and the uniform distribution on the state space and \(TV\) stands for the total variation norm) satisfies \(\frac{1}{C}( \max (n,n^{3}/L^{3})) \log n\leq T(n,L)\leq C( \max (n,n^{3}/L^{3})) \log n\) for some constant \(C\). The upper bound was not proved and this paper could not prove or disprove it. Instead, it shows that \(\frac{1}{C}\max (n,n^{3}/L^{3})\leq \tau (n,L)\leq C( \max (n,n^{3}/L^{3})) \) for the relaxation time \(\tau (n,L)=\sup_{f} \text{Var}(f)/\mathcal{E}(f,f)\), where the supremum is taken over all non-constant functions \(f\) of the configuration \(\eta \), \(\text{Var}(f)=\frac{1}{n!}\sum_{\eta }f^{2}(\eta )-( \frac{1}{n!}\sum_{\eta }f(\eta )) ^{2}\) and \[ \mathcal{E}(f,f)=\frac{1}{2nL}\sum_{x=1}^{n}\sum_{l=1}^{L}\frac{1}{n!}\sum_{\eta }( (f(\eta ^{xl})-f(\eta )^{2}) \] with \(\eta ^{xl}\) the configuration resulting from \(\eta \) by doing the reversal described above. The authors also consider the case where the segment length is chosen according to a non-uniform distribution \(p(l)\propto \theta ^{l}\) and obtain \[ \frac{1}{C}\max (n,[ n(1-\theta )] ^{3})\leq \tau (n,\theta )\leq C( \max (n,[ n(1-\theta )] ^{3})) \] for \(\tau (n,\theta )=\sup_{f}\text{Var}(f)/\mathcal{E}_{\theta }(f,f)\) with \[ \mathcal{E}_{\theta }(f,f)=\frac{1-\theta }{2n}\sum_{x=1}^{n}\sum_{l=1}^{L}\theta ^{l-1}\frac{1}{n!}\sum_{\eta }( (f(\eta ^{xl})-f(\eta )^{2}). \]