Timeline for Why does the overhand shuffle converge to the uniform distribution on $S_n$?

6 events

when toggle format	what		by	license	comment
May 16, 2016 at 22:14	vote	accept	Jack M
May 16, 2016 at 22:13	comment	added	Jack M		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!}$$
May 16, 2016 at 18:10	comment	added	Ori Gurel-Gurevich		@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.
May 16, 2016 at 13:16	comment	added	Jack M		@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.
May 16, 2016 at 12:18	comment	added	Ori Gurel-Gurevich		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 .
May 16, 2016 at 12:02	history	answered	Douglas Zare	CC BY-SA 3.0