6
$\begingroup$

Suppose a deck of cards consists of $a_1+a_2+\cdots+a_k$ cards of $k$ types, where there are $a_i$ indistinguishable cards of each type. How many shuffles does it take, on average, to randomize the deck? For example, $a_i=4$ and $k=13$ gives a standard deck of playing cards; $a_i=4$ for $1\le i\le9$, $i_{10}=16$, $k=10$ gives the cards for blackjack.

In general I would expect that this would be an easier task than shuffling a deck where all cards are indistinguishable. A standard deck has about 226 bits of entropy, while the same deck without suits has only 166 bits of entropy.


Consider a standard deck of 52 playing cards. Bayer & Diaconis (famously) showed that, under a certain model, it takes 7 riffle shuffles to sufficiently randomize the deck. Salem applies a different methodology and gets 6 idealized riffle shuffles. Mann uses a much stricter measurement and determines 11.7 as the expected stopping time for the riffle unshuffle (and thus the riffle shuffle) to randomize the deck.

In particular, Mann gives a formula: $$E(\mathbf{T})=\sum_{k=0}^\infty\left[1-{2^k\choose n}\frac{n!}{2^{nk}}\right]$$ which lends itself to generalization nicely.

I'm partial to Mann's method, but my question applies broadly.


[1] David Aldous and Persi Diaconis, "Shuffling cards and stopping times", The American Mathematical Monthly 93:5 (1986), pp. 333-348.

[2] Dave Bayer and Persi Diaconis, "Trailing the dovetail shuffle to its lair", The Annals of Applied Probability 2:2 (1992), pp. 294-313. JSTOR: 2959752

[3] Brad Mann, How many times should you shuffle a deck of cards?

[4] Michael P. Salem, How many shuffles are necessary to randomize a standard deck of cards?

$\endgroup$
5
  • 1
    $\begingroup$ The famous result about 7 riffle shuffles is actually due to Bayer and Diaconis here: jstor.org/stable/2959752 $\endgroup$ Jun 2, 2010 at 13:22
  • 2
    $\begingroup$ Also, depending on what you mean by "sufficiently", one might just as well say Bayer and Diaconis showed it takes 10 riffle shuffles. See Table 1 in the paper I linked to (assuming you have access to JSTOR). $\endgroup$ Jun 2, 2010 at 13:26
  • $\begingroup$ Thanks, Mark! I actually read their paper, but in my sleepy haze last night I misattributed it. Thanks for clearing that up, I'm sure that would have confused others. $\endgroup$
    – Charles
    Jun 2, 2010 at 14:07
  • $\begingroup$ Strangely, I corrected the same misattribution on a well-known blog recently. $\endgroup$ Jun 2, 2010 at 15:20
  • $\begingroup$ My mistake was misreading reference 1 for reference 2 in Mann's paper; perhaps the blog author did the same thing? $\endgroup$
    – Charles
    Jun 2, 2010 at 16:58

1 Answer 1

7
$\begingroup$

A place to start is the recent preprint:

Riffle shuffles of a deck with repeated cards Sami Assaf, Persi Diaconis, K. Soundararajan.

They also have another preprint about reducing this to a "rule of thumb", and cite some earlier work of Conger and Viswanath, available here.

Pulling carelessly from tables in the different papers without checking exactly what I'm saying, it seems that in the total variation distance, (the measure which yields seven shuffles for a standard deck), four shuffles are already sufficient for blackjack, while for the separation distance (the measure yielding eleven shuffles for a standard deck), it still takes nine shuffles.

$\endgroup$
2
  • $\begingroup$ That's it, perfect! Theorem 4.2 ff. are just what I hoped for. I also see that this solves the other question I was considering: how many shuffles are needed to integrate U unshuffled cards into S shuffled cards: treat the shuffled cards as indistinguishable and apply the formulas from the paper. $\endgroup$
    – Charles
    Jun 2, 2010 at 16:58
  • $\begingroup$ Though in that special case you can just shuffle the U cards then integrate in a single shuffle... $\endgroup$
    – Charles
    Jun 2, 2010 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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