5
$\begingroup$

It is known that 7 random riffle shuffles are enough to make almost every configuration equally likely in a deck of 52 cards.

Perfect Shuffle is when you cut the cards exactly in half and perfectly interleave the cards from the two halves.

In-Shuffle is Perfect Shuffle in which top card from the top half remains top after the shuffle, while Out-Shuffle is one in which bottom card from the first half becomes bottom (in other words top card becomes second) after the shuffle.

Question:

If randomly chosen In and Out Shuffles are performed on a deck of 52 cards, how many shuffles are needed to make almost every configuration equally likely?

$\endgroup$
  • $\begingroup$ In/out-shuffle are still mixed up. Out-shuffle is the one where top stays at top and bottom at bottom. $\endgroup$ – Sleafar Oct 11 '15 at 18:13
  • $\begingroup$ What do you mean by "almost every configuration"? $\endgroup$ – xnor Oct 12 '15 at 0:18
8
$\begingroup$

No amount of in-shuffles and out-shuffles will approach a random shuffle.

Let's say that two cards mirror each other if they are the same distance from the middle of the deck. This means that the $i$th and $j$th cards from the top mirror each other if and only if $i+j=53$.

If two cards mirror each other, then after the deck is either in-shuffled or out-shuffled, they will still mirror each other. This means that the result of several in/out-shuffles is uniquely determined by the top 26 cards, so that at most $2^{26}\times 26!$ of the $52!$ deck permutations can be achieved by in/out shuffling.

$\endgroup$
3
$\begingroup$

I think it is impossible. Using $52$ cards there are $52!=8.06*10^{67}$ possible combinations of cards. Using in/out-shuffles randomly we have potentially $2^n$ possibilities after $n$ shuffles. To reach at least $52!$ combinations this way we would need at least $226$ shuffles.

Let's look at the situation after $104$ shuffles. The interesting feature of in/out-shuffles is that $8$ out-shuffles in a row return the deck to the starting position. The same applies to $52$ in-shuffles. So after $104$ shuffles we have at least $2$ cases with the starting position again, and not enough other cases to cover all other combinations. After a total of $208$ shuffles we have more than $4$ cases with starting position and not enough cases to cover the rest, and so on.

Therefore we will never reach a situation where all shuffles are equally likely.

$\endgroup$
  • $\begingroup$ I think we need some numerical constraints, like where "at least six sigmas of shuffles have probabilities within a relative variation of $\pm 5\%$", to be able to give a numerical answer. $\endgroup$ – Joe Z. Oct 11 '15 at 18:57
  • $\begingroup$ @JoeZ. Sorry, can you repeat that for a non-math-student? $\endgroup$ – Sleafar Oct 11 '15 at 19:14
  • $\begingroup$ Basically, the likelihood of any given permutation being more than 5% away from the average probability (1 in 52!) should be less than about 1 in 500 million. en.wikipedia.org/wiki/68–95–99.7_rule $\endgroup$ – Joe Z. Oct 12 '15 at 5:25

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.