UC Davis

We prove a theorem that reduces bounding the mixing time of a card shuffle to verifying acondition that involves only triplets of cards, based on earlier work by Morris involving pairs of cards. Then we use it to obtain a bound on the mixing time of the lazy version of a shuffle introduced by Diaconis. The Diaconis shuffle is a variation on the 15-puzzle. There are n2 tiles arranged in an n × n torus. Each step, a random tile and direction (North, South, East, West) are selected, and the chosen tile’s row or column is cycled in the chosen direction. Diaconis conjectured that the mixing time is O(n3 log n). We prove a mixing time bound of O(n3 log3 n).