[Math Lair] Randomness

Math Lair Home > Topics > Randomness

Generating a sequence of random numbers might, at first glance, appear to be easy. All we need to do, we might think, is to rattle off digits from 0 to 9 (or a string of 0's and 1's, or H's and T's, or X's and O's, or whatever) in any ridiculous sequence we please, and the result will be a random sequence, right? I'll try this right now and see what I get.

1100110010001010101011100010101010110010101010100001011011010011000101010101010101010001011100110101

If you think about this method, you may discover problems. Everybody has psychological hangups that make this method imperfect. Try it for yourself: Write down a bunch of digits from 0 to 9. If you have a look at them, you'll likely find that you seem to favour some digits or sequences of digits, while you don't use other digits or sequences as much. We would expect that, if a sequence of digits were truly random, the digit 4 (for example) would occur about one-tenth of the time, and the sequence of 93 (for example) about one-hundredth of the time. This is one of the necessary characteristics of randomness.

Looking at the sequence I typed out above, I count 48 1's and 52 0's. Almost even, so that's not too bad. But if we look at groups of two bits, there are 16 00's, 36 01's, 36 10's, and 11 11's. In a "truly" random sequence, you would like each of these four possibilities to be approximately equally represented. I guess that I have a tendency to alternate digits more often than average. On the other hand, if you were to flip a coin 100 times, you would notice longer streaks and a more even distribution of each pair.

However, flipping a coin isn't perfectly random either. What we need is a sequence with an approximately equal number of each symbol, an approximately equal number of each possible pair of two symbols, an approximately equal number of each possible group of three symbols, and so on. If we get that, then we could call the resulting sequence random. We would be able to get no information about the next symbol based on the previous symbols. Can we do this?

When I was young, I once thought about all the possible line-ups involving me and my two brothers. I noticed that there always was some sort of pattern in these line-ups; either the line-up was in order from oldest (that was me!) to youngest, or youngest to oldest, or it would be if you looked at the line as a circle. I think that I concluded that there was no "random" arrangement of me and my brothers. If we have a longer sequence, would we be able to eliminate all patterns?

No. Unfortunately, it has been proved that there is no such thing as a sequence that satisfies all of the requirements specified two paragraphs ago. We have to settle for the next best thing. To figure out what this is, we might want to look at some of the characteristics of random sequences.

One of these characteristics is that of unpredictability; you shouldn't be able to guess the next digit in a sequence of random digits. This would mean that, for example, listing the digits in the decimal expansion of an irrational number such as the square root of 2, or some other square root, or e, or π wouldn't work. After all, if we know the first n digits of any of these numbers, we have algorithms for generating the n+1st digit. Therefore, we need a more elaborate technique. But what? When we say that a sequence is unpredictable, we mean that we can't predict the next digit by using any algorithm. If we can't predict the next digit by using any algorithm, then no algorithm could exist for generating the next digit, including even the algorithm that the most jumbled-up human brain would use! Therefore, if there is a way of generating the next digit in a sequence of "random" digits, then the sequence can't be random because the next digit is predetermined. Hmmmm... .

What if the motion of all atomic particles could be predicted? If we could do that, then we could predict the output of any "random" number generator, which would no longer be random at all! On the other hand, it may be the case that events exist that are inherently unpredictable (likely quantum mechanical events). In that case, we might be able to turn those events into a random number generator. If quantum events occur in our brain, then our brain might well turn out to be the best random number generator!

As previously mentioned, the nature of randomness can be confusing. See Clustering Illusion for another example of this.