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](http://www-stat.stanford.edu/~cgates/PERSI/papers/aldous86.pdf)", *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](http://www.jstor.org/stable/2959752)


[3] Brad Mann, [How many times should you shuffle a deck of cards?](http://www.dartmouth.edu/~chance/teaching_aids/Mann.pdf)


[4] Michael P. Salem, [How many shuﬄes are necessary to randomize a standard deck of cards?](http://cosmos.phy.tufts.edu/~salem/Documents/shuffle.pdf)



Shuffling decks of cards where not all cards are distinguishable
A place to start is the recent preprint:


[Riffle shuffles of a deck with repeated cards](https://arxiv.org/abs/0905.4698)
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](http://www.math.lsa.umich.edu/%7Edivakar/).


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.


