Perfect shuffling with fewer lazy transpositions

arXiv2208.06629MaRDI QIDQ6407776FDOQ6407776

Carla Groenland, Alex Scott, Jamie Radcliffe, Tom Johnston

Publication date: 13 August 2022

Abstract: A lazy transposition $(a,b,p)$ is the random permutation that equals the identity with probability $1-p$ and the transposition $(a,b)in{S}_n$ 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 $$, 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 $$, and consider some related questions.

This page was built for publication: Perfect shuffling with fewer lazy transpositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6407776)