Random number generator
|
|
A random number generator is a computational or physical device designed to generate a sequence of numbers that does not have any easily discernable pattern, so that the sequence can be treated as being random. Random number generators have existed since ancient times, in the form of dice and coin flipping, the shuffling of playing cards, the use of yarrow stalks in the I Ching, and many other methods.
| Contents |
"True" random numbers vs. pseudo-random numbers
Main article: pseudo-random number generator
What consitutes a "true" random number is difficult to decide, since the concept of randomness is itself somewhat difficult to define. What is universally agreed that any "random number generator" based solely on deterministic computation cannot be regarded as a "true" random number generator, since its output is inherently predictable. John von Neumann once famously said "Anyone who uses software to produce random numbers is in a state of sin".
However, under some circumstances, carefully chosen pseudo-random number generators can be used instead of true random numbers for some applications. Rigorous numerical analysis is usually needed to justify these applications.
In other circumstances, particularly for security applications, the use of pseudo-random numbers instead of true random numbers can completely compromise the application they are being used for.
Generating random numbers from physical processes
Main article: hardware random number generator
There a general consensus that if there are such things as "true" random number, they are likely to be found by looking at physical processes which are, as far as we know, unpredictable.
A physical random number generator is based on an essentially random atomic or subatomic physical phenomenon. Examples of such phenomena include radioactive decay, thermal noise, and shot noise.
Physical random number generators relying on quantum mechanical processes may the advantage that the sequences they produce are completely unpredictable, assuming that current theories of quantum physics are correct.
Post-processing and statistical checks
Even given sources of plausible random numbers, obtaining numbers which are completely unpredictable and unbiased is a very difficult task. Since random number generators are inherently designed to be unpredictable, it is difficult to ensure that they are being predictably unpredictable. For example, many hardware random number generators generate random numbers which tend to get focused in certain areas instead of being distributed uniformly, and their behavior may change with temperature, with voltage, with the age of the device, or with outside interference. A software bug in a pseudo-random number routine, or a hardware bug in the hardware it runs on, may be similarly difficult to detect.
For these reasons, random numbers are typically subjected to statistical tests before use (to ensure that the underlying source is still working), and then post-processed to improve their statistical properties.
Also, when using random numbers, we must take into account whether they include or exclude their upper and lower bounds. Some 0 to 1 RNGs include 0 but exclude 1, while others include both, and yet others exclude both.
If you have access to many independent RNGs, XORing their results will provide a combined RNG that is at least as good as the best RNG you have access to. More details about uncorrelated near random bit streams.
Computational and hardware random number generators are commonly combined to obtain the benefits of both kinds. Computational random number generators can typically generate pseudo-random numbers than much faster than physical generators can generate true randomness.
Uses of random numbers
Random number generators have several important applications. Note that, in general, in applications where human fraud or adversaries exist, hardware-generated numbers should be used in preference to pseudo-random number generators.
Simulation
Random number generators were originally constructed to carry out computer simulation of physical phenomena, specifically the simulation of neutron transport in nuclear fission.
Pseudo-random numbers are frequently used in simulation of statistical events, a very simple example being the outcome of tossing a coin. More complicated implications are the simulation of genetics in whole populations, or the behaviour of sub-atomic particles. Such simulation methods, often called stochastic simulation methods have many applications in computer simulation of real-world effects.
Cryptography
Random number generation is also important in modern cryptography.
Experimental design
Random numbers are often used in experimental design, particularly in the creation of double-blind trials.
Parapsychology
Random numbers are often used in parapsychology as a test of precognition.
Gambling
Every modern electronic casino game contains one or more random number generators that decide the outcome of a trial in the game. Even in slot machines, where mechanical reels appear to spin randomly, the reels are actually spinning for entertainment value and eventually stop exactly where the machine's software decided they would stop when the handle was first pulled. (It has been alleged that some gaming machines' software is deliberately biased to prevent true randomness, in the interests of maximizing their owners' revenue -- this sort of allegation is why state gaming inspectors exist.)
Low-discrepancy sequences as an alternative
Some computations that make use of a random number generator can be summarized as the computation of a total or average value, such as the computation of integrals by the Monte Carlo method. For such problems, it may be possible to find a more accurate solution by the use of so-called low-discrepancy sequences, also called quasirandom numbers. Such sequences have a definite pattern that fills in gaps evenly, qualitatively speaking; a truly random sequence usually leaves larger gaps.
See also
External links
- Random.org - generate random bitmaps, flip virtual coins etc. (http://www.random.org) (random numbers generated from atmospheric noise from a radio)
- HotBits: Genuine Random Numbers (http://www.fourmilab.ch/hotbits/) (random numbers generated from radioactive decays)
- LavaRnd demonstration (http://www.lavarnd.org/demo/index.html) (random numbers generated from a webcam CCD chip)
- RandomNumbers.info (http://www.randomnumbers.info/) (random numbers generated by exploiting elementary quantum optics process)
- KenoRND() (http://www.kenotracker.com/keno/Random.asp) (random numbers generated from results of live keno at real casinos)nl:toevalsgenerator