Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
The famous result about 7 riffle shuffles is actually due to Bayer and Diaconis here: jstor.org/stable/2959752 –  Mark Meckes Jun 2 '10 at 13:22
1  
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). –  Mark Meckes Jun 2 '10 at 13:26
    
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. –  Charles Jun 2 '10 at 14:07
    
Strangely, I corrected the same misattribution on a well-known blog recently. –  Mark Meckes Jun 2 '10 at 15:20
    
My mistake was misreading reference 1 for reference 2 in Mann's paper; perhaps the blog author did the same thing? –  Charles Jun 2 '10 at 16:58
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  Charles Jun 2 '10 at 16:58
    
Though in that special case you can just shuffle the U cards then integrate in a single shuffle... –  Charles Jun 2 '10 at 17:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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