Introduction to Randomness and Random Numbers
by Dr Mads Haahr
RANDOM.ORG is a true random number service that generates randomness via atmospheric noise. This page explains why it's hard (and interesting) to get a computer to generate proper random numbers.
Random numbers are useful for a variety of purposes, such as generating data encryption keys, simulating and modeling complex phenomena and for selecting random samples from larger data sets. They have also been used aesthetically, for example in literature and music, and are of course ever popular for games and gambling. When discussing single numbers, a random number is one that is drawn from a set of possible values, each of which is equally probable, i.e., a uniform distribution. When discussing a sequence of random numbers, each number drawn must be statistically independent of the others.
With the advent of computers, programmers recognized the need for a means of introducing randomness into a computer program. However, surprising as it may seem, it is difficult to get a computer to do something by chance. A computer follows its instructions blindly and is therefore completely predictable. (A computer that doesn't follow its instructions in this manner is broken.) There are two main approaches to generating random numbers using a computer: Pseudo-Random Number Generators (PRNGs) and True Random Number Generators (TRNGs). The approaches have quite different characteristics and each has its pros and cons.
Pseudo-Random Number Generators (PRNGs)
As the word ‘pseudo’ suggests, pseudo-random numbers are not random in the way you might expect, at least not if you're used to dice rolls or lottery tickets. Essentially, PRNGs are algorithms that use mathematical formulae or simply precalculated tables to produce sequences of numbers that appear random. A good example of a PRNG is the linear congruential method. A good deal of research has gone into pseudo-random number theory, and modern algorithms for generating pseudo-random numbers are so good that the numbers look exactly like they were really random.
The basic difference between PRNGs and TRNGs is easy to understand if you compare computer-generated random numbers to rolls of a die. Because PRNGs generate random numbers by using mathematical formulae or precalculated lists, using one corresponds to someone rolling a die many times and writing down the results. Whenever you ask for a die roll, you get the next on the list. Effectively, the numbers appear random, but they are really predetermined. TRNGs work by getting a computer to actually roll the die — or, more commonly, use some other physical phenomenon that is easier to connect to a computer than a die is.
PRNGs are efficient, meaning they can produce many numbers in a short time, and deterministic, meaning that a given sequence of numbers can be reproduced at a later date if the starting point in the sequence is known. Efficiency is a nice characteristic if your application needs many numbers, and determinism is handy if you need to replay the same sequence of numbers again at a later stage. PRNGs are typically also periodic, which means that the sequence will eventually repeat itself. While periodicity is hardly ever a desirable characteristic, modern PRNGs have a period that is so long that it can be ignored for most practical purposes.
These characteristics make PRNGs suitable for applications where many numbers are required and where it is useful that the same sequence can be replayed easily. Popular examples of such applications are simulation and modeling applications. PRNGs are not suitable for applications where it is important that the numbers are really unpredictable, such as data encryption and gambling.
It should be noted that even though good PRNG algorithms exist, they aren't always used, and it's easy to get nasty surprises. Take the example of the popular web programming language PHP. If you use PHP for GNU/Linux, chances are you will be perfectly happy with your random numbers. However, if you use PHP for Microsoft Windows, you will probably find that your random numbers aren't quite up to scratch as shown in this visual analysis from 2008. Another example dates back to 2002 when one researcher reported that the PRNG on MacOS was not good enough for scientific simulation of virus infections. The bottom line is that even if a PRNG will serve your application's needs, you still need to be careful about which one you use.
True Random Number Generators (TRNGs)
In comparison with PRNGs, TRNGs extract randomness from physical phenomena and introduce it into a computer. You can imagine this as a die connected to a computer, but typically people use a physical phenomenon that is easier to connect to a computer than a die is. The physical phenomenon can be very simple, like the little variations in somebody's mouse movements or in the amount of time between keystrokes. In practice, however, you have to be careful about which source you choose. For example, it can be tricky to use keystrokes in this fashion, because keystrokes are often buffered by the computer's operating system, meaning that several keystrokes are collected before they are sent to the program waiting for them. To a program waiting for the keystrokes, it will seem as though the keys were pressed almost simultaneously, and there may not be a lot of randomness there after all.
However, there are many other ways to get true randomness into your computer. A really good physical phenomenon to use is a radioactive source. The points in time at which a radioactive source decays are completely unpredictable, and they can quite easily be detected and fed into a computer, avoiding any buffering mechanisms in the operating system. The HotBits service at Fourmilab in Switzerland is an excellent example of a random number generator that uses this technique. Another suitable physical phenomenon is atmospheric noise, which is quite easy to pick up with a normal radio. This is the approach used by RANDOM.ORG. You could also use background noise from an office or laboratory, but you'll have to watch out for patterns. The fan from your computer might contribute to the background noise, and since the fan is a rotating device, chances are the noise it produces won't be as random as atmospheric noise.
Thunderstorm over Denver, USA
Thunderstorms generate atmospheric noise
As long as you are careful, the possibilities are endless. Undoubtedly the visually coolest approach was the lavarand generator, which was built by Silicon Graphics and used snapshots of lava lamps to generate true random numbers. Unfortunately, lavarand is no longer operational, but one of its inventors is carrying on the work (without the lava lamps) at the LavaRnd web site. Yet another approach is the Java EntropyPool, which gathers random bits from a variety of sources including HotBits and RANDOM.ORG, but also from web page hits received by the EntropyPool's own web server.
Regardless of which physical phenomenon is used, the process of generating true random numbers involves identifying little, unpredictable changes in the data. For example, HotBits uses little variations in the delay between occurrences of radioactive decay, and RANDOM.ORG uses little variations in the amplitude of atmospheric noise.
The characteristics of TRNGs are quite different from PRNGs. First, TRNGs are generally rather inefficient compared to PRNGs, taking considerably longer time to produce numbers. They are also nondeterministic, meaning that a given sequence of numbers cannot be reproduced, although the same sequence may of course occur several times by chance. TRNGs have no period.
Comparison of PRNGs and TRNGs
The table below sums up the characteristics of the two types of random number generators.
Characteristic Pseudo-Random Number Generators True Random Number Generators
Efficiency Excellent Poor
Determinism Determinstic Nondeterministic
Periodicity Periodic Aperiodic
These characteristics make TRNGs suitable for roughly the set of applications that PRNGs are unsuitable for, such as data encryption, games and gambling. Conversely, the poor efficiency and nondeterministic nature of TRNGs make them less suitable for simulation and modeling applications, which often require more data than it's feasible to generate with a TRNG. The following table contains a summary of which applications are best served by which type of generator:
Application Most Suitable Generator
Lotteries and Draws TRNG
Games and Gambling TRNG
Random Sampling (e.g., drug screening) TRNG
Simulation and Modelling PRNG
Security (e.g., generation of data encryption keys) TRNG
The Arts Varies
Quantum Events or Chaotic Systems?
One characteristic that builders of TRNGs sometimes discuss is whether the physical phenomenon used is a quantum phenomenon or a phenomenon with chaotic behaviour. There is some disagreement about whether quantum phenomena are better or not, and oddly enough it all comes down to our beliefs about how the universe works. The key question is whether the universe is deterministic or not, i.e., whether everything that happens is essentially predetermined since the Big Bang. Determinism is a difficult subject that has been the subject of quite a lot of philosophical inquiry, and the problem is far from as clear cut as you might think. I will try and explain it here, but would also like to point out that Wikipedia has a concise account of the debate.
Quantum mechanics is a branch of theoretical physics that mathematically describes the universe at the atomic and subatomic levels. Random number generators based on quantum physics use the fact that subatomic particles appear to behave randomly in certain circumstances. There appears to be nothing we know of that causes these events, and they are therefore believed by many to be nondeterministic.
In comparison, chaotic systems are those in which tiny changes in the initial conditions can result in dramatic changes of the overall behaviour of the system. Weather systems are a good example of this, and you may have heard of the butterfly effect, a thought experiment in which a butterfly beating its wings in Brazil is able to affect the winds subtly but critically, just enough to cause a tornado in Texas.
Proponents of random number generators of the quantum variety argue that quantum physics is inherently nondeterministic, whereas systems governed by physics are essentially deterministic. I am personally undecided as to where I stand on the determinism-nondeterminism scale, but for the sake of argument, I will put on my determinist hat and use RANDOM.ORG as an example. You could argue that the atmospheric noise used as a source for the RANDOM.ORG numbers can be viewed as a chaotic but deterministic system. Hence, if you knew enough about the processes that cause atmospheric noise (e.g., thunderstorms) you could potentially predict the numbers generated by RANDOM.ORG.
However, to do this, you would probably need knowledge of the position and velocity of every single molecule in the planet's weather systems. This is of course infeasible, and the inaccuracy of weather forecasts is a good example of how difficult it is to give even a rough estimate of the behaviour of weather systems. For this reason, it is impractical to predict random numbers from RANDOM.ORG, even for a determinist. A similar case (on a different scale) could be made for random number generators based on lava lamps.
Now, you may think that since there's dispute about the suitability of chaotic phenomena for generating randomness, then why not just stick with quantum physics? That would seem to be the safe bet. However, quantum generators aren't safe from critique either. Hard determinists will dispute that subatomic particle behaviour is really random and instead claim that the way they behave is exactly as predetermined as everything else in the universe has been since the Big Bang. The reason we think these specific particles behave randomly is simply that no human measurement has been able to account for their behaviour. In this view, subatomic events do indeed have a prior cause, but we just don't understand it (yet), and the events therefore seem random to us. To a hard determinist, quantum physics is exactly as suited for random number generation as is atmospheric noise or lava lamps.
This is only one possible argument, and there are many others. When it comes down to it, I think the most meaningful definition of randomness is that which cannot be predicted by humans. Whether randomness originates from unpredictable weather systems, lava lamps or subatomic particle events is largely academic. While quantum random number generators can certainly generate true random numbers, it seems to me that they for all intents and purposes are equivalent to approaches based on complex dynamical systems.
