Robert Johnson

Partial shuffles by lazy swaps

Suppose we generate a random permutation using a sequence of random swaps -- that is, we perform a sequence of moves each of which involves swapping a pair of elements in given positions with given probability. How many such moves are needed to make sure that at the end we have a uniformly random permutation? What if we just require that every element is equally likely to be in any position? And what if we insist that every pair, or just a single fixed pair, of elements is uniformly distributed?

I will discuss some problems and results on these questions and related ones.

Joint work with Barnabás Janzer and Imre Leader.