|Inside Random Numbers|
|Written by Mike James|
|Tuesday, 18 November 2014|
Page 1 of 3
We often refer to things that are unpredictable as being "random" but this is not the same as truly random behavior - which is something we have to work hard to achieve. Put another way - how can a logical deterministic device like a computer produce a random number?
What Is Random?
Most things that are unpredictable in a common sense way we call “random” but it is important to notice that this isn’t the same thing as truly random behavior.
You could say that true randomness isn’t really a part of everyday life and experience.
For example, if you throw a coin up in the air you might say that which side it comes down is “random”. However, if you think a little more carefully what you are saying is that the physics of the process are simply not within your powers to predict.
You could imagine that if you measured the forces applied to the coin and knew its mass and shape then application of Newton’s laws of motion would make the outcome predictable.
OK there would be problems such as air currents and so on in making the calculation but you can see that by putting enough effort into the problem, in principle if not in practice, you can reduce something that is random to something that is predictable.
Or putting the whole situation the other way round you could invent a machine to toss the coin so accurately that it always came down heads. That is by setting the initial conditions accurately the apparent random behaviour vanishes.
This is how it nearly always is in the real world and unless you are a quantum physicist you really should think in terms of randomness as meaning “unpredictable”.
Although it isn’t really important from a computing point of view most people do like to know if there is such a thing true randomness.
One answer to this question is hinted at in an earlier comment. Only quantum physics seems to provide us with examples of true randomness because part of its dogma is that quantum processes are in principle unpredictable. That is, unlike the coin tossing, the randomness in quantum behaviour isn't something you can remove.
If you accept the truth of quantum mechanics then the best you can do is to give probabilities for what is going to happen. When the objects involved get larger than these probabilities move closer to one and zero and we have the approximation to the world we live in where things can be certain and predictable.
A second and slightly more modern answer is that some processes are chaotic. What this means is that while they are governed by exact equations the sensitivity of the output to the inputs is such that tiny changes in the initial conditions produce extremely different outcomes. This makes a system predictable in theory but not predictable in any reasonable definition of "practical".
This last conception is closer to the computer's implementation of random but some argue that chaos is true randomness while others reserve the term for the quantum mechanical sort that is in principle not predictable.
It is worth stating again that this level of discussion is more suited to philosophy. What matters about practical randomness is that there are no patterns that make the future outcomes predictable.
More cartoon fun at xkcd a webcomic of romance,sarcasm, math, and language
Can a single number be random?
Computers and Randomness
So moving back to computers and randomness what sort of things can we make a computer do that makes it look unpredictable?
Notice that even here we have to be weaker than simply saying “to make a computer behave randomly”. The reason is that even though “random” mostly means the same as “unpredictable” there is a big difference between the unpredictability of tossing a coin and what you can make a computer do.
The difference is, of course, the program.
When you toss a coin you are giving in to vague mechanics to produce something that is unpredictable. When you program a computer everything is precisely and entirely predicable. The fact that a program makes a computer do what it does means that, unlike the coin, you always have a mechanism for predicting what it is going to do i.e. the program it is running always determines exactly what is going to happened and reading it through reveals all.
In general a program given the same set of inputs or initial conditions will always produce exactly the same outputs - what could be more predictable?
For this reason the sort of unpredictability that a computer can produce is usually called “pseudo randomness” – or false randomness.
In practice the difference between true randomness, randomness, and “pseudo randomness” doesn't matter but you still have to be clear in your mind about which one you are discussing, particularly when criticizing a situation that is claimed to be “random”.
Sources of Entropy
One way of creating a random program is to make use of an input to the computer that is random.
This is usually referred to as making use of a source of entropy i.e. disorder.
For example, you could read an input pin connected to a device that generates a random signal and turn this into a random number. Physical random number generators of this sort are used but they are much more difficult to create than you might think. It is very easy for regularity to find its way into what you might assume is a random signal. For example, the electronics might accidently pick up a regular signal from the power circuit and so introduce a non-random component.
Once entropy source that is guaranteed by the laws of physics to be random is the decay of a radioactive substance. You can use the output from a Geiger counter to generate random numbers of the highest quality but this isn't a practical way to do the job in most cases.
One way to get real random numbers - an early random number generator used radioactive decay to generate a random signal.
One method that has become popular in the smart phone era is to make use of the camera's light sensor. The noise that this generates is essentially a quantum phenomenon and hence it should be a good source of random numbers - however it is embedded in a circuit which has lots of periodic signals and there is no guarantee that it wont pick one or more of these up so introducing a regularity.
What we really need is a program that will generate unpredictable numbers without the use of an external source of entropy.
|Last Updated ( Tuesday, 18 November 2014 )|