4
$\begingroup$

Pemantle 1989 proves, among other things, that the Markov chain on $S_n$ induced by repeatedly and independently performing an overhand shuffle on a deck of $n$ cards is ergodic and has limiting distribution $U$, the uniform distribution on $S_n$.

What bothers me is that this result is announced without much fanfare, in fact it's never even made explicit: it's an implicit consequence of Theorem 1 in that paper. Pemantle simply begins by assuming that the limit distribution is $U$ and then produces bounds to prove it. But to me this is a very surprising result. When we perform an overhand shuffle, we randomly select one of a certain subset $O$ of permutations on the deck, and it's not even obvious to me that the subgroup generated by $O$ is equal to $S_n$. That the limiting distribution is $U$ is equivalent to the transition matrix being double stochastic, which is not obvious to me either.

My question is: is there some more general result about random walks on finite groups or on $S_n$ which predicts that the limiting distribution is $U$? Or alternatively, is there some simple argument I'm missing to show that the transition matrix in this case is double stochastic?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

Shuffles like the overhand shuffle or riffle shuffle are not just random walks, they are symmetric random walks because you apply a random permutation drawn from the same distribution no matter what the initial configuration is. You can apply a shuffle with the cards face down. (That's not the case for non-shuffle random walks like "Deal out the first 5-10 cards and sort them.") The transition matrices are automatically doubly stochastic. They preserve the uniform distribution.

As long as there is some $t$ so that after $t$ shuffles, all permutations occur with positive probability (the shuffles generate $S_n$ and not all shuffles are odd), then the Perron-Frobenius theorem says that the limiting distribution is uniform, and the question is how long it takes to get close to uniform by various metrics.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This is standard. All you need to prove is that the chain is irreducible and aperiodic. See, e.g., Proposition 1.7 in Levin, Peres and Wilmer's book here: pages.uoregon.edu/dlevin/MARKOV . $\endgroup$
    – Ori Gurel-Gurevich
    Commented May 16, 2016 at 12:18
  • 1
    $\begingroup$ @OriGurel-Gurevich I've already read the proofs that for any irreducible and aperiodic Markov chain there is such a value of $t$, but I have to say it's not clear to me why this particular chain should be irreducible and aperiodic. $\endgroup$
    – Jack M
    Commented May 16, 2016 at 13:16
  • 2
    $\begingroup$ @Jack M: There is a positive probability to apply to identity permutation, thus it is aperiodic. There is also a positive probability to transpose any two adjacent cards. It is easy to see that you can generate any permutation by transposing adjacent cards, thus it is irreducible. $\endgroup$
    – Ori Gurel-Gurevich
    Commented May 16, 2016 at 18:10
  • $\begingroup$ Thanks, I see now. Since I'm unfamiliar with this area I seriously overthought it. The uniform distribution is stationary because if $S$ is the shuffle and $X$ is the uniformly distributed prior state of the deck, then $$P(SX = \pi)=\sum_{\sigma\in S_n}P(X=\sigma)P(SX=\pi\sigma^{-1})=\frac1{n!}\sum_{\sigma\in S_n}P(SX=\pi\sigma^{-1})=\frac1{n!}$$ $\endgroup$
    – Jack M
    Commented May 16, 2016 at 22:13
2
$\begingroup$

The answer to the question you posed in the final paragraph:

Is there some more general result about random walks on finite groups or on $S_n$ which predicts that the limiting distribution is $U$?

is yes.

A random walk on a finite group $G$ converges to $U$ as long as the driving probability is not concentrated on a subgroup (irreducibility) or coset of a normal subgroup (aperiodicity).

A proof may be found in here (theorem 1.3.2).

Improve this answer
$\endgroup$
0
$\begingroup$

These questions are addressed (without any ergodic machinery) in my old paper (there are also more recent versions, which are written up a little more carefully) - see Section 9 and 10, in particular. There are explicit convergence estimates, too. The only point about the overhead shuffle is that the overhead permutations generate $S_n,$ which is basically an exercise.

Improve this answer
$\endgroup$

You must log in to answer this question.

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