# Shuffling decks of cards where not all cards are distinguishable

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 shuﬄes are necessary to randomize a standard deck of cards?

-
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
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