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.