PARTIAL SHUFFLES BY LAZY SWAPS.

How many random transpositions (meaning that we swap given pairs of elements with given probabilities independently) are needed to ensure that each element of [n] 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 2nlog2 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(nlog2 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. [ABSTRACT FROM AUTHOR]