Math help : Define a better shuffled deck of cards

[am77494]

My friend and I have a bet that our card shuffling methods are superior than each other. So we have set out to test it in a scientific way.

So for starters - statistically what is a measure of the degree of good shuffling for the following cases :

Case A. We start with a deck of cards arranged in order - A,K,....?

Case B. The initial deck arrangement is unknown ?

[ultrafilter]

You can't measure the "shuffledness" of a deck of cards--after all, any ordering could be the outcome of a random process--but you can measure how well a given shuffling algorithm randomizes. Unfortunately, the math is pretty complicated. If you're comfortable with group theory and Markov chains, you can search for Persi Diaconis's work on card shuffling.

[Wendell Wagner]

It doesn't matter what ordering you start with. It's known that it takes at least seven imperfect shuffles to randomize a deck of cards. An imperfect shuffle is one in which you split the deck in half and shuffle the two halves together, not so that you're always putting one card from one half between two cards from the other half (that's a perfect shuffle), but so that there will be several cards from one half, then several cards from the other deck, etc. The point of an imperfect shuffle is that you don't know beforehand how many from each half will be shuffled between two from the other half.

[Smashed Ice Cream]

Ultrafilter beat me to pointing you towards Diaconis. But here's a paper of his which explains the ugly, ugly maths behind riffle shuffling.

MATHEMATICAL DEVELOPMENTS FROM THE ANALYSIS
OF RIFFLE SHUFFLING

[Lance Turbo]

One aspect of my job is testing Pseudorandom number generators for use in gaming (gambling) devices.

If we were asked to evaluate a shuffling algorithm we would first do a mathematical analysis looking for obvious flaws. Something like the algorithm being unable to produce all possible permutations or a bias to certain permutations.

If the algorithm passed that stage, we'd generate a bunch of shuffles from an ordered set. (If the order was not known there would be no way to tell if the shuffle did anything at all.)

We'd then perform at battery of statistical tests on that data set to see if we could tell the difference between that data set and "perfectly" random data.

If the algorithm passed all those tests all we could say is that the list of tests we performed can't distinguish this algorithm from a perfectly random shuffle.

Comparing two algorithms to each other would be similar. If both passed there'd be no way to say which was better from our perspective (although one could make an argument that the less computationally intensive algorithm was the winner).

If we were doing such an analysis we'd also probably be wondering the whole time why you just didn't use Fisher-Yates.

[Sage Rat]

Originally Posted by ultrafilter

You can't measure the "shuffledness" of a deck of cards--after all, any ordering could be the outcome of a random process--but you can measure how well a given shuffling algorithm randomizes. Unfortunately, the math is pretty complicated. If you're comfortable with group theory and Markov chains, you can search for Persi Diaconis's work on card shuffling.

You can demonstrate that the end position is not correlated to the start position, given a large enough sample size and some statistical analysis. Of course, if all of your methods of shuffling guarantee that there is no correlation, then there is no particular ranking system that you can give them as regards randomness.* Perfectly random and super-magically perfectly random are indistinguishable.

* You can rate them based on processing time or simplicity, on the other hand.

[t-bonham@scc.net]

Or you could just describe the 2 shuffling methods, and probably some of the experts here could give you a definitive answer as to which is better, and the reasons. Be sure to specify how many times you do the shuffling process.

[ftg]

As a Computer Scientist, I usually use the "random" in the context of Kolmogorov based Algorithmic Information Theory.

The practical problems with that are: 1) You have to specify a computational model as the base. 2) Any Turing-complete base is automatically uncomputable. (So it's a great definition that's useless in practice. You can define bases for computable classes, but you either end up too weak of a base or it's too hard to compute.)

What I do in practice is use a top-notch compression algorithm. Random stuff doesn't compress. So, run several million tests on output. Almost all of it should not compress the same as a true random shuffle. (The encoding of the deck itself will allow some compression.) There should be a teeny percentage of slightly compressed stuff.

Always, always, remember John von Neumann's quote: "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin."

[am77494]

So given Deck A and Deck B - there is no simple test to tell which one is better shuffled ?

[ultrafilter]

Originally Posted by am77494

So given Deck A and Deck B - there is no simple test to tell which one is better shuffled ?

There's no test at all.

[septimus]

I think the answers have been correct, but may not have answered OP's intended question. He doesn't want to use Fisher-Yates; he wants to physically riffle a physical deck using two thumbs and several fingers. (Can you do that with Fisher-Yates?) He doesn't want to model shuffles mathematically; he wants to perform them physically, finger foibles and all. He doesn't want to shuffle thousands of decks and perform elaborate statistical tests; he just wants to do a handful of shuffles (perhaps 3 or even fewer each by him and his friend) and calculate a simple but useful "randomness score."

My advice to OP is

• Sort the cards completely before each shuffle (say Spades: Ace, Deuce, ... through King; then Hearts the same way; then Clubs; then Diamonds)
• Shuffle (perhaps allowing a fixed number of seconds for the shuffling since almost any method will shuffle better if you repeat it longer)
• Compute a simple "randomness score."

Of course there are no usable perfect "randomness scores," but I think there are some usable for your purpose. One way (mentioned in the papers cited to gauge effectiveness of riffle shuffles, though it might be a reasonable test for some other shuffling patterns as well) is to count rising sequences. Counting the rising sequences may be a bit error-prone and time-consuming, but may not take much longer than the Sort cards completely step and, if done in a certain way, leaves the deck in that sorted order, ready for the next trial, upon completion!

Here's how to count "rising sequences":
Starting at the same end of the deck that had card #1 (Ace of Spades) before the shuffle, search until you find that #1 card (and then pull it out and set it aside, forming the sorted deck for the next shuffle) and continue forward from the location of #1 until you reach #2, set it aside and continue to #3 and so on. When you get to the end of the deck, start over at the beginning and increment a count.

The number of times you go back to the beginning of the deck in this procedure is your "count of rising sequences." The count will be 1 if you did no shuffling at all, 2 after a single riffle, and will increase up to a point as the shuffling improves. (The count will reach 52 if you manage to shuffle until the cards are exactly reversed from their starting position!)

This is just one simple randomness test and may unfairly favor one shuffling method over another. Depending on how important your bet is, you might want some alternate tests.

Crudely, the larger the number of rising sequences the better but since the largest number (52) represents perfect unshuffling, it might be better to let the winner be whoever approaches the average rising sequence count among all orderings. (What is that "average count"? Let's leave that as an exercise for now. )