# Random Number Information

(Click to generate some Random Numbers)

### The Nature of Randomness

Certain natural events are believed (by most physicists) to be completely random. An often-quoted example of such an event is the spontaneous decay of a radioactive atom: there is no way that one can predict the time when such an event will occur, and so the time between two consecutive clicks on a Geiger counter is to all intents and purposes truly random.

The randomness of other, more everyday, events may be harder to determine. Take the example of flipping a coin. It is generally accepted that the result - heads or tails - is random, but what would happen if the coin was poorly flipped so that it is possible to watch it spinning in the air? If we knew the initial orientation of the coin then we could count the number of times it turned before being caught, and so we could predict the outcome of the flip. We would no longer call it a random event. If we had fast enough reflexes then perhaps we could watch any coin-flip and predict the outcome accurately - certainly it's possible to imagine a machine which could do something like this.

So, is flipping a coin a random event? It really depends on the definition of the word 'random'. If we take it to mean that the outcome is theoretically unpredictable then no, the coin flip is not random. But in the real world it is practically impossible to predict the outcome of a good flip, so in that respect we can call it a random event.

### Lotteries and Butterflies

Similarly the tumbling balls inside a Lotto machine all obey the laws of physics so in theory it should be possible to predict the lottery numbers given the initial starting positions of all the balls and a precise description of their physical properties. But in practice we can never know these values with sufficient accuracy, and even a tiny discrepancy in the initial conditions will lead to a huge variation in the outcome - making it impossible to predict the lottery numbers that will be drawn by the machine. In the field of weather forecasting this potential for a massive change in outcome for a miniscule difference in the starting conditions is often known as the 'butterfly effect', from the observation that a butterfly flapping its wings in South America might ultimately alter the course of a storm in Florida!

### Chaos out of Order

Often it is very useful to have a computer generate a series of random numbers - they can be used to test the behavior of computer simulations, or to create unpredictable events (such as the motion of an enemy in a game). However a computer is an inherently predictable machine, so how can it be used to generate random numbers? The solution is to produce numbers which are predictable to the computer, but which behave as though they were random - rather like the coin-flipping experiment.

Typically one of the required characteristics of a random number generator is that all numbers within a given range are equally likely. This behavior could be achieved if we listed all the numbers in the range, then shuffled the list and returned the numbers in the new sequence. Each number would be guaranteed to appear exactly once, so all would be equally likely, and if the shuffling was performed well enough then it would be practically impossible to predict one number from the next.

It turns out that there are certain relatively simple mathematical operations which will effectively step through all the numbers in certain ranges in a 'shuffled' order, visiting each number exactly once. Such sequences of numbers are sometimes called 'pseudo-random', since the sequence is in fact predictable but has many characteristics in common with a truly random sequence.

### An Example - the LCG

The family of formulae most commonly used to generate pseudo-random numbers are known as 'Linear Congruential Generators' (LCGs). These have the property that each number in the sequence is derived from the previous one by multiplying it by a suitable number a, adding an offset b, and taking the result modulo n. (Modulo n means the remainder after dividing by n. For values of n which are a power of 2, this is a very easy operation for computers.) Let's take an example, using a=4, b=5, and n=9. Then if we start with the number 0, our second number is:
(0 x 4) + 5 modulo 9 = 5.
The third number is:
(5 x 4) + 5 modulo 9 = 7 (because 20+5=25, and 25/9 is 2 remainder 7)
The fourth number is:
(7 x 4) + 5 modulo 9 = 6

The complete sequence is:
0, 5, 7, 6, 2, 4, 3, 8, 1, 0, 5, 7, 6...
We can see that this sequence works through all the numbers from 0 to 8, in its particular shuffled order, before repeating.

Not all choices of a, b and n produce sequences which include all the values from 0 to n - there is an art to choosing suitable values. Try manually calculating the sequence using a=5, b=3, and n=9 - you will find there are four distinct 'sub-sequences' generated, depending on the starting value.

Using a bigger value of n will make it possible to produce sequences that run for longer before repeating - although the corresponding a and b values need to be chosen carefully in order to produce maximal length sequences.

A feature of LCGs is that the lower (rightmost) digits tend to be 'less random' than the higher digits. To avoid this problem, it is good practice to use only the higher digits of the generated values, since there will then be less correlation between successive values.

### In Use

Typical values used in a 'real' LCG are:
a=1664525, b=1013904223, n=232=4294967296
which cycles through all possible 32-bit numbers, and has the advantage that the modulo operation happens automatically on most computers. The first few values in this sequence are:
1013904223, 3442648290, 4022689497, 1349532260,
3173630579, 2017633590, 132832029, 2625544664

It can be seen that these numbers alternate - odd, even, odd, even, odd... - which is an example of the non-randomness of the lower digits. Using higher digits from these numbers would remove this pattern.

There are many refinements to the LCG - for example a variant which stores the last few values and returns them in a shuffled order, or another variant which combines two LCGs with different repeat periods to produce a third sequence with a much longer period than either of the original sequences. There are also other pseudo-random generators based on shift registers, which are useful for producing a stream of single binary random 'bits'. However the LCG is by far the most popular method for generating pseudo-random sequences and is found in virtually all computer languages.