2022/10/24 by Barnabás Janzer, Janzer, Barnabás, J. Robert Johnson +3 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2210.13286
openalex publication_date 2022/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (1)/(2) n log2 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 log2 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.