Partial shuffles by lazy swaps

• Main Authors: Janzer, Barnabás, Johnson, J. Robert, Leader, Imre
• Format: Text
• Language: unknown
• Published: 2022
• Subjects: Mathematics - Combinatorics; Groenland
• Online Access: http://arxiv.org/abs/2210.13286

What is the smallest number of random transpositions (meaning that we swap given pairs of elements with given probabilities) that we can make on an $n$-point set to ensure that each element is uniformly distributed -- in the sense that the probability that $i$ is mapped to $j$ is $1/n$ for all $i$ and $j$? And what if we insist that each pair is uniformly distributed? In this paper we show that the minimum for the first problem is about $\frac{1}{2} n \log_2 n$, with this being exact when $n$ is a power of $2$. For the second problem, we show that, rather surprisingly, the answer is not quadratic: $O(n \log^2 n)$ random transpositions suffice. We also show that if we ask only that the pair $1,2$ is uniformly distributed then the answer is $2n-3$. This proves a conjecture of Groenland, Johnston, Radcliffe and Scott. Comment: 15 pages