= Top-to-random card shuffle
The <Top-to-random card shuffle> removes the top card and inserts it in one of the $n$ positions uniformly. Its <Stationary distribution> is uniform on <permutation>[permutations]. Each move is the inverse of a move of the <Random-to-top card shuffle>, so these chains are time reversals under that <Stationary distribution>.
In this group-walk setting they also have the same <total variation distance>[total variation] <mixing time of a Markov chain>[mixing profile]. Starting from the <identity permutation>, a random-to-top path multiplies <independent> identically distributed increments $G_1,\ldots,G_t$. The top-to-random increments have their inverse law. Reversing the order of an <independent and identically distributed>[iid] list leaves its joint law unchanged, so the product of inverse increments has the law of $(G_1\cdots G_t)^{-1}$. Inversion is a <bijection> preserving the <uniform distribution>; it therefore preserves <total variation distance> to that distribution. Translation symmetry makes the distance <independent> of the starting <permutation>.
Consequently top-to-random shares the $n\log n$ <cutoff for Markov chains>[cutoff] scale and order-$n$ window of random-to-top. The <group> symmetry is essential to this argument: time reversal alone does not give equality of worst-case <total variation distance>[total variation] profiles for arbitrary Markov chains.
Back to article page
