Perfect shuffling with fewer lazy transpositions

Carla Groenland¹¹1Utrecht University, Utrecht, The Netherlands, [email protected]. Partially supported by the ERC Horizon 2020 project CRACKNP (grant no. 853234). Tom Johnston²²2School of Mathematics, University of Bristol, Bristol, BS8 1UG, UK and Heilbronn Institute for Mathematical Research, Bristol, UK, [email protected].
Jamie Radcliffe³³3University of Nebraska-Lincoln, USA,[email protected]. Alex Scott²²footnotemark: 2 ⁴⁴4Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK, [email protected]. Supported by EPSRC grant EP/V007327/1.

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 $\binom{n}{2}$ , 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 $\frac{2}{3}\binom{n}{2}+O(n\log n)$ , and consider some related questions.

1 Introduction

Let $S_{n}$ be the symmetric group on $n$ elements, and write $(a,b)\in S_{n}$ for the transposition that swaps $a$ and $b$ , and $1\in S_{n}$ for the identity permutation. A lazy transposition $T=(a,b,p)$ is the random permutation

T=\begin{cases}(a,b)&\text{ with probability }p,\\ 1&\text{ otherwise}.\end{cases}

The composition of a sequence of lazy transpositions is also a random permutation, and we will be interested in sequences which generate a uniformly random permutation. Let $U(n)$ denote the minimum length $\ell$ for which there exists a sequence of independent lazy transpositions $T_{1},\dots,T_{\ell}$ such that $T_{1}\cdots T_{\ell}\sim\operatorname{Uniform}(S_{n})$ , the uniform distribution over $S_{n}$ . We will call such a sequence a transposition shuffle. These were first discussed on Stack Exchange in 2011 [stack], before being investigated in more depth by Angel and Holroyd in 2018 [angel2018perfect]. Both give constructions using $\binom{n}{2}$ lazy transpositions and ask if this is best possible.

Problem 1 (Fitzsimons [stack], Angel and Holroyd [angel2018perfect]).

Does $U(n)=\binom{n}{2}$ for all $n$ ?

The main result of this paper is a new construction for shuffling with lazy transpositions which improves the constant in the upper bound of $U(n)$ and answers Problem 1 in the negative.

Theorem 2.

There exists an $\varepsilon>0$ such that $U(n)\leq(1-\varepsilon)\binom{n}{2}$ for all $n\geq 6$ . Moreover,

U(n)\leq\frac{2}{3}\binom{n}{2}+O(n\log n).

It will often be convenient to think of transpositions as moving $n$ distinguishable “counters” across $n$ “positions” which we label $1,\dots,n$ . A transposition $(a,b)$ acts by switching the counters currently in positions $a$ and $b$ , so a lazy transposition $(a,b,p)$ switches the counters currently in positions $a$ and $b$ with probability $p$ , and does nothing with probability $1-p$ . In this language a transposition shuffle is a sequence of independent lazy transpositions such that the final order of the counters is uniformly distributed over all $n!$ orders.

Transposition shuffles are a special case of the more general problem of shuffling $t$ counters across $n$ positions. We start with counters in positions $1,\dots,t$ , and leave the other positions empty. A transposition $(a,b)$ switches any counters in positions $a$ and $b$ (which may include switching a counter with an empty space). A sequence of lazy transpositions naturally defines a random variable by the positions of the counters at the end of sequence, and we can again ask that this be uniformly distributed over all $t!\binom{n}{t}$ options. If the output is