It's all in how you shuffle the deck

The Astounding card trick

Ladies and gentlemen, I will now perform for you the celebrated John the Math Guy card trick. Without the use of PhotoShop or other devious means of deception, I will shuffle an ordinary deck of cards not once (as in tricks performed by the far less talented Rupert the Math Guy), but twice. 

Yes, my friends, I said that two times I will invoke the Goddess Tyche, the Greek (or Roman or whatever) goddess of luck. Twice I will knock on her gates and implore her to make my deck of cards be like unto a random ordering in her sight.

Please turn your attention to the first photograph below - an actual unretouched photograph of the order in which I have placed the deck before my heretofore unprecedented act of prestidigitation. Note the orderliness of the cards, as befits an applied mathematician of my lofty stature. I have proof of the veracity and authenticity of this picture on file in the form of a document to which has been affixed the paw prints of my dear and most honorable dog, Scrabble, attesting to the undeniable fact that all I am relating is the absolute truth.

The actual cards used in this actual experiment before the actual experiment takes place

Now, please watch carefully as I perform the act of shuffling this ordinary deck of cards. The procedure is tripartite in that there are three parts. First the deck is cut roughly in half. (Preferably, it is cut lengthwise and parallel to the face of the cards.) The right and the left hand take the first and second half of the deck, respectively.

Second, the two half-decks are "riffle shuffled", as shown below. The cards are flexed and the thumbs are slowly moved to allow the cards to be flapped downward under the inducement of the flexing. As is well known to one skilled in the art, the order that the cards fall, left or right, is governed solely by the whims of Lady Tyche.

The riffle step of the riffle shuffle

In the third and final step of this tripartite procedure, one applies a reverse flexing of the cards so as to propel them out over the table to the embarrassment of the dealer. The random nature of collecting the cards back into a deck is how randomness is attained.

Friends, with Dog as my witness [1], I am here to tell you that I performed this very procedure exactly twice. Surely if Tyche has provided us with a completely random order by virtue of the first riffle shuffle, then the second process of riffle shuffling should leave us with an even more random order. But to the amazement and perplexification of all in my reading audience, the following unretouched photo shows but a sampling of the bewildering arrangement of the deck. I show the top ten cards of the deck, which include the unbelievable quantity of no less than four kings, and the even more unbelievable quantity of four queens... all in the very topmost ten cards. 

First ten cards in the deck after two riffle shuffles

Explanation

There is no trick here. It took me a few tries to get these results, but these are actual results. I am not a skilled magician, and definitely not a skilled card player. I have been to Vegas only once, and that was for a convention. Let me tell you, the gaming tables are pretty lonely when the annual Math Guy convention hits town! But at least the bars are busy. And the show girls.

If one has executed the riffle shuffle perfectly, the last card down is (let's say) the king of spades. The next to last down will be king of clubs from the other hand. Prior to that, the queen of spades falls, and prior to that, the queen of clubs, and so on. When the deck is split in half for the second riffle, the deck is cut between the two black aces and the two red kings. (Ok... truth be told, I cheated and glanced at the cards as I cut the deck so I could get the correct split. Scrabble didn't catch that.)

It does not take a whole lot of practice to be able to amaze your own friends with this trick. A reasonably well controlled riffle will readily produce a pattern after two shuffles that is clearly not random. This is not rocket science, but anyone who has settled for two shuffles of the deck clearly has not thought this through.

How many times should you shuffle?

Which brings me to the practical question... how many times should you shuffle? I am sure there are many statistically valid ways to look at this question, but I offer one approach that is relatively simple. I start by considering the very top card, which in the illustration of the virgin deck was the king of spades.

I make the simplifying assumption that corresponding cards (that is, the fifth card of the half-deck on the right side, and the fifth card of the half-deck on the left side) will square off and the two will fall in random order. Thus, after the first "perfect" riffle, the king of spades might still be on top, or he might have dropped to the position of the second card.

"No... you go first, I insist"

If the king fell to the second position after the first riffle shuffle, then he will square off with the second card on the other side and wind up in either the third or fourth position after the second riffle. If he makes it down to the fourth position he has a chance to make it to the eighth position after the next riffle. With each additional riffle shuffle, the possible extent that the king may have traveled is doubled.

Thus, under these simplifying assumptions, one needs to shuffle the deck at least six times in order to make it possible for the top card to move to any other position. Wow. I can't imagine any group of card players having the patience to allow someone to shuffle that much!

Scrabble playing poker with some of his buddies

Schafkopf and the riffle shuffle

If you happen to be from Wisconsin, you will know that "Schafkopf" (also known as sheepshead) is a card game. If you are lucky enough to have had someone try to teach you the game, you will know that the queen of clubs takes all, but is only worth two points (or was it three?), whereas the tens are all worth ten points, but don't take many tricks at all. Kings, of course, are four points. The seven of diamonds (which is worth no points at all) will take the ace of spades, which is a good thing, since the partner (one of four players aside from the fellow who picked) has the called ace and has to play it when someone leads that suit. And that's eleven points. I mean the ace is eleven points. If this happens (I mean the seven of diamonds thing) and you are the picker, you better hope you buried some points in the blind so you can at least get schneider, cuz people are likely to schmear!

Sheepshead is often played with five people, and most frequently with a sixth player alternately sitting out so they can deal and then refill everyone else's beer. If you happen to be from Wisconsin, you will be familiar with this amber liquid. If you happen to be from Wisconsin and play sheepshead (but I repeat myself), you will understand that it is impossible to remember all the darn rules for sheepshead without large quantities of this amber liquid. Some have gone so far as to say that beer was invented just so that that people would be able to play sheepshead. 

I mention sheepshead first off because it is the only thing in Wisconsin that is sillier than a cheesehead hat [2]. But more importantly, I mention it because I have a secret to tell - one that up until now, no one else has known.

The cheesehead hat

Sheepshead uses a deck of 32 cards. (That's not the secret, by the way.) If you were to do five perfect riffle shuffles (where the cards fall first from the right side, then the left, then the right, and so on, always starting from the right side) on a sheepshead deck, you will be back exactly where you started. The deck will appear to have not been shuffled at all.

How do I happen to know this? I am glad you asked, because it allows me to brag. Way back in 1984, when most computers were built from Tinkertoys, I built an image processing computer that could perform two dimensional fast Fourier transforms on images. Exciting stuff. Good resume fodder. I mean, what real applied mathematician hasn't taken a youthful foray into Fourier space? I spent at least four years being spaced out in the foyer.

MIT's Tinkertoy computer

I envisioned at the time a faster fast Fourier transform computer, one which utilized 16 or 32 or 1,024 individual processors, each working on their own part of the data. The difficulty in this design is that eventually the processors would need to share data with other processors - not just any processors, but very specific ones. The riffle shuffle provided exactly the right connections for the proper data sharing. In the first pass, the deck (the data array) is split in half, and adjacent pairs are combined. In the second pass, the array is once again split in half... and so on.

Looking at the FFT flowchart below, it looks as though that second pass does not split the deck in half, but rather into quarters. The difference is that in the traditional algorithm, the results of the combination of the first and the n/2th entry goes in the first location and the n/2th location. There is no shuffling in the traditional algorithm, as there is in my riffle shuffle FFT algorithm. As a result, the data points to combine are always the same in the RS FFT - data points in the first half of the array are always combined with the corresponding points in the second half. This is the magic that makes this the perfect algorithm for a group of 2ⁿ processors. The processors that need to pass data amongst themselves are always the same.

FFT butterflies follow the perfect shuffle

When implemented in a standard processor, there is a small benefit to the RS FFT algorithm. The standard FFT requires a final step of de-scrambling the array. The RS FFT algorithm does not require this. The final results are in the correct order.

And that's how I figgered out that five perfect riffle shuffles will restore a deck of cards to it's original order.


I never built this processor or even filed for a patent, but I still think about it whenever I am playing sheepshead and my deal comes up.

------------------------------------------

[1] The Dog in question can be plainly seen in the painting that can be seen between my wrists in the riffle shuffle photo. This is a painting of Scrabble the Shitsu. For more examples of my sister's excellent portraiture, please have a look at Jean Kelly's website. Scrabble was also the model for my blog post on mathematical misnomers.

[2] Disclaimer - While I mention the cheesehead hat, show a picture, and provide a link for where to buy one, I neither promulgate nor disparage wearing the C.H. hat. Those who choose to wear one on a first date, job interview, or wedding ceremony do so at their own risk.