The Top-to-random card shuffle removes the top card and inserts it in one of the positions uniformly. Its Stationary distribution is uniform on 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 mixing profile. Starting from the identity permutation, a random-to-top path multiplies independent identically distributed increments . The top-to-random increments have their inverse law. Reversing the order of an iid list leaves its joint law unchanged, so the product of inverse increments has the law of . 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 cutoff scale and order- 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 profiles for arbitrary Markov chains.
Articles by others on the same topic
There are currently no matching articles.