information theory Given a deck of n cards, how many times must we shuffle it to make it “random”?

Question

I am new to information theory and I am not sure where the error is in the following:

The question is: Given a deck of n cards, how many times must we shuffle it to make it “random”? I know the answer is 6 but I have encountered someone who claims it is 5 because of the following: there are $52$ ways to order a normal deck of cards and therefore there are $\log_2 52! = 225.58$ bits of information.

Let's define the process of riffle shuffle as follows:
A riffle shuffle consists of a cut of the deck into two stacks and an interleaving of the two stacks. We can cut in any of 52 places and the interleaving can be non-perfect. which means that if we have cut into stacks of $r$ cards and $52-r$ cards, and in the interleaving, we need to choose r place for the r card in the first stack to be so we have ${52}\choose{r}$ options
therefore $\sum_{r=1}^{52} {{52}\choose{r}} = 2^{52}$. meaning $52$ bits of information.
$225.58 / 52 = 4.33$ rounding up we get 5.

Answer 1

There are two problems with this approach. One is the computation of $52$ bits per shuffle ignores the fact that many of the shuffles produce the same output. For example, the shuffle that results in the same order as you started with can come from cutting the pack at any point, then stacking the old top on the old bottom. You have counted these as $52$ different shuffles but it is really only one. The other is that sequences of shuffles may result in the same deck. Let me define a crazy shuffle that is either swapping the top two cards or not. Clearly one of these contributes $1$ bit of entropy to the state of the deck. However, doing it $226$ times does not add $226$ bits of entropy as there are still only two possible orders it can produce.

I have seen numbers like $7$ or $8$ but this is just based on experience saying the deck is well mixed after that many. I strongly doubt you can get a uniform distribution over the $52!$ possible decks with any reasonable amount of shuffling. Small numbers are sufficient to break up long runs of one suit.

Answer 2

The question can be answered by studying the mixing time of Markov chains that represent the riffle shuffle. I believe the famous paper from Diaconis and Bayer has the result you need. Given a deck of $n$ cards, you need about $\frac32 \log_2n$ shuffles to make the deck "random".

What they show is that if the distribution over all arrangements of cards is given by $P^k$ after $k$ shuffles, then $\|P^k-U\|_{\mathrm{TV}}$ becomes close to $0$ when $c \geq \frac32 \log_2n$, i.e., the current distribution is arbitrarily close to the uniform one in total variation distance. Here, $U$ denotes the uniform distribution over all cards arrangements.

Another paper looked at the same problem but using the KL-Divergence instead of the total variation distance, and they show that in that case one needs only about $\log_2n$ shuffles to make the KL-Divergence arbitrarily close to $0$.