Partial Shuffles by Lazy Swaps
Barnabás Janzer, J. Robert Johnson, Imre Leader · SIAM Journal on Discrete Mathematics · 2023
Abstract. How many random transpositions (meaning that we swap given pairs of elements with given probabilities independently) are needed to ensure that each element of [Formula: see text] is uniformly distributed—in the sense that the probability that [Formula: see text] is mapped to [Formula: see text] is [Formula: see text] for all [Formula: see text] and [Formula: see text]? 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 [Formula: see text], with this being exact when [Formula: see text] is a power of 2. For the second problem, we show that, rather surprisingly, the answer is not quadratic: [Formula: see text] random transpositions suffice. We also show that if we ask only that the pair [Formula: see text] is uniformly distributed, then the answer is [Formula: see text]. This proves a conjecture of Groenland, Johnston, Radcliffe, and Scott.