2022/08/13 by Carla Groenland, Groenland, Carla, Tom Johnston +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2208.06629
openalex publication_date 2022/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A lazy transposition (a,b,p) is the random permutation that equals the identity with probability 1-p and the transposition (a,b)∈ Sn with probability p. How long must a sequence of independent lazy transpositions be if their composition is uniformly distributed? It is known that there are sequences of length \binomn2, but are there shorter sequences? This was raised by Fitzsimons in 2011, and independently by Angel and Holroyd in 2018. We answer this question negatively by giving a construction of length \frac23 \binomn2+O(nlog n), and consider some related questions.