Measuring the Randomness of a Shuffled Deck
Date: 12/19/2003 at 15:36:14 From: Stephanie Subject: Ways to measure randomness in a deck of cards Last year for our science fair I asked, "Which shuffles a deck of cards better, and automatic card shuffler, or suffling by hand?" To measure this, I decided to say that the first shuffler to reach total randomness was the best way to shuffle. I can't find a new way to measure randomness, and I really, really need to find a way. This project intrigues me, and the only thing I need to find out the answer is another way to randomize card decks. Casinos use computers with fancy programs, but I don't have that. I need a new and simple way to measure randomness. I numbered a deck of cards 1-52, then shuffled them, and tried to break up ascending groups of numbers. If they had two different cards in between them, they were broken. My hypothesis was correct: the automatic card shuffler won. This year, I would like to continue this project, but in order to do that, I need a new way to measure randomness without the use of fancy computers or something like that. I have researched it on the Internet, but have come up with nothing.
Date: 12/20/2003 at 18:19:33 From: Doctor Vogler Subject: Re: Ways to measure randomness in a deck of cards Hi Stephanie, Well, I guess that "true random" would mean that every possible ordering of the cards in the deck (there are 52! of them) has an equal chance of being the one the shuffled deck ends up in. Humans typically have a hard time being "random." They tend to fall into patterns or otherwise be predictable. I've heard of a college professor of probability who would have half of his class write down a list of zeros and ones from a bunch of coin tosses and the other half write down a list of zeros and ones that they would try to make look random, and he could sort out the papers with only a glance at each paper. In general, a human could probably shuffle the deck into any of the 52! different permutations of the cards, but he probably has his "way" of shuffling, and this may make the distribution of the probabilities rather uneven. On the other hand, computers have what programmers call "pseudorandom number generators." That means that they have some function f that takes an input of 16 or 32 or perhaps 64 bits (that is, 2^16 or 2^32 or 2^64 different possible inputs) and outputs the same number of bits, and it mixes up the numbers a lot. Let's say that we're using "k" bits. The best kind of function to use here is one which has "full period" which means that if you start with some number x, and then you change x to f(x) and repeat this 2^k times, you will not repeat until you get to the very end, at which point you will get your original x again. (Often, they will use a type of function called a "linear congruential generator" or LCG.) So the way a pseudorandom number generator works is that it starts with an input called a "seed" and then every time you ask for a number, it gives you f(seed) and then changes the seed to the number it just gave you. Or, more often, it only gives you the upper half (k/2 bits) of the number f(seed). That way, the next number is not determined by the one it just gave you. But, the important thing is that the next number *is* determined by the current seed. And so if you start with any one of 2^k different seeds and then generate thousands and billions of random numbers, there are actually only 2^k possible different sequences of random numbers that you might get, at least if you know what the function f is. That's the biggest limitation of pseudorandom number generators, and that's why they're called "pseudorandom." They're not truly random because the next number is determined by the current value of the seed. The second limitation is in the seed itself. If you start with the same seed, you'll get all the same numbers. So it is very important to get one "random" input for the seed. Generally, this means that you need some input from the outside world (outside of the computer). Most often, programmers will take the seed from the computer's clock (a record of real-world time), and this works well for most purposes, but you can really only do it once because knowing one time will generally tell you what (or about what) the next time will be, and the precision of the computer's clock limits the size of the number "k" of bits of your seed. For example, if your computer only records the date and time in seconds, then any given year will have fewer than 2^25 different seeds that might go into the random number generator. If you have a 64-bit seed, then you're still really not going to get 2^64 different sequences of random numbers. So you would need to find some other inputs from the outside world to fill the seed, such as measuring microseconds between keypresses or something like that. Now 52! is bigger than 2^225, so even if you have a 64-bit seed or a 128-bit seed, there will be many different permutations of the cards that your pseudorandom number generator will never give you. So you would definitely need to have a lot of input from the outside world to get at least 226 bits and preferably many more bits than this of "truly random" seed. I should hope that casinos with their fancy programs do this, but I'll bet the operators of those programs don't know about these mathematics, don't care, and really don't want to type for a while before every shuffle, so I wouldn't be surprised if the programmers of their fancy programs just hush up about the complications and only use a 32-bit seed with input from the clock, in which case no more than 2^32 of the 52! permutations would be possible, and the others would never happen. So I guess the thing to do is first find out how sophisticated computers that do the shuffling are (perhaps by asking at the casinos or talking to someone who writes the shuffling programs), and then to try to study how random human shuffling is, which is not at all an easy thing to do. My first thought on the human shuffling would be to have different people each shuffle a deck many times and count how many times they end up with each of the 52! permutations, and see how even this distribution is. But then each person would have to shuffle several times 10^68 times, which is not feasible by a long shot. So you'll have to find a different way to measure it. Good luck! - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 12/21/2003 at 15:34:37 From: Stephanie Summar Subject: Thank you (Ways to measure randomness in a deck of cards) Thank you, Dr. Vogler! I was having huge problems with this, and your answer has cleared things up for me a lot. Thank you so much!
Date: 12/22/2003 at 14:23:51 From: Doctor Douglas Subject: Re: Ways to measure randomness in a deck of cards Hi Stephanie, I'd like to supplement Dr. Vogler's answer by providing a couple of online references that may give you some ideas on how to measure randomness and how to apply it to your situation: Disorder in the Deck http://www.maa.org/mathland/mathtrek_10_16_00.html Java applet simulation of shuffling a deck http://www.math.washington.edu/~chartier/Shuffle/simulation.html I hope this helps. - Doctor Douglas, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.