0
$\begingroup$

So we are having a discussion with my friends. One is saying that if he shuffles a deck of cards x amount of times and then somebody else shuffles it again, the deck after the second shuffle is more shuffled than the deck shuffled after one time.

I think it is not the case cause there is only 52! ways to shuffle a deck of cards, so no matter how many times you shuffle it, it still be as shuffled as if you only shuffled it once.

What do you all think?

$\endgroup$
  • 4
    $\begingroup$ statweb.stanford.edu/~cgates/PERSI/papers/aldous86.pdf $\endgroup$ – saulspatz Aug 22 at 1:39
  • 6
    $\begingroup$ Define "more shuffled". (Not kidding. When you say "there is only $52!$ ways", you are saying that all orders are equally shuffled, but the rest of your question seems to suggest that some orders are more shuffled than others.) $\endgroup$ – Eric Towers Aug 22 at 1:39
1
$\begingroup$

If by "shuffle" or "shuffles" you mean application of a uniformly distributed permutation, or of independent uniformly distributed permutations, then of course you are right. The buzz word here is "Haar measure" on the group $S_{52}$.

But if the second shuffle is cleverly chosen to be the inverse of the first, then of course the combined shuffling effect is trivial. In this case the random permutations are not independent.

If the successive shuffles are independent but not uniformly distributed (as is the case in the Diaconis and Aldous paper cited in a comment) then things get mathematically interesting: the second shuffle might well make the card deck more random than just the first shuffle alone, and one might (as those authors do) try to figure out, in quantitative terms, how much good repeated shuffles do.

$\endgroup$
0
$\begingroup$

To complete the answer by kimchi lover by a precise statement proving the non-increasing property the OP mentions : Exercise 4.4 p.59 of "Markov chain and mixing times" by Levin Peres.

Let $P$ be the transition matrix of a Markov chain with stationary distribution $\pi$. Let

$$d(t)=\max_{x} \|P^t(x,\cdot)-\pi\|_{TV}$$

be the worst-case total variation distance between $P^t(x,\cdot)$ and $\pi$. Prove that for any $t \ge 0$, $$d(t + 1) ≤ d(t).$$

A quite remarkable property. Notice that, in this setting (homogeneous Markov chains), the law of your independent shuffles are allowed to depend on the state $x$ but not on $t$. See :

https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.