Pseudo Random

When you work with probabilities it is all too easy to lose sight of the fact that the phenomena you are describing aren’t really random – they are deterministic but beyond your ability to model accurately. Computers are often used to generate random numbers, and at first this seems to be a contradiction. How can a program generate random numbers when its dynamics are completely determined – more determined than the toss of a coin, say. We usually reserve the term pseudo random for numbers generated in this way but they are no more pseudo random than the majority of other numbers that we regard as truly random.

Notice that as pseudo random numbers are generated by a program much smaller than the generated sequence they are most certainly not algorithmically random in the sense of Kolmogorov. It is also true that an algorithmically random sequence might not be so useful as a sequence of random numbers because they might have irregularities that allow the prediction of the next value. For example an algorithmically random sequence might have more sixes say than any other digit. It would still be algorithmically random because this doesn’t imply that you can write a shorter program to generate it. What is important about pseudo random numbers is that they are not predictable in a statistical sense, rather than there being no smaller program that generates the sequence. Statistical prediction is based on detecting patterns that occur more often than they should for a random sequence. In the example given above, the occurrence of the digit six more often than any other digit would mean that guessing that the next digit was six would be correct more often than chance.

When we use the term pseudo random we mean that in principle all digits occur with equal frequencies, all pairs of digits occur with equal frequencies, all triples of digits occur with equal frequencies and so on. A pseudo random sequence that satisfies this set of conditions allows no possibility of predicting what might come next as every combination is equally likely. In practice, pseudo random numbers don’t meet this strict condition and we tend to adopt a less stringent requirement depending on what the numbers are going to be used for. The key idea is that the sequence should not give a supposed adversary a good chance of guessing what comes next. For example, pseudo random numbers used in a game can be of relatively low quality as the player has little chance to analyzing the sequence and so finding a weakness. Pseudo random numbers needed for cryptography have to be of a much higher quality as you can imagine that a nation state might put all of the computer power it has into finding a pattern.

Pseudo random numbers are number sequences that satisfy a condition of non-predictability given specified resources. In this sense what is pseudo random is a relative term.

True Random

If you have followed this reasoning you should be happy to accept the fact that there is no random, only pseudo random. What would a truly random event look like? It would have to differ from deterministic randomness by not being deterministic at all. In other words, there would have to be no theory that could predict the outcome, even in principle.

A fairly recent discovery, chaos, is often proposed as an example of something that can stand in for randomness. The idea is that systems exist that are so sensitive to their initial conditions that predicting their behavior rapidly becomes impractical. If the throw of a coin were a chaotic system then the behavior of the coin would be very different for starting states that differed by very little. If you knew the initial state of the coin and this allowed you to predict that it would come down heads then, for a chaotic system, a tiny change in that initial state would make it come down tails. Given that you cannot in practice know the initial state perfectly then the chaotic dynamics gives you no choice but to resort to probabilities.

A chaotic system however is still not in principle unpredictable. In this case adding more-and-more information still makes the predictions more accurate. This is not true randomness even though it is very interesting at a practical and theoretical level.

The question of whether or not there are truly random processes, i.e. ones that are even in principle not predictable, is considered open for some people, and answered by quantum mechanics for others. What is so special about quantum mechanics? The answer is that it has probability built into it. The equations of quantum mechanics don’t predict the exact state of a system, only the probability that it will be in any one of a number of states. If a coin was governed by quantum mechanics then all that the equations could say is that there is a 50% chance of it being heads and 50% chance of it being tails. Even given all of the information about the quantum coin and its initial state, the dynamics of the system is inherently probabilistic.

If quantum mechanics is correct, to paraphrase Einstein, “God does play dice with the universe”.

If you don’t find this disturbing, and Einstein certainly did, consider that when the quantum coin lands heads or tails you cannot ask about the deterministic sequence of events that led to the outcome. If there was such a sequence, it could have been used to predict the outcome and probability wouldn’t enter into it. To say that a coin lands heads without anything on the way to the outcome actually determining this is very strange. For a real coin we think that the initial throw, the air currents and how far it travels before landing determine its final configuration, but this cannot be so for a quantum coin. A quantum event does not have an explanation only a probability.

Some find this so disturbing that they simply postulate that, like our supposedly random physical coin, we are simply missing some information in the quantum case as well. However, to date no complete theory has been shown to give the same predictions as standard quantum mechanics and so far these predictions have been correct.

So, if you want true randomness you need to use a quantum system?

No, in most cases this isn’t necessary pseudo random is more than good enough. It is interesting to note that even a supposedly quantum-based random number generator is difficult to create as it is all too easy for the system to be biased by non-quantum effects. For example, a random number generator based on radiation can be biased by non-quantum noise in the detector.

This idea that there is no causal sequence leading up to the outcome is very similar to the idea of algorithmic randomness. There is no program smaller than the sequence that generates it and, in a sense, this means that there is no deterministic explanation for it. The program is the deterministic sequence, an explanation if you like for the infinite sequence it generates.

To see this, consider how could we create an algorithmic random number generator?

We would need to write a finite program that generated the sequence but, as the sequence is algorithmically random, there is no such program. You could write an infinite program, but this would be equivalent to simply quoting the digits in the sequence. But how can you quote an infinite sequence of digits? How can you determine the next digit? There seems to be no possibility of a causal way of selecting the next digit because if there was you could use it to construct a shorter program. In this sense algorithmically random sequences are not deterministic. Perhaps this is the key to the difference between pseudo random and physically random numbers. This leads us on to the subject of the next chapter, “the axiom of choice”.