Real-world problems with naive shuffling

Question

I'm writing a number of articles meant to teach beginning programming concepts through the use of poker-related topics. Currently, I'm working on the subject of shuffling.

As Jeff Atwood points out on CodingHorror.com, one simple shuffling method (iterating through an array and swapping each card with a random card elsewhere in the array) creates an uneven distribution of permutations. In an actual application, I would just use the Knuth Fisher-Yates shuffle for more uniform randomness. But, I don't want to bog down an explanation of programming concepts with the much less coder-friendly algorithm.

This leads to the question: Just how much of an advantage would a black-hat have if they knew you were using a naive shuffle of a 52-card deck? It seems like it would be infinitesimally small.

Answer 1

Subjective.

It seems like it would be infinitesimally small.

Agree.

Answer 2

It turns out the advantage is quite significant. Check out this article

Part of the problem is the flawed algorithm, but another part is the assumption that you can get "random" numbers from a computer.

Answer 3

It's not like you're writing a poker program that will be used for an actual online gambling site. An ability for someone to cheat at the program isn't a big deal when you're teaching people how to program.

Leave a note saying that this is a poor model of the real world (with a reference to it as a possible security flaw), and just keep going with the teaching.

Answer 4

A simple & fair algorithm for shuffling would be to assign a random floating-point number (e.g., between 0 and 1) to each card in the deck, then sort the deck by the assigned numbers.

This is actually a perfect example for students to realize that just because something is intuitive, the naive shuffle in our case, doesn't mean it's correct.

Answer 5

Just as an aside, there was a blog post over on ITtoolbox about shuffling that may be of interest when it comes to simulating a shuffle.

As to your question, consider that there are 52! deck configurations that one could start with that may play a role in where things land as in Jeff's example of the 3 card deck, note that the 1 in the over-represented occurs in each slot once. Also note that he says you'd have to have a few thousand examples before it becomes apparent where the advantage is, but with a deck you aren't likely to start again with the exact same initial deck, are you? You'd take the dealt cards and put them on the bottom and shuffle them which isn't likely to repeat I'd think.

Answer 6

The knuth shuffle is an insignificant change compared to the naive shuffle: Just swap with any card in the remaining (unshuffled) section of the deck instead of anywhere in the entire deck. If you think of it as repeatedly choosing the next card in order from the remaining unchosen cards, it's pretty intuitive, too.

Personally, I think teaching students a poor algorithm when the proper one is no more complicated (and easier to visualise!) is a bad approach.