Random number generation
From Wikipedia, the free encyclopedia
The many applications of randomness have led to many different methods for generating random data. These methods may vary as to how unpredictable or statistically random they are, and how quickly they can generate random numbers.
Before the advent of computational random number generators, generating large amount of sufficiently random numbers (important in statistics) required a lot of work. Results would sometimes be collected and distributed as random number tables.
Contents |
[edit] Physical methods
The earliest methods for generating random numbers - dice, coin flipping, roulette wheels are still used today, mainly in games and gambling as they tend to be too slow for applications in statistics and cryptography.
Some physical phenomena, such as thermal noise in zener diodes appear to be truly random and can be used as the basis for hardware random number generators. However, many mechanical phenomena feature asymmetries and biases that make their outcomes not truly random. The many successful attempts to exploit such phenomena by gamblers, especially in roulette and blackjack are testimony to these effects.[1][citation needed]
There are several imaginative sources of random numbers online. A common technique is hashing a frame of a video stream from an unpredictable source. Most notable perhaps was Lavarand which used images of a number of lava lamps. Lithium Technologies uses a camera pointed at the sky on a windy and cloudy day[2]. Random.org has a more obvious approach of listening to atmospheric noise. Details about how they turn their input into random numbers can be found on their respective sites.
Completely randomized design falls within the category of true random number generation. The generation of true random numbers outside the computer environment is based on the theory of entropy[3]. Sources of entropy include nuclear decay and atmospheric conditions. HotBits uses radioactive decay, while Random.org uses radio noise to generate randomness.
[edit] Computational methods
Pseudo-random number generators (PRNGs) are algorithms that can automatically create long runs (for example, millions of numbers long) with good random properties but eventually the sequence repeats exactly (or the memory usage grows without bound). One of the most common PRNG is the linear congruential generator which uses the recurrence
- Xn + 1 = aXn + b(mod m)
to generate numbers. The maximum number of numbers the formula can produce is the modulus, m. See the article in question for more details.
A simple pen-and-paper method for generating random numbers is the so-called middle square method suggested by John Von Neumann. While simple to implement, its output is not guaranteed to be random.
A pen-and-paper method proven to generate truly random numbers exploits the fact that the decimal expansion of the reciprocal 1/q will produce a stream of random numbers of length q - 1 if q is such that q = 2S + 1 where S is a Sophie Germain prime, and both S and 2S + 1 are of the form 3, 9 or 11 mod 20. Thus “suitable” prime numbers q are 7, 23, 47, 59, 167, 179, etc (corresponding to S = 3, 11, 23, 29, 83, 89, etc.). The result is a stream of length q-1 digits (including leading zeros). So, for example, using q = 23 generates the random digits 0,4,3,4,7,8,2,6.....3,9,1,3
[edit] Practical applications
Random number generators are very useful in developing Monte Carlo simulations as debugging is facilitated by the ability to run the same sequence of random numbers again by starting from the same seed. They are also used in cryptography so long as the seed is secret. Sender and receiver can generate the same set of numbers automatically to use as keys.
The generation of pseudo-random numbers is an important and common task in computer programming. While cryptography and certain numerical algorithms require a very high degree of apparent randomness, many other operations only need a modest amount of unpredictability. Some simple examples might be presenting a user with a "Random Quote of the Day", or determining which way a villain might move in a computer game. Weaker forms of randomness are also closely associated with hash algorithms and in creating amortized searching and sorting algorithms.
