I’m not good at shuffling cards. I can eventually scramble up a deck tolerably well, given time, but I can’t do a good riffle shuffle. Nor can I do any of the moves that show competence at card-shuffling. That thing where people make a little semicircular arch of cards in their hands? I can’t even understand how that works, never mind do it myself.
That said, I do know how many shuffles it takes to randomize a deck of cards. I mean a standard deck of 52. It’s seven. I learned that ages ago, but never saw it proved. Best I could work out was that each shuffling would, if done perfectly, mix the upper and lower halves of the old deck. So I want what had been (say) the first and second card to be mixed up arbitrarily far from one another. One shuffle might get one or two cards between the old first and second. Two shuffles might double that; three shuffles that again, and so on. By six shuffles there could be anywhere up to 64 cards between the first and second, and that’s … surely enough, right? Then one more for good luck? It’s not rigorous but you can see where that satisfies.
The Probability Fact of the Day tweet above gives a real explanation. It links to the paper Trailing the Dovetail Shuffle to its Lair, by Dr Dave Bayer and Dr Persi Diaconis. It first appeared in the Annals of Applied Probability, 1992, Vol 2, Number 2, 294 – 313. It gives an actual proof of why seven shuffles are what’s needed.
I’m sad to admit the paper isn’t one you can jump into without mathematical training. Even the symbols may seem bizarre: it uses π not for that thing to do with circles. Instead it’s used as a variable name, the way we might use ‘x’ in ordinary algebra. In this context it stands for ‘permutation’. That’s a standard thing to do in this field of mathematics. It just looks funny if you’re coming in cold.
A permutation, here, means how you change the order of things. For example, suppose we start out with five things, which I’ll label with the letters of the alphabet. Suppose they start out in the order A B C D E. (We could use other labels, but letters are convenient.) I can apply a permutation π to this ordered list of letters. Suppose that afterwards they end up in the order C A B E D. Then the permutation π did this: it moved the first thing to the second spot. It moved the second thing to the third spot. It moved the third thing to the first spot. It moved the fourth thing to the fifth spot. It moved the fifth thing to the fourth spot. There are several ways to describe this efficiently. I could say, for example, that the permutation π is (2 3 1 5 4). (If you don’t see why that works, think about it a while.) There’s other ways to write this. We don’t need them just now.
You can chain permutations together. If we did the same swapping of order on C A B E D, we would get the list B C A D E. That’s the same list we would have gotten if we had started with A B C D E and done a different permutation once. It’s what we would get if we had done (3 1 2 4 5). We can think of this as what you get if we “multiply” π by π. Permutations, these directions of how to shuffle a list of things, can work a lot like numbers.
There’s more interesting things in here, even if you don’t follow the argument. I admit I get lost somewhere in section 3. I’m hoping someone asks me about the baker’s transformation. But it does describe some impressive-sounding magic tricks to be done with a slightly shuffled deck. And it gives this great puzzle, as well as answering it.
Suppose someone has a well-shuffled deck of cards. She deals them one at a time. You try to guess what card is coming up next. And you never make the foolish mistake of predicting a card that’s already come up. Most of the time you’ll be wrong. But at least you’ll end on a success. After 51 cards have been dealt you will call the final one right.
How many cards would you expect, on average, to call correctly, out of these 52?