## Shuffling notes

I've been trying out some boardgames that require a fair bit of card shuffling; in particular, RoboRally requires shuffling the entire (large) deck after every turn. It's led me to wondering about randomness and especially about good shuffling methods that result in a reasonable degree of randomness. Searching led me to some interesting web pages; this entry is mostly just a bookmark to let me find them again easily.

I've known for a long time about Bayer and Diaconis's mathematical proof that it takes seven riffle shuffles to adequately randomize a standard 52-card deck. That link is to a copy of a 1990 New York Times article on the topic, which also discusses the fact that some expert card players rely (or at least used to rely) on the usual approach of shuffling only a couple of times; such players may be surprised when they encounter a really randomized deck.

The Harvey Mudd math department has a couple of interesting brief web pages on related topics: Seven Shuffles, which notes in passing that the other common approach to shuffling, the “overhand” shuffle, requires 2500 shuffles to randomize a deck; and Rising Sequences in Card Shuffling, which demonstrates that there's at least one sequence of cards in a deck (relative to the starting sequence) which is literally impossible to get to in only five shuffles.

An article at the AMS website, How Many Times Do I Have to Shuffle This Deck?, goes into a fair bit of mathematical detail to demonstrate the Diaconis seven-shuffle result. I couldn't follow most of it, but the parts I could seemed interesting. (Diaconis's bio, btw, from a paper that this article links to, starts out “Persi Diaconis left High School at an early age to earn a living as a magician and gambler, only later to become interested in mathematics and earn a Ph.D. at Harvard.”)

Anyway, I eventually found pretty much what I was looking for: a Stack Exchange question about how to shuffle a discard deck in a boardgame. The chosen and highest-ranked answers suggest a couple of forms of pre-shuffling: either putting discards into multiple stacks as you go, or having someone constantly shuffling the discard pile in the background as it grows. Not sure that really helps with RoboRally, but it might be useful in some other games.

(Not all of the upvoted answers on that page are of equal quality, btw; for example, one of them says that the shuffling method is irrelevant, and that cutting works as well as any other method, both of which are wrong.)

The Wikipedia article on Shuffling has lots more info on various subtopics, of course.

(See also: Facebook thread for this post.)