Straight Dope Message Board > Main Math help : Define a better shuffled deck of cards
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
07-07-2012, 09:54 PM
 am77494 Guest Join Date: Mar 2012
Math help : Define a better shuffled deck of cards

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 ?
#2
07-07-2012, 10:40 PM
 ultrafilter Guest Join Date: May 2001
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.
#3
07-07-2012, 10:51 PM
 Wendell Wagner Charter Member Join Date: Jul 1999 Location: Greenbelt, Maryland Posts: 11,199
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.
#4
07-07-2012, 10:58 PM
 Smashed Ice Cream Guest Join Date: Sep 2001
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
#5
07-08-2012, 12:04 AM
 Lance Turbo Guest Join Date: Aug 1999
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.
#6
07-08-2012, 12:07 AM
 Sage Rat Member Join Date: Mar 2004 Location: Howdy Posts: 13,864
Quote:
 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.

Last edited by Sage Rat; 07-08-2012 at 12:08 AM.
#7
07-08-2012, 03:55 AM
 t-bonham@scc.net Guest Join Date: Mar 2003
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.
#8
07-08-2012, 08:20 AM
 ftg Guest Join Date: Feb 2001
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."
#9
07-08-2012, 05:23 PM
 am77494 Guest Join Date: Mar 2012
So given Deck A and Deck B - there is no simple test to tell which one is better shuffled ?
#10
07-08-2012, 05:28 PM
 ultrafilter Guest Join Date: May 2001
Quote:
 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.
#11
07-08-2012, 06:56 PM
 septimus Guest Join Date: Dec 2009
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. )

Last edited by septimus; 07-08-2012 at 06:57 PM.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 12:32 AM.

 Contact Us - Straight Dope Homepage - Archive - Top

Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

Send questions for Cecil Adams to: cecil@chicagoreader.com