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).