Generating a random signed permutation with random reversals (Q2576806): Difference between revisions

This article analyzes a mathematical model of gene rearrangements on a cyclic molecule: in this model, there are \(n\) positions in a circle, labeled \(1, 2, \dots, n\), going clockwise. There are also \(n\) markers, labeled \(1, 2, \dots, n\), each with a distinct top and bottom. Start with all markers with the top up, each marker on the position of its own label. Each unit time, choose \(i\) and then \(j\) and reverse the order of the markers \(i\) to \(j\), and with probability \(1/2\), flip these markers. The question is: if \(Q^{*k}\) is the probability distribution of assignments of markers to positions (and parity for top up versus top down), how rapidly does \(Q^{*k} \to U\), \(U\) being the uniform distribution, as \(k \to \infty\)? The primary result is that \(Q^{*k}\) becomes approximately uniform at \(k(n) = \Theta(n \log n)\), using convergence in \(\ell^2\) and (hence) in total variation. This result is proven by comparing it with a similar but more tractible ``paired flips'' random walk, following the method of \textit{P. Diaconis} and \textit{L. Saloff-Coste} [Ann. Prob. 21, No.~4, 2131--2156 (1993; Zbl 0790.60011)]. As this is a random walk on the hyperoctahedral group, with a relatively small number of steps available from each group element, the algebraic properties of the group are exploited to develop the convergence result for the ``paired flips'' walk. The article is only somewhat self-contained, and the article cites [\textit{P. Diaconis}, ``Group representations in probability and statistics'' (1998; Zbl 0695.60012)] and [\textit{C. H. Schoolfield}, SIAM J. Comput. 29, No. 3, 880--892 (2002)] for background.