Birthday Attacks and Stacked Decks

Question

So this may be a common question, I have no idea. Similar to the birthday paradox, I was wondering how many times one would need to shuffle a 52 card deck (assuming instant shuffles, no set starting point, and no human patterns in shuffling) before a repeat order is statistically likely. I know that 52! is an incredibly high number, but the odds for a repeat must be much more likely since not every combination would need to happen before a repeat does.

As an aside, is there a way to mathematically account for things like the fact that every deck of cards starts off in the same order, and that people have patterns in shuffling? Most people divide the deck in half, putting the top half in their dominant hand before riffle shuffling. Short of putting each individual card down, then picking them up in a random order, I would imagine that these patterns significantly increase the likelihood of a repeat deck order.

Answer 1

Let's say we are repeatedly and independently performing a random experiment with $N$ different outcomes, all of which have the same probability $N^{-1}$, where $N$ is large.

The probability of no repeated outcome in $k+1$ trials is $\prod_{i=1}^k (1-\frac{i}{N}) \approx \prod_{i=1}^k \exp(-\frac{i}{N}) = \exp(- \frac{k(k+1)}{2N})$.

For this to be substantially less than 1, e.g. $ < e^{-1}$, you would need $\frac{k((k+1)}{2N} > 1$ or approximately $k > \sqrt{2N}$. If $N = 52!$, this means at least $\sqrt{2 \cdot 52!} \approx 1.27 \cdot 10^{34}$ repetitions. That is still a very large number.

I believe this argument is well known and has most likely been made precise somewhere.

Answer 2

The probability that $n$ samples drawn from $d$ equally likely possibilities contain a repeated sample is roughly $$ p(n,d)\approx 1-e^{-n^2/2d}. $$ In your case, assuming perfect shuffles, $d=52!$. So the number of shuffles required before there is a $50\%$ chance of a repeat is $n \approx \sqrt{2d\log 2}\approx 10^{34}$. Still pretty large.

Answer 3

On the topic of patterns in shuffling: A perfect shuffle of a deck of cards is one in which you cut the deck exactly in half and interlace the two halves perfectly. There are two versions: In an out shuffle the original top card remains on top; an in shuffle leaves the original top card second from the top. In The Mathematics of Perfect Shuffles by Diaconis, Graham, and Kantor, the authors note that it takes only eight out shuffles to return a deck to its starting order, versus 52 in shuffles to recycle the deck.

Perfect shuffles have long been used by magicians and gamblers to manipulate cards to their advantage, but they are hard to achieve. In Shuffling Cards and Stopping Times, David Aldous and Persi Diaconis remark that "...professional dealers drop single cards 80% of the time, pairs about 18% of the time and hardly ever drop three or more cards."