Determing randomness of a shuffled deck
January 7th, 2010 at 8:11:04 AM
permalink
Is there a method to determine if a deck of cards, after being sufficiently shuffled, is arranged in such a way that one could prove mathematically the order of the cards is in fact random? Thank you for your time and consideration of my question.
January 7th, 2010 at 8:49:39 AM
permalink
Quote: detroitjoeIs there a method to determine if a deck of cards, after being sufficiently shuffled, is arranged in such a way that one could prove mathematically the order of the cards is in fact random? Thank you for your time and consideration of my question.
Any ordering of a single deck, no matter its order, is equally likely to occur as any other, and therefore no randomness test can be done merely on the order of the cards by themselves.
The question is if the shuffle itself is "random." For this, you would need the original deck order and the order after the shuffle. However, "randomness" can never be proven. What can be proven given sufficient evidence is that, with a high degree of confidence, the shuffle is not random.
--Dorothy
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
January 7th, 2010 at 9:00:09 AM
permalink
Quote: DorothyGale
Any ordering of a single deck, no matter its order, is equally likely to occur as any other, and therefore no randomness test can be done merely on the order of the cards by themselves.
--Dorothy
This is an intersting statement that I would agree with on the surface. However, I wonder how many BJ players have ever seen a deck where the shuffle brought the deck back to the original order of a new pack (ie: all cards in sequence by suit). Based on how the cards are distributed when a pack is is first opened, and the limited number of shuffles through it when it is first played, I would say that there is probably no possibiity that it could revert back to it's original order, but after so many play throughs is it possible that it could eventually get there? Could this be ONE of the reasons that decks are replaced every few hours (other than an anti-tampering method)?
So I says to him, I said "Get your own monkey!"
January 7th, 2010 at 9:04:26 AM
permalink
I do understand the probability of order, that each card has the same probability of occurring next. I'm focused more on patterns. I am using the assumption that a new deck ordered 2-A by suit has a defined, distinct pattern. This is the starting point. Now shuffle that deck. What mathematical test could be used to show, as you put it, to a high degree of confidence that the shuffle was not random? Thanks for your help.
January 7th, 2010 at 9:06:11 AM
permalink
Quote: MrPapagiorgioQuote: DorothyGale
Any ordering of a single deck, no matter its order, is equally likely to occur as any other, and therefore no randomness test can be done merely on the order of the cards by themselves.
--Dorothy
This is an intersting statement that I would agree with on the surface. However, I wonder how many BJ players have ever seen a deck where the shuffle brought the deck back to the original order of a new pack (ie: all cards in sequence by suit).
Returning the cards to their original order should occur by chance on average 1 every 52! shuffles.
My original statement is true, so I am not sure what you are disagreeing with. The question of randomness is based solely on the difference in the order from the cards preceeding the shuffle to the order after the shuffle, and not the particular order of the cards in either state.
--Dorothy
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
January 7th, 2010 at 9:13:25 AM
permalink
I'm not one to normally disagree with someone helping me, but empirical data would suggest that the chance of cards returning to suited and numbered status after a rifle shuffle being 1 in 52 is just not correct, unless you performed 52 perfect rifle shuffles in a row, which is unlikely in a real world scenario. Of course, being an amateur at best, I cannot prove this mathematically. You may have the same probability of drawing a card from a deck, but rifle shuffling the deck is something completely different.
That said, you mentioned you could prove to a high degree of confidence the shuffle was not random. How would you go about doing this?
That said, you mentioned you could prove to a high degree of confidence the shuffle was not random. How would you go about doing this?
January 7th, 2010 at 9:14:26 AM
permalink
Quote: DorothyGaleQuote: MrPapagiorgioQuote: DorothyGale
Any ordering of a single deck, no matter its order, is equally likely to occur as any other, and therefore no randomness test can be done merely on the order of the cards by themselves.
--Dorothy
This is an intersting statement that I would agree with on the surface. However, I wonder how many BJ players have ever seen a deck where the shuffle brought the deck back to the original order of a new pack (ie: all cards in sequence by suit).
Returning the cards to their original order should occur by chance on average 1 every 52! shuffles.
My original statement is true, so I am not sure what you are disagreeing with. The question of randomness is based solely on the difference in the order from the cards preceeding the shuffle to the order after the shuffle, and not the particular order of the cards in either state.
--Dorothy
I am simply saying that I have never seen a fresh shuffled deck, or any deck, dealt back in the original package order - not anywhere close - and I've seen a lot of shuffles in single deck, double deck, and six deck. I think it is a rare event for anyone to have seen this - especially from a fresh deck that has only been spread around on the table, then shuffled 3 or 4 times. In fact, I do not even know if it is possible for a deck to revert back to its original order after being spread around on the table and then shuffled three or four times before play.
So I says to him, I said "Get your own monkey!"
January 7th, 2010 at 9:16:40 AM
permalink
Quote: detroitjoeI'm not one to normally disagree with someone helping me, but empirical data would suggest that the chance of cards returning to suited and numbered status after a rifle shuffle being 1 in 52 is just not correct. Of course, being an amateur at best, I cannot prove this mathematically. You may have the same probability of drawing a card from a deck, but rifle shuffling the deck is something completely different.
That said, you mentioned you could prove to a high degree of confidence the shuffle was not random. How would you go about doing this?
That caught me too, wouldn't it be something like:
1/52 * 1/51 * 1/50 *1/49 etc?
So I says to him, I said "Get your own monkey!"
January 7th, 2010 at 9:19:05 AM
permalink
It would take 52 perfect rifle shuffles in a row to return the original deck back to original state (according to wiki articleThis is not a real world scenario.
January 7th, 2010 at 9:20:30 AM
permalink
All the shuffling stuff aside, you mentioned you could prove to a high degree of confidence the shuffle was not random. How would you go about doing this?
January 7th, 2010 at 9:21:48 AM
permalink
That why Dorothy said "52!" The exclamation point is not there to indicate enthusiasm! (That one is!) There's really no such thing as "random" It like the "Wow! 25 Reds in a row in Roulette...what are the odds?!!" The same as any other combination that will reveal itself every 25 rolls.
January 7th, 2010 at 9:23:43 AM
permalink
The resident Oz-like entity actually said it would happen 1 in every 52! shuffles, not 1 in every 52 shuffles. 52! is 52*51*50 etc, which is... a very large number: 8.06581752 × 10^67 in fact. So you will almost certainly never, ever see this.
Note that the total number of ways to arrange the deck is 52! not 1/52 * 1/51 * 1/50 etc. Since there are 52! ways to arrange the deck, a shuffle that perfectly randomizes the deck has a 1 in 52! chance to be the original shuffle.
Think about it this way: if you were shuffling by randomly drawing cards and putting them back into a pile, you would initially have 52 cards to pick from. Then you would have 51, then 50, etc.
Note that the total number of ways to arrange the deck is 52! not 1/52 * 1/51 * 1/50 etc. Since there are 52! ways to arrange the deck, a shuffle that perfectly randomizes the deck has a 1 in 52! chance to be the original shuffle.
Think about it this way: if you were shuffling by randomly drawing cards and putting them back into a pile, you would initially have 52 cards to pick from. Then you would have 51, then 50, etc.
January 7th, 2010 at 9:28:06 AM
permalink
For Ms. Dorothy, you mentioned you could prove to a high degree of confidence a shuffle was not random. Based on a starting point of a brand new deck, then taking the final order, how would you prove this.
January 7th, 2010 at 9:28:30 AM
permalink
What I meant above is, once you shuffle a deck a few times, it will always be "random". You're attempting to determine non-randomness by what? 4 Aces in a row? 8 Clubs? Any "pattern" that you see has the same chance at appearing as any other run of cards.
January 7th, 2010 at 9:32:37 AM
permalink
Quote: MrPapagiorgioQuote: detroitjoeI'm not one to normally disagree with someone helping me, but empirical data would suggest that the chance of cards returning to suited and numbered status after a rifle shuffle being 1 in 52 is just not correct.
?
That caught me too, wouldn't it be something like:
1/52 * 1/51 * 1/50 *1/49 etc?
You misread my post. I said 1 in 52! not 1 in 52. The number 52! is defined to be 52*51*50*...*3*2*1. Apologies, I thought the notion of factorials was known.
--Dorothy
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
January 7th, 2010 at 9:34:07 AM
permalink
Quote: DorothyGaleQuote: MrPapagiorgioQuote: detroitjoeI'm not one to normally disagree with someone helping me, but empirical data would suggest that the chance of cards returning to suited and numbered status after a rifle shuffle being 1 in 52 is just not correct.
?
That caught me too, wouldn't it be something like:
1/52 * 1/51 * 1/50 *1/49 etc?
You misread my post. I said 1 in 52! not 1 in 52. The number 52! is defined to be 52*51*50*...*3*2*1. Apologies, I thought the notion of factorials was known.
--Dorothy
It's been a long time since math class, but I do recall this now that you have pointed it out. Thanks for the refresher.
So I says to him, I said "Get your own monkey!"
January 7th, 2010 at 9:42:14 AM
permalink
My fault altogether, like I said I am an amateur when it comes to this stuff and I missed that completely. Besides that, you did mention you could prove to a high degree of confidence that a shuffle was not random, how would this be done?
January 7th, 2010 at 9:44:35 AM
permalink
It IS known. But you gotta remember that this is a group of people that know what phrases like "House Edge" mean, and still look for ways to beat the system.Quote: DorothyGaleI thought the notion of factorials was known.
If you had simply said "1 in 52! (factorial)" we all would have understood that you weren't merely tring to make an exagerated point.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
January 7th, 2010 at 9:46:01 AM
permalink
Quote: detroitjoeFor Ms. Dorothy, you mentioned you could prove to a high degree of confidence a shuffle was not random. Based on a starting point of a brand new deck, then taking the final order, how would you prove this.
In hypothesis testing, there's something called the "Null Hypothesis." That's the thing you want to be true but can never really prove is true. In this case "the shuffle is random." To do hypothesis testing, we assume the Null Hypothesis is true, and based on this assumption we compute test statistics to gather evidence against this hypothesis. It's kind of like "proof by contradiction," which is used, for example to prove that the square root of 2 is irrational. However, it's very important to understand that the final answer is not the probability that the Null Hypothesis is true, rather, it provides evidence that the Null Hypothesis is false. We can never prove the shuffle is random, but we can certainly show evidence against it being random.
One particularly useful statistic for this type of testing is the chi-squared statistic. In the case of shuffling, one can compute the frequency of the distribution of pairs (x,y) of cards over the span of many shuffles. Or one can compute the distribution of distances between initially adjacent cards. Both of these can lead to a useful P-value using chi-squared testing.
There are infinitely more tests, it's really up to the creativity of the tester. Look up the "Diehard Tests" on wikipedia. To be truly random, according to Knuth in "Seminumerical Algorithms," the shuffle would have to pass "all conceivable tests."
Sorry, this is all very technical.
--Dorothy
"Who would have thought a good little girl like you could destroy my beautiful wickedness!"
January 7th, 2010 at 9:47:14 AM
permalink
Quote: cclub79What I meant above is, once you shuffle a deck a few times, it will always be "random". You're attempting to determine non-randomness by what? 4 Aces in a row? 8 Clubs? Any "pattern" that you see has the same chance at appearing as any other run of cards.
This is exactly my question, is there a method that can be used to prove a shuffle is not random. Using suits, card numbers, colors, any or all three?
Assume you ordered the cards by color, which would seem easy since there are only two. I've placed the cards in what I consider to be a defined order, all red cards and all black cards together. Now you shuffle that deck. Could you prove the randomness of the shuffle, the placement of cards by color in the shuffled deck, mathematically?
January 7th, 2010 at 9:51:30 AM
permalink
Quote: DorothyGaleQuote: detroitjoeFor Ms. Dorothy, you mentioned you could prove to a high degree of confidence a shuffle was not random. Based on a starting point of a brand new deck, then taking the final order, how would you prove this.
In hypothesis testing, there's something called the "Null Hypothesis." That's the thing you want to be true but can never really prove is true. In this case "the shuffle is random." To do hypothesis testing, we assume the Null Hypothesis is true, and based on this assumption we compute test statistics to gather evidence against this hypothesis. It's kind of like "proof by contradiction," which is used, for example to prove that the square root of 2 is irrational. However, it's very important to understand that the final answer is not the probability that the Null Hypothesis is true, rather, it provides evidence that the Null Hypothesis is false.
One particularly useful statistic for this type of testing is the chi-squared statistic. In the case of shuffling, one can compute the frequency of the distribution of pairs (x,y) of cards over the span of many shuffles. Or one can compute the distribution of distances between initially adjacent cards. Both of these can lead to a useful P-value using chi-squared testing.
There are infinitely more tests, it's really up to the creativity of the tester. To be truly random, according to Knuth in "Seminumerical Algorithm," the shuffle would have to pass "all conceivable tests."
Sorry, this is all very technical.
--Dorothy
Understood, this has been very helpful and I am learning a great deal here today. Sorry for my ignorance but I am just starting out. I will look further into the chi-squared test. I appreciate all your help, and everyone else. Anyone with further information please continue to post.
January 7th, 2010 at 9:56:57 AM
permalink
Bear in mind that in a casino (and usually in home games as well), new or sorted decks are first washed before going thru a standard shuffle. My opinion is that the wash alone is usually sufficient to randomize it.Quote: MrPapagiorgioBased on how the cards are distributed when a pack is is first opened, and the limited number of shuffles through it when it is first played....
On an unrelated note, have you ever seen one of these cheap plastic card shufflers?
They actually do a decent job of randomizing the deck.
Although I don't use it much, I own one. One day, for sh*ts and giggles, I sorted a deck, and put the red cards in one stack, and the black in the other and pressed the button.
When watching it run, you think it simply pulls one card from the bottom of each stack alternatively.
After a single pass, I flipped and spread the deck. I was shocked at what I saw.
Not only were there cases where it pulled more than one card at one time from a side, it did NOT always pull the bottom card! And this reversal of sequence did not always happen when two cards from the same side got pulled at once.
At that point, I came to the conclusion that, given 4 or 5 passes in this machine, that the resulting shuffle would be sufficiently randomized.
If you ever get a chance, try it. You'll be equally flabbergasted.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
January 7th, 2010 at 10:00:16 AM
permalink
Quote: DJTeddyBearIt IS known. But you gotta remember that this is a group of people that know what phrases like "House Edge" mean, and still look for ways to beat the system.Quote: DorothyGaleI thought the notion of factorials was known.
If you had simply said "1 in 52! (factorial)" we all would have understood that you weren't merely tring to make an exagerated point.
I think we may have just been compared to this:
So I says to him, I said "Get your own monkey!"
January 7th, 2010 at 10:00:18 AM
permalink
The only problem is, going by one shuffle, you are saying that you will know it's random by lack of clumps of the same color? The problem is, if it's truly random, you COULD see large clumps of the same color in a series. By saying clumps of the same color makes it not random or shuffled, you are FAVORING a mix that is not more likely than any other. Again, go back to my roulette example. You would say that a wheel is not random because 10 reds came in a row. But then you would be eliminating that possibility. Granted, I know that roulette is completely independant every time, and with each card drawn the odds of the following card are then affected, but ANY 52 card series should be as likely and random as any other.
A good way to look at it would be to take the colors, numbers, suits, etc out of it. Pretend the deck has 52 random people you know on it, but no words, etc. You get the deck alphabetically by name. I'm sure that after one shuffle, you would be hard pressed to tell if the cards were still "clumping".
We see patterns with numbers and think that we didn't do a good job of shuffling.
A good way to look at it would be to take the colors, numbers, suits, etc out of it. Pretend the deck has 52 random people you know on it, but no words, etc. You get the deck alphabetically by name. I'm sure that after one shuffle, you would be hard pressed to tell if the cards were still "clumping".
We see patterns with numbers and think that we didn't do a good job of shuffling.
January 7th, 2010 at 10:03:51 AM
permalink
Not at all.Quote: MrPapagiorgio
You have to be fairly bright to understand what a "house edge" is.
It's the dim bulbs that prefer the double-zero roulette tables because there's one more way to win than a single-zero table.
I invented a few casino games. Info:
http://www.DaveMillerGaming.com/ —————————————————————————————————————
Superstitions are silly, childish, irrational rituals, born out of fear of the unknown. But how much does it cost to knock on wood? 😁
January 7th, 2010 at 10:05:11 AM
permalink
Quote: cclub79The only problem is, going by one shuffle, you are saying that you will know it's random by lack of clumps of the same color? The problem is, if it's truly random, you COULD see large clumps of the same color in a series. By saying clumps of the same color makes it not random or shuffled, you are FAVORING a mix that is not more likely than any other. Again, go back to my roulette example. You would say that a wheel is not random because 10 reds came in a row. But then you would be eliminating that possibility. Granted, I know that roulette is completely independant every time, and with each card drawn the odds of the following card are then affected, but ANY 52 card series should be as likely and random as any other.
I agree that you could still see large "clumps" after the shuffle. But given the starting point I mentioned, 26 red then 26 black in a row, then shuffled, is there a way to measure how the cards are ordered after the shuffle based on the clumps, like how many clumps, how big the clumps are, how often the clump changes from red to black, anything like that? It would not have to be only one shuffle, the number of shuffles does not matter to me. It's just the end result of the cards.
January 7th, 2010 at 10:08:51 AM
permalink
Quote: DJTeddyBearNot at all.Quote: MrPapagiorgio
You have to be fairly bright to understand what a "house edge" is.
It's the dim bulbs that prefer the double-zero roulette tables because there's one more way to win than a single-zero table.
Then I suppose we are more like this ;)
So I says to him, I said "Get your own monkey!"
January 7th, 2010 at 10:40:06 AM
permalink
Quote: detroitjoeQuote: cclub79The only problem is, going by one shuffle, you are saying that you will know it's random by lack of clumps of the same color? The problem is, if it's truly random, you COULD see large clumps of the same color in a series. By saying clumps of the same color makes it not random or shuffled, you are FAVORING a mix that is not more likely than any other. Again, go back to my roulette example. You would say that a wheel is not random because 10 reds came in a row. But then you would be eliminating that possibility. Granted, I know that roulette is completely independant every time, and with each card drawn the odds of the following card are then affected, but ANY 52 card series should be as likely and random as any other.
is there a way to measure how the cards are ordered after the shuffle based on the clumps, like how many clumps, how big the clumps are, how often the clump changes from red to black, anything like that? It would not have to be only one shuffle, the number of shuffles does not matter to me. It's just the end result of the cards.
I think I just keep going back to my idea that "Once they are shuffled, they are shuffled forever." You can't see patterns and theyn say that they are not natural. I don't think there's a way to measure "how shuffled they are", as you asked.
January 7th, 2010 at 11:34:14 AM
permalink
According to these articles, it can be proved when a deck of cards becomes randomly mixed, which means:
"By saying that the deck is completely mixed after seven shuffles, Dr.
Diaconis and Dr. Bayer mean that every arrangement of the 52 cards is equally
likely or that any card is as likely to be in one place as in another."
So 7 shuffles is the turning point to a truly "mixed" deck.
This makes sense, since if you have half the deck in one hand, and half in the other, and you rifle shuffle the cards, the probability of the top card from either half being at the bottom of the deck after one shuffle is zero, it cannot occur. So there is not an equal probability of order on every shuffle, especially not one shuffle.
I guess my answer is in these pages. Thanks to everyone for posting.
"By saying that the deck is completely mixed after seven shuffles, Dr.
Diaconis and Dr. Bayer mean that every arrangement of the 52 cards is equally
likely or that any card is as likely to be in one place as in another."
So 7 shuffles is the turning point to a truly "mixed" deck.
This makes sense, since if you have half the deck in one hand, and half in the other, and you rifle shuffle the cards, the probability of the top card from either half being at the bottom of the deck after one shuffle is zero, it cannot occur. So there is not an equal probability of order on every shuffle, especially not one shuffle.
I guess my answer is in these pages. Thanks to everyone for posting.
January 7th, 2010 at 2:13:49 PM
permalink
Quote: detroitjoeIt would take 52 perfect rifle shuffles in a row to return the original deck back to original state (according to wiki article http://en.wikipedia.org/wiki/Shuffling. This is not a real world scenario.
If you use a certain type of rifle shuffle called an out-shuffle, it only takes 8 perfect shuffles to return to the original position. (An out shuffle keeps the top card on top of the deck, and bottom card on the bottom of the deck)
Make sure you use an in-shuffle when you rifle shuffle, to get the randomness you want after 7 shuffles.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
January 8th, 2010 at 3:49:13 PM
permalink
Quote: stephenThe resident Oz-like entity actually said it would happen 1 in every 52! shuffles, not 1 in every 52 shuffles. 52! is 52*51*50 etc, which is... a very large number: 8.06581752 × 10^67 in fact. So you will almost certainly never, ever see this.
By way of comparison, the age of the universe (very roughly 14 billion years) is about 4.4 × 1017 seconds, or on the order of 19!.
