Tags

, , , , , , , , ,

shuffle

***

Yesterday, card magician Derek DelGaudio appeared on NPR radio’s quiz show, Ask Me Another, where his quiz category was…playing cards.

What an incredible stroke of fortuitous luck engineered by the quiz show Gods! (not)

Anyway, Derek answered questions like, “Which suit used to be represented by batons and sticks?” and “One of the four Kings’ faces is different from the other three: which, and why?” Of course Derek answered these questions correctly—he is after all performing card magic nightly in his new one man Off-Broadway show, In & Of Itself—but it was the final question that was the most amusing. Here’s how the conversation went:

Host:  “According to mathematicians at Harvard and Columbia, how many—”

DelGaudio (and magicians across the country):  “Seven!”

Host: (Stunned silence, then laughter) “Yes, correct.”

******

Spoiler: As the host later told the audience, the question’s finish was, “how many riffle shuffles does it take to fully shuffle a deck into a randomized state?”  It’s a more interesting question than might appear at first glance, with quite a few sticky points.

First of all, is it referring to any kind of shuffle? No; it applies specifically to the riffle shuffle, also known as the dovetail shuffle—the deck is divided into two packets, one packet held from above in each hand, with each thumb at one short end of the cards, and the other fingers at the opposite short end. Then some cards are riffled off the bottom of one packet by the thumb onto the table, and next, some cards are riffled off the bottom of the other packet by the other thumb onto the table. This is repeated, riffling off cards from the bottom of the two packets onto the table, alternately, until both packets are exhausted (or at least a little bit sleepy). Most bridge players are familiar with this kind of shuffle.

Do the cards have to be perfectly alternated, one card from each hand, in perfect syncopation (magicians call this a “faro shuffle”)? Again, the answer is no. There is no requirement that the cards be perfectly interlaced, nor that the deck be cut into two even packets at the beginning. But even with imperfect shuffling, the cards should be fully randomized after seven riffle shuffles.

With some reflection, one might ask, what does it even mean to say that the cards are now in a random order? Isn’t every order a random order? The whole question of randomness is non-trivial, but a quick and dirty explanation as applied to shuffling depends on two notions. First, suppose we number all the cards in a deck consecutively from the top, 1-52.  Now we shuffle the deck. When we look at our new shuffled order, are there any clues in the new order that might lead us to suspect what the original order might have been? For example, if the new order looked like 1-20, 26-40, 21-25, 41-52, we can see that the “chunks” from the original order have left a calling card of sorts of the previous order; we would not say that the shuffle had randomized the order yet. The other thing to realize is, that given our original stack ordered 1-52, it is not true that every other conceivable stack could be obtained by one riffle shuffle—even if we were allowed to decide exactly how the cards should fall. For example, if we wanted a new stack that began 2-1-7-3 on top, there is no way of splitting the original 1-52 stack and doing one riffle shuffle that would put those four cards on top.

So, now we are in a position to talk about what a randomly shuffled deck would mean. It means that if we were to compare the positions before shuffling and after shuffling, there would be no clues left as to what the original order was; and that the new order was just as likely to have resulted from the actual beginning order as from any other beginning order. It turns out that only if you riffle shuffle at least the magic seven times, can you be sure that the preceding two conditions are true.

This result was proved by Persi Diaconis, presently a professor of mathematics at Stanford University, but also one of the most intriguing and elusive figures in modern sleight-of-hand conjuring.  When he was 14, he ran away from home and joined a much older magician, Dai Vernon, on a cross-country scramble to track down the best underground card sharks in America. The idea was to learn new card sleights that other magicians had not yet discovered. Diaconis was so intrigued by gambling questions that he enrolled in college math courses to learn the math that would give him more insight into such problems. Later on, Diaconis got himself a teaching post at Stanford on the recommendation of the Scientific American columnist Martin Gardner. Gardner it turns out, was a first-class amateur magician; Diaconis had shown him a few card tricks that he had invented, and on the strength of those card tricks, Gardner recommended Diaconis to the department head at Stanford who then hired Diaconis.

Diaconis has since published papers on many topics of potential interest to magicians and gamblers, including a proof that when flipping a fair coin, it is slightly more likely to fall on the side it started on. Equally intriguing is Diaconis’s tight-lipped attitude towards questions about the now-deceased Vernon. Vernon had many acolytes, most of whom have shared in print or video what Vernon had taught them. Vernon himself was not averse to revealing some of his confidences. But Diaconis is one of the few who refuses to speak about any of the Master’s teachings, and believes that some mysteries are meant to be taken to the grave.

But Diaconis’s riffle shuffle paper is well known among magicians. So now you know why Derek DelGaudio didn’t need to hear the rest of the question…