Whatever else it is, randomness is peculiar. More peculiar still is our perception of what is or is not random. Consider, for example, the case of flipping a coin five times. Suppose you do that and get the sequence `T,H,H,T,H`

(T is tails, H is heads). That seems perfectly reasonable, right? Random? Imagine instead that you got `H,T,H,T,H`

. You’d probably think the alternating heads and tails is pretty weird, but you still got almost the same number of tails as heads which is pretty much the definition of what people think of as “random.”

If you got `H,H,H,H,H`

, you’d probably think that the coin was rigged. It could be, but it could also be a perfectly fair coin.

Given five flips of a fair coin, there are 2^{5} (32) possible sequences that can occur. You’re equally likely to get all heads as you are to get something like the first sequence I showed, or all tails, or any other sequence. The all heads result just *seems* “not random” because it’s so distinctive. But there is a one in 32 chance of that or any other result.

Pick up your coin again and flip it five times, writing down each result. Was the sequence `T,T,H,T,H`

? For approximately one out of 32 people who do this exercise, it will be.

Think of it this way. Write down a number from 1 to 32, go to random.org and have it generate a number in that range. Would you be very surprised if it picked your number on the first try? More or less surprised than if you flipped a coin five times and got all tails?

Instead of getting random.org to generate a number for you, you could ask somebody to guess what it is. But that wouldn’t be a fair test because people don’t pick numbers randomly. Asked to select a number in some range, people are more likely to pick an odd number than an even number, more likely to pick primes, and the chosen number is usually in the bottom third or top third of the range. See for example, Is 17 the “most random” number? and Probability, algorithmic complexity, and subjective randomness. Or just do a Google search for “psychology of randomness.”

Because *you* probably picked a number using the same criteria, other people have a better chance of guessing your number than does a computer that gives each number equal weight. Of course, now that you know what most people do, you’ll probably pick a number that others are less likely to guess.

What most people think of as “randomness” is really complexity. The more complex a sequence looks, the more “random” we perceive it. `THHTH`

appears more complex than `HHHHH`

, and therefore more “random” in our eyes. It’s what researchers call subjective randomness.

Not only are people terrible at perceiving randomness, they’re also terrible at generating randomness. Asked to flip a coin 100 times and write down the results, many college students will “cheat” and forego flipping the coin. They’ll just write down what they think is a random sequence. It’s usually easy to catch them because the idea of run of four or five tails just seems “not random.” But getting five heads or five tails in a row is very common given 100 flips of a fair coin.

Let me demonstrate with a smaller set.

There are 32 possible sequences of five flips, which I’ve reproduced below. I’ve substituted ‘0’ for ‘T’ and ‘1’ for ‘H’ because 0 and 1 are more visually distinct than T and H, and because I’m accustomed to using 0 and 1 for binary results.

`00000 01000 10000 11000`

00001 01001 10001 11001

00010 01010 10010 11010

00011 01011 10011 11011

00100 01100 10100 11100

00101 01101 10101 11101

00110 01110 10110 11110

00111 01111 10111 11111

The sequence `00`

occurs in 19 of those 32 results. So the likelihood of getting two tails in a row in a sequence of five flips is 19/32, or about 59%. The odds of *not* getting two tails in a row, then, is 13/32, or 41%. Getting two tails in a row wouldn’t be strange. Neither would getting two heads. What *would* be strange is not getting either two heads or two tails in a row. There are only two sequences that don’t have a matching pair (`01010`

and `10101`

), so in 30 out of 32 cases (94% of the time), there will be either two heads in a row or two tails in a row.

It’s not uncommon, in fact, to see a run of three tails. In the results above, there are eight sequences with `000`

, so 25% of the time you’ll see a run of three tails. In just five flips of the coin!

You can actually compute the probability of *not* getting a run of *k* tails in *n* tosses using something called a Fibonacci *k*-step number. I used that formula to verify the results I derived above.

There are 2^{100} (a really big number) possible sequences of 100 flips. I can’t list them all, but I can use the formula to determine the likelihood of not getting a run of five tails in a sequence of 100 flips. I just had to compute the 102^{nd} item in the 5-step sequence. Here’s the method I used.

private BigInteger KStep(int k, int n) { // Calculate the nth value in the Fibonacci k-step number number sequence BigInteger[] all = new BigInteger[n]; all[0] = 1; all[1] = 1; for (int i = 2; i < n; ++i) { BigInteger rslt = all[i - 1]; for (int j = i - 2; j >= 0 && j >= i - k; --j ) { rslt = rslt + all[j]; } all[i] = rslt; } return all[n - 1]; }

That’s not the most efficient implementation possible, but it did the job. The result I got for `KStep(5, 102)`

is 240,714,680,556,315,819,945,145,376,976, or about 2.41 x 10^{29}. I have to divide that by 2^{100} (1.27 x 10^{30}), the result of which is 0.1899. So given 100 flips, 19% of the time I won’t see a run of five tails.

Because I don’t have a trillion lifetimes to generate and examine all the possible 100-flip sequences, I wrote a little function that will generate a million different *n*-flip sequences, each time checking to see if it got a run of *k* tails. It keeps track of how many times there *isn’t* a run, and reports the results. Called with `Flipper(5, 100)`

, it reports a value pretty close to 19% every time.

```
private const int NTries = 1000000;
private void Flipper(int k, int n)
{
var rnd = new Random();
string testString = new string('T', k);
int runCount = 0;
// how often do we NOT get k tails in n flips?
for (int i = 0; i < NTries; ++i)
{
var sb = new StringBuilder(n);
for (int flip = 0; flip < n; ++flip)
{
var x = rnd.Next(2) == 0;
sb.Append(x ? 'H' : 'T');
}
if (!sb.ToString().Contains(testString))
{
++runCount;
}
}
Console.WriteLine("{0:N0} out of {1:N0}: {2:P2}",
runCount, NTries, (double)runCount/NTries);
}
```

If you play with the program a bit, you’ll find that runs of six tails happen more than half the time, runs of seven happen about a third of the time, and you’re *twice* as likely to get a run of 10 than not get a run of four. File that one away in the “Math that just don’t feel right” drawer.