There is an experiment done in some statistics and psychology classes that goes
like this: divide the class into two parts. As homework, the first half
is asked to flip a coin 200 times and record the results. The second
half is asked to fake the results of the first group by making up a "random"
sequence of 200 coin flips. When the results are handed in during the next
class, the instructor is able to identify the real ones from the fakes
with around 95% accuracy, to the general amazement of the class.
If you want to try this experiment on yourself, hop into an editor
right now and type out your best guess of what 200 random tosses of a coin
would look like (using 'H' and 'T', or your two favorite keys of choice).
If you actually attempt this, it will make this writeup more interesting,
I promise. I'll wait.
/me waits
OK. The way to distinguish real random sequences from human-generated
ones is to look for a place on the list where there are at least six heads
or tails entries in a row. Almost everyone who tries to fake the tosses
fails to include a run of such length, yet it is almost a statistical
certainty that it will occur in a sufficiently large number of tosses.
Using 200 flips, roughly 98% of the entries should have such a sequence
of at least six consecutive heads or tails.
This is actually nontrivial to compute (see bottom), but a quick-and-dirty
calculation that ignores any conditional probability is as follows: at
any given point, the probability of getting six of the same side in a row
is (1/2)^6 = 1/64. Thus at any given point the probability of not having
such a sequence occur in the next six tosses is (1 - 1/64), and thus the
likelihood of this not happening over the entire run is (1 - 1/64)^195 =
approximately 5%. (We use 195 not 200, since it is impossible to get six
in a row in the last 5 flips). So the rough probability of the sequence happening is 95%. The actual result is even higher.
Hence almost every time we can expect to get a run of six or more,
but the near-certainty of this from a probability standpoint does not mesh
with our psychological picture of what random coin tosses are supposed
to "look like". In fact, what most people tend to write down is
a sort of pseudo-alternation of heads and tails, which is anything but
random. If you look at randomness from a compression or signal analysis
standpoint, it is equivalent to white noise, meaning that no patterns
can be usefully extracted (and no compression can usefully be done). The
more a sequence resembles H,T,H,T,H,T.... throughout, the more it becomes
nonrandom because it contains the pattern of "H,T alternating".
Part of the conceptual difficulty people have with including long sequences
of heads- or tails-only is the misconception that the probabilities of
future flips somehow should depend on the previous results. They don't,
because each coin flip is an independent trial. While you have 1 chance
in 64 of getting six heads in a row as an all-or-nothing proposition, the
probability of getting heads on each individual filp, and each subsequent
one, is still 1/2.
It's interesting to examine an actual sequence, because it doesn't
"look" random enough to most people even after you have internalized
the mathematics of it. Here's a 200-flip sequence generated by my computer's
random() function (represented as 1 and 0):
11001000001111111010100100100110101011101101101110100111111
00100000000010100011011000000100101100011111000101011000111
10001011101000100011111111111010000010010101010111001000010
100101100001101011101101
Note the string of eleven (count 'em) 1's near the middle.
To calculate the actual probability of six or more heads or tails in
200 coin flips is not a straightforward exercise, even if you know
a bit of probability theory, because the combinatorics gets messy. The
problem is that in 200 coin flips, any calculation has to allow for multiple
sequences of more than six.
The easiest way to come up with a reasonable estimate is by simulation:
a small program in C (or the language of your choice) can demonstrate that
in a large number of trials like 10,000 or 100,000, the probability is quite close to 98.4%. If
you are one of those folks that needs an exact answer, well, OK. *deep breath*
To simplify things, take the case for n=3, ie: a 3-heads or tails sequence.
Let's look at the first few tosses.
For the first toss, you get H or T. In the second generation, you get
HH, TT, HT or TH. Since we're aiming for sequences of three, getting HT
or TH is cancelling our run, so we might as well represent it as H or T.
So in generation 2 we get: HH, TT, H and T. In generation 3 we get HHH,
TTT, HH, TT, and 2 each of H and T. This is obviously symmetric in H and T, so we consider
only heads. For H we have the following production rules:
- H produces HH, H
- HH produces HHH, H
- HHH produces 2 * HHH
The first two you can see from the above argument (visualize the possibilities
as a binary tree throughout this). The last one is a bit subtle: once
we have made it to 3 heads, we are done, so we count each of the 2 branches
of the tree as being in the class HHH. We can make a table that counts
the number of each class for every generation:
generation: 0 1 2 3 4 5 6 7 n
-----------------------------------------------
an = HHH: 0 0 1 3 8 19 43 94 bn-1 + 2(an-1)
bn = HH: 0 1 1 2 3 5 8 13 cn-1
cn = H: 1 1 2 3 5 8 13 21 2n-1 - an-1
2 things to note here: (1) the sum of any column is the total number of outcomes after n generations = 2n. (2) the recurrence relation that results
for the class we are interested in (HHH) is:
an = 2n-3 - an-3 + 2(an-1)
It's not hard to show that this is the same for a six-heads sequence,
the only difference being that (n-3) in the power and subscript terms becomes (n-6):
an = 2n-6 - an-6 + 2(an-1)
The probability we want is a199 / 2199 (since we indexed from n=0). You can use a symbolic math package like
Mathematica or Maple to evaluate this. It is, as is demonstrated from simulation, about
98%. You can also compute this with generating functions,
but it involves some manipulation of series and is even more messy.