Top to random shuffling stationary distribution

Question

Top to random shuffling is a method of shuffling a deck of N cards whereby the top card of the deck is removed and placed at random in the deck, and the procedure is repeated. I want to know the stationary distribution of the Markov chain where a state is a permutation of the deck. I saw a proof using random walks on groups that the stationary distribution is the uniform distribution. Is there a intuitive way to see this?

Answer 1

There are $52!$ states in this discrete time Markov chain (DTMC), one state for each permutation $p$. Let $X(t)$ be the permutation at time $t \in \{0, 1, 2, ...\}$. The DTMC can be shown to be irreducible (you can get from any state to any other state using the top card method). The DTMC is aperiodic because the top card method can take from the top and put back on the top (so it has a self-transition where $X(t+1)=X(t)$).

So this is an irreducible, aperiodic, finite-state DTMC.

So there is a unique probability mass vector that solves the stationary equation $\pi = \pi P$, and the limiting probability distribution is equal to this stationary distribution (regardless of the initial distribution). It remains to show that the uniform distribution solves the stationary equation (so it must be the unique probability mass vector solution that is also the limiting steady state distribution).

Suppose we start in the uniform distribution, so $$P[X(0)=q]=1/52! \quad \mbox{for all permutations $q$} \quad \mbox{ (Eq. 1)}$$ Let $p$ be a permutation. We have $$P[X(1)=p] = \sum_{j=1}^{52}P[X(1)=p|J=j]P[J=j]$$ where $J$ is the random card we put the top card behind. It suffices to show $P[X(1)=p|J=j]=1/52!$ for all $j \in \{1, ..., 52\}$.

Note that the event $\{J=j\}$ creates the permutation shift: $$ 1\rightarrow j \rightarrow (j-1) \rightarrow (j-2) \rightarrow ... \rightarrow 2 \rightarrow 1$$

Given $J=j$ and $X(1)=p$, we know $X(0)=p_j'$ for some unique permutation $p_j'$ that is obtained from the inverse shift. So $$P[X(1)=p|J=j]=P[X(0)=p_j'|J=j] \overset{(a)}{=} P[X(0)=p_j'] \overset{(b)}{=} 1/52!$$ where step (a) holds because the random choice $J$ is made independently of the permutation at time $0$, that is, event $\{J=j\}$ is independent of the event $\{X(0)=p_j'\}$; step (b) holds by (Eq. 1).