BGonline.org Forums

Diaconis on Randomness

Posted By: Douglas Zare
Date: Wednesday, 22 May 2013, at 9:32 p.m.

In Response To: Diaconis on Randomness (Colin Owen)

I agree with Colin Owen.

I've complained about the "it takes 7 shuffles" statement many times. It is an easy urban legend to pass around, but you can't reconstruct what the result is supposed to be from the statement. It mutates, and people come up with false versions that they spread. Then, since they have spread them, and they don't want to think of themselves as fools, they cling to the false versions almost as tightly as to axioms.

A perfect riffle shuffle exactly interleaves the cards from two packets of 26. There are two choices: you can preserve the top card (and bottom card) of the deck or not. If you preserve the top card of the deck, then this perfect shuffle returns to the original position after 8 repetitions. This is because there is a simple description of the riffle shuffle. If the cards are numbered 0,1,2,...,50,X, then they move to locations 0,2,4,6,...,100,X mod 51, where the bottom card X stays fixed. So after 2 riffle shuffles, they are in positions 0,4,8,12,...,200,X mod 51, and after 8 they are in positions 0, 2^8, 2^8 * 2, 2^8 * 3, ..., 2^8 * 50, X mod 51. And 2^8 = 256 = 1 mod 51 (hmm, a backgammon audience already knows what 2^8 is), so the cards are back in their original positions. One very hard magic trick is to learn to do a perfect shuffle, and do this 8 times, and get the deck back into its original order this way. It has been said that Persi Diaconis (who was a professional magician before becoming a mathematician) can do one perfect shuffle with a reasonably high probability, but that he could not do 8 perfect shuffles in a row reliably enough. I don't know if that's just an urban legend, though. It's easier to do false shuffles, which look like they are shuffles to the audience, but which don't change the order of the cards. For example, you can push the two halves of the deck through each other and put the top half back on top. Magicians also switch out the entire deck for a prepared deck. Anyway, if you are doing perfect riffle shuffles preserving the top card, then 8 shuffles won't look right, although 7 would still look far from random: As, 3s, 5s, 7s, 9s, Js, Ks, 2d, 4d, ... If you choose the opposite method, then you are really doubling the index mod 53, and the first time you get back to the original is after 52 shuffles, since 2^52 is the first positive power which is 1 mod 53. (If you combine the two methods, for some deck sizes you get very interesting groups far smaller than the whole symmetric group. This was also studied by Diaconis.)

However, most people aren't doing anything close to perfect riffle shuffles. Their shuffling is closer to the binomial model mentioned, the inverse of dealing out the deck into two piles according to 52 fair coin tosses. Then there is nothing wrong with shuffling more than 7 times, and it is better than 7.

By the way, it's very easy to describe making n binomial shuffles. The inverse is to deal each card into one of 2^n piles at random, then collect these piles in order. It's easy to see that if every card goes into its own pile, then you can say nothing about the ordering. Any remaining nonrandomness from n riffle shuffles can only come from times that you deal cards to the same pile. This gives an easy bound that something like 12 shuffles should get you close to a uniform distribution. If you deal the cards out into 2^12=4096 piles, there is a good chance that each card is in its own pile -- 52 people would have a good chance to have distinct birthdays if there were 4096 days in the year. That 7 shuffles starts to get you close is harder to prove, but Persi Diaconis is a great mathematician, and he (or his coauthor) saw how to apply ideas from the "representation theory of the symmetric group."

I'm far from convinced that the way people actually shuffle is that close to the binomial random riffle shuffle. I think with actual shuffles, you don't put in 52 bits of randomness. Well, I don't. I think it depends on the person, and some people might only put in 20 bits of randomness (which would still mean there are a million possible shuffles you could make), in which case it will take almost 20 shuffles before it's possible that the deck is close to uniform. I think the mathematical model of the binomial riffle shuffle is so nice for mathematicians, and so confusing for others, that people overlook that it may be a poor model for what happens.

Persi didn't get to it in that talk, but one of his transparencies mentioned bridge hands. One application of shuffling theory was to explain what was wrong when bridge tournaments switched to computerized shuffles, and people got less even distributions than they expected, more hands with say, 8 out of 13 of your cards of one suit. The answer was that the computerized shuffles were fine. Previously, people had manually shuffled the deck after sorting their hands into clumps, either within a hand or by playing cards of the same suit on top of each other. After these clumps were insufficiently shuffled, dealing out the cards one at a time tends to deal cards of the same suit to different players, which makes it much less likely that someone has most of the cards of one suit. So, the old method for shuffling was wrong, and it had consequences that hands which should have happened 2% of the time happened only 1%, and people noticed the difference. At least, that's the explanation I've heard. It's also possible that there was no real difference, but when there was some potential difference people started noticing the hands with extreme distributions and suspected that there was a problem, much the way people complain about the dice on every single backgammon server.

Douglas Zare

Post Response

Subject:
Message: