2
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ It is a finite state space irreducible and aperiodic DTMC and the uniform distribution is invariant, meaning it solves the stationary equation $\pi = \pi P$. So it is the unique stationary distribution, and all initial distributions converge to it. $\endgroup$
    – Michael
    Feb 14 at 1:45
  • $\begingroup$ How do we know $\pi=\pi P$? $\endgroup$
    – abc
    Feb 14 at 1:48
  • 1
    $\begingroup$ If we are in the uniform distribution, then taking one step by the top card method maintains this distribution. If $J\in\{1,...,52\}$ is the random card we place behind, you can condition on the event $\{J=j\}$ for $j \in \{1, ..., 52\}$, and the corresponding switch in positions $1\rightarrow j\rightarrow (j-1)\rightarrow (j-2)\rightarrow ...\rightarrow 2\rightarrow 1$. For each $j$, the conditional new distribution, given $J=j$, is still uniform. If $p$ is a permutation and $p'_j$ the unique permuatation that this shifts from (given $J=j$) then $P[New=p|J=j]=P[Old=p'_j]=1/52!$. $\endgroup$
    – Michael
    Feb 14 at 1:57
  • $\begingroup$ Maybe its obvious but I am struggling to see why the new distribution must be still uniform $\endgroup$
    – abc
    Feb 14 at 1:59
  • 1
    $\begingroup$ I added to my previous comment with some more detail. If you know $\{J=j\}$, there is a one-to-one correspondence between permutations $p\leftrightarrow p_j'$, meaning for every new permutation $p$ we shift into, there is only one unique previous permutation $p_j'$ that could have been the case (it is the one created by the inverse shift from $p$). $\endgroup$
    – Michael
    Feb 14 at 2:01

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I consider $n=52$ but the same holds for any positive integer $n$. $\endgroup$
    – Michael
    Feb 14 at 2:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .