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/