Card Shuffling: You’re Not Done Yet

When playing games involving a deck of cards, I am sometimes told that I take too long to shuffle the deck.  This is due in part to the fact that I simply do not shuffle very well, and the extra fumbling takes time.  But I also tend to shuffle the deck more times than might seem typical, reasonable, or necessary– usually 8 or 9 riffle shuffles if I can get away with it.

There is a lot of interesting mathematics involved in shuffling cards.  I will not try to re-hash all of the many applications and beautiful results here; see the references at the end of this post for some great survey reading on the subject.  Instead, I will just point out a few specific ideas that are interesting and/or new to me.

First, my interest in card shuffling was renewed recently via a rather roundabout path between related problems, beginning with “cold hit” DNA profiling, progressing from there to the birthday problem, and ending with the question of whether it is likely or not that there have ever, in the history of playing cards as we know them today, been two completely shuffled yet identically arranged decks of cards.  I think this would be a great exercise for students, particularly because of the interesting end result, namely that it is extremely likely that no two completely shuffled decks have been the same.

Of course, this raises further questions about the assumptions implied in the problem, in particular what “completely shuffled” means.  Basically, we would like the probability distribution on the set of all possible deck arrangements to be uniform… or as nearly uniform as possible.  This leads naturally to the widely cited, perhaps even “popular” anecdote due to Bayer and Diaconis, that seven riffle shuffles of a 52-card deck are needed to randomize the deck (references 1-3).

This result involves some very elegant mathematics, from the random modeling of the riffle shuffle to the choice of metric for distance between probability distributions.  More precisely, the Bayer-Diaconis result is that total variation distance from the uniform distribution first drops below 0.5 after seven GSR riffle shuffles, so named after Gilbert, Shannon, and Reeds, who first studied them.

(Last week I read a paper by Trefethen (reference 4) that considers information-theoretic entropy as another measure of randomness.  Although I do not read their conclusions quite this way, the paper seems to be cited as suggesting that only five or at most six shuffles are sufficient.  I don’t quite agree with this, as will be shown below.)

I think it is useful to consider relatively simple ways to explain and justify repeated riffle shuffling, whether to your family or friends across the card table, or to students in the classroom.  Following is an outline of three interesting arguments showing that you need at least four, five, and six riffle shuffles, respectively, at a minimum, to randomize a deck of 52 cards.

First, three shuffles are definitely not enough: Bayer and Diaconis describe a very cool card trick called “Premo,” discovered by Charles Jordan (reference 3).  The magician hands a deck to the spectator, and tells the spectator to riffle shuffle the deck three times, then cut the deck.  The spectator is then instructed to look at and remember the top card, insert it randomly into the deck, and give the deck a final cut.  The magician takes the deck and fans it on the table, and after looking at the cards for a few moments, announces the spectator’s chosen card.

This trick is surprisingly easy to learn, and with some practice I have gotten much faster at identifying the chosen card.  What is interesting is why and how the trick works… and when it doesn’t.  I have run some computer simulations of the trick, and although I can reproduce Bayer and Diaconis’s results, the probability that the trick works seems to be very sensitive to how the cuts and random insertion of the chosen card are modeled (e.g., uniformly, binomially, etc.).  More analysis is warranted here.  [Edit: That further analysis turned out to be pretty interesting.]

Four shuffles are not enough, either.  Consider weakening the requirements a bit, from demanding that all possible arrangements of cards be approximately equally likely, to simply ensuring that all arrangements are possible.  That is, how many riffle shuffles are needed to have any chance of generating each of the 52! possible arrangements of the deck?  If there are g different single riffle shuffles, then \lceil log_g 52!\rceil is a lower bound on the required number of shuffles.  We can associate every possible riffle shuffle with a binary sequence of length 52, where the number of zeros indicates the position of the cut, and the pattern of zeros and ones indicates the interleaving of cards from the top and bottom packets, respectively.  Thus, g=2^{52}, yielding a lower bound of at least five riffle shuffles.

Finally, we can refine the above argument a bit by considering the number of shuffles required to reach a particular permutation of cards.  It turns out that a reversal of the order of cards is the “hardest” permutation to reach, by considering the number of “rising sequences” in a permutation (see references 1,2).  Since a single shuffle at most doubles the number of rising sequences (this takes some work to show), we need at least \lceil log_2 52\rceil = 6 shuffles to realize the 52 rising sequences in the permutation that reverses the deck.

In summary, the above arguments show that you need at least six riffle shuffles just to have a chance of realizing all possible arrangements of the deck.  Throw in just one more shuffle “for good measure” of randomness, and the anecdotal seven shuffles seems like a reasonable guide.

References:

  1. Diaconis, Assaf, S. and Soundararajan, Riffle shuffles of a deck with repeated cards. K. DMTCS Proceedings, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 0(1):89-102. [PDF]
  2. Diaconis, Mathematical Developments from the Analysis of Riffle-Shuffling. In A. Fuanou, M. Liebeck (eds.) Groups Combinatorics and Geometry, pp.73-97, World Scientific, N.J. (2003). [PDF]
  3. Diaconis and D. Bayer, Trailing the Dovetail Shuffle to its Lair. Ann. Appl. Prob., 2(2):294-313. (1992) [PDF]
  4. Trefethen, L. N. and Trefethen, L. M., How many shuffles to randomize a deck of cards? Proceedings of the Royal Society, Series A 456 (2002): 2561–2568, doi:10.1098/rspa.2000.0625

Was the Moon Super or Not?

Recently I have been studying some of the interesting mathematics involved in DNA profiling.  That led to some even more interesting new ideas (or at least new to me) about card shuffling, of all things.  I planned on discussing one or both of these semi-related topics this weekend… but after seeing the rather beautiful “Super Moon” last night, along with several commentaries on its media coverage, I felt compelled to make a brief detour.

The motivation here comes from several online sources: blog posts at Wired, ScienceBlogs, and Bad Astronomy… and NASA.  The blog posts in particular are rather dismissive of the media hype surrounding the so-called “Super Moon,” or the coincidence of the full moon with lunar perigee.

First, most of the criticism seems to be directed, justifiably so, at the suggested links between the super Moon and natural disasters such as earthquakes, volcanoes, etc.  For astrologers, the religious, and others who seek to find patterns where none exists, the unfortunate timing of the tragedy in Japan will probably only fuel that fire.

On the other hand, I thought the treatments of the changes in the apparent size of the Moon were slightly misleading.  Perhaps it is simply that I am not an astronomer and had not bothered to perform these calculations before; at any rate, I thought the extent of the difference was not ho-hum, but actually rather interesting.

As the blogs correctly point out, the effect is due to nothing more complicated than the fact that closer objects appear larger than more distant objects of the same actual size.  The Moon’s orbit is elliptical, and last night the (full) Moon was at perigee, or the point in its orbit that is nearest the center of the Earth, about 356,577 km away.  By my calculation, at that distance the Moon (with mean radius 1,737 km) subtends an angle of about 0.56 degree in the sky, compared with only 0.49 degree at apogee (406,655 km, about 50,000 km farther away).

(Note that I am focusing on the change in actual angle subtended by the Moon, and not the so-called Moon illusion, which is admittedly a larger effect.)

The NASA site has a nice image comparing these two extremes of views of the Moon.  What I found interesting was that there, as well as everywhere else I looked, the increase in size was expressed as a ratio of apparent diameters.  That is, the common anecdote was that “the Moon appears 14% larger at perigee than at apogee.”  This comparison of linear (angular) dimension does not seem appropriate when evaluating how large a nearly-spherical object appears to a human observer.  Comparing solid angles makes more sense to me in this context, in which case the difference is more like 30%.

apparent_size

How much larger is the first circle than the second?

 

Consider the extreme example of the two circles in the above figure.  Would you say that the first circle is 100% larger than the second; that is, twice as large?  Or would you say that the first circle is 300% larger than the second, or four times as large?  The radii are in ratio 2:1, while the areas are in ratio 4:1.

(Along these same lines, beware of misleading pictorial graphs and charts in the media; USA Today has a particularly amusing track record in this regard.)

The Job Interview Question, Part 2

When I was interviewed for a software engineering job about 7 years ago, during the interview I was asked to play a game of Mastermind.  The interviewer described the game briefly, then secretly wrote down a pattern of colors.  I then provided a series of guesses of the pattern, explaining my motivation for each guess and the information that was gained from its evaluation.  (There is a simple FreeGLUT/OpenGL implementation of the game at the usual location here.)

I wonder how wacky this sounds to someone not in a software-related field.  In what other fields does this happen?  A couple of weeks ago I saw some online discussion about this sort of thing (here and here), with many people expressing a strong dislike of puzzles, both personally and as part of the interview process.  The issues seem to be (1) whether you need to like solving puzzles to be a good programmer, and (2) whether such puzzles are a useful means of evaluating job candidates.

I like solving puzzles.  Mathematical puzzles, logic puzzles, computer science puzzles, etc.  I like solving them just for fun, and independent of whether they are useful or directly applicable to my work.

But I also think such puzzles are in fact more than just recreation, they are recreational exercise, and exercise certainly seems useful to me.  Running on a treadmill seems pretty stupid if all you care about is getting somewhere right now.  But it makes more sense if you view it as exercise, as preparation for the times when you do need to get somewhere.

For those who don’t like solving puzzles, that seems too bad.  I suppose that might be because their particular job does not involve writing code that requires much mathematics or interesting algorithms or data structures, that are at the heart of most puzzles.  (One of the above posts mentions Facebook as an employer that emphasizes puzzle-solving; I admit I don’t see a lot of “meat” in the problems one might encounter on a typical day at Facebook.)

The more interesting question to me is the second one, how useful such “puzzle-type” questions are in a job interview.  I tend to think many (most?) of them are not terribly useful in this context, for two reasons.  First, many common interview puzzles are just that, common, being so well-known that the ability to provide a solution indicates nothing more than “I’ve heard that one before.”

Also, for the unfortunate job candidate who hasn’t heard that one before, coming up with a solution in the 30-60 minutes of time during an interview may be difficult or impossible.  This problem is made worse by the fact that some common interview puzzles are of the “brain teaser” type that require flash of insight more than structured reasoning, where the latter is probably much more important to the job in question.

(Last week’s post involved two puzzles that I think are interesting in that they both straddle the line between these two types.  If you were confronted with either of these problems in an interview, it would initially seem that you were missing some information necessary to solve it.  But if an answer is expected in a very short time, then a “test-taker’s” approach might be to assume that a unique solution exists, and so it must not depend on that missing information… and so you can simply pick a convenient value for that missing information.  This would yield an answer quickly, without actually proving that the answer was in fact unique.)

Coming back to the Mastermind episode, although I was surprised by the approach at the time, looking back, I actually think it was a reasonably effective interview component.  Mastermind is a puzzle… but it’s a puzzle that doesn’t have just one solution that you can learn or look up ahead of time.  Also, having to describe the thought process involved in each guess, and the information obtained from the scoring of each guess, requires clear verbal communication of logical reasoning, which I think should be a necessary part of any job, software-related or not.

The Job Interview Question, Part 1

Similar to last month, this week I just want to present a couple of problems to consider.  Once again, neither of these is new, nor particularly difficult.  But I think they are interesting, and as before, these problems have a point, being related both to each other as well as to a more detailed discussion next week.

Problem 1.  On his death-bed, your grandfather tells you of a time when he and another man were captured by pirates.  One night, the two men escaped overboard from the pirates’ ship, taking with them a priceless golden statue that the pirates had stolen.  They eventually reached a small deserted island; however, the other man was mortally wounded during the escape attempt, and died shortly after reaching the island.  Your grandfather buried the other man under a simple marked gravestone.

He also buried the golden statue– elsewhere on the island– and it has remained there to this day.  Your grandfather gives you the following directions to find the statue: in addition to the gravestone, there are two other landmarks on the island, a maple tree and a palm tree.  You are to begin at the gravestone, walk directly to the maple tree, turn left 90 degrees, walk that same distance again, and mark the spot with a stake.  Then return to the gravestone, walk from there directly to the palm tree, turn right 90 degrees, walk that same distance again, and mark the spot with a stake.  The statue is buried at the midpoint between the two stakes.

After your grandfather’s funeral, you travel to the island, and find the maple tree and palm tree… but the gravestone is nowhere to be found.  How can you find the buried golden statue?

Problem 2.  Suppose that you drill a cylindrical hole six inches long through the center of a sphere.  That is, after drilling the hole, the distance between the two circular rims of the hole is six inches.  What is the volume that remains?  (Sorry, I couldn’t figure out how to work pirates into this one.)

Problem 3.  What do the two problems above have in common?