MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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, "Strong uniform times Shuffling cards and finite random walks"stopping times", Advances in Applied Mathematics 8The American Mathematical Monthly 93:1 5 (1987).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?

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. Aldous 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, "Strong uniform times and finite random walks", Advances in Applied Mathematics 8:1 (1987).

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

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

1

# 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. Aldous & 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, "Strong uniform times and finite random walks", Advances in Applied Mathematics 8:1 (1987).

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

[3] Michael P. Salem, How many shuﬄes are necessary to randomize a standard deck of cards?