Random number generation

From Wikipedia, the free encyclopedia

(Redirected from Random
number generator)

Jump to: navigation,
search

A random number generator (often abbreviated as RNG) is a
computational or physical device designed to generate a sequence of numbers or symbols
that lack any pattern, i.e. appear random. Computer-based systems
for random number generation are widely used, but often fall short of this goal,
though they may meet some statistical tests for randomness intended to ensure
that they do not have any easily discernible patterns. Methods for generating
random results have existed since ancient times, including dice, coin flipping, the shuffling of
playing
cards, the use of yarrow stalks in the I Ching, and many other
techniques.

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

1 Physical methods

2 Computational
methods

3 Practical applications and
uses of random numbers

4 Activities and
demonstrations

5 "True" random numbers vs.
pseudo-random numbers

6 Generating random numbers
from physical processes

7 Post-processing and
statistical checks

8 Other
considerations

9 Low-discrepancy sequences
as an alternative

10 Generation from a
probability distribution

11 See also

12 External links

[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 systematic 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]

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. 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

to generate numbers. The maximum number of numbers the formula can produce is
the modulus,
m.

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

Most computer programming languages include functions or library routines
that purport to be random number generators. They are often designed to provide
a random byte or word, or a floating point number uniformly
distributed between 0 and 1.

Such library functions often have poor statistical properties and some will
repeat patterns after only tens of thousands of trials. They are often
initialized using a computer's real time clock as the
seed. These functions may provide enough randomness for certain tasks (for
example video games) but are unsuitable where high-quality randomness is
required, such as in cryptographic applications, statistics or numerical
analysis. Much higher quality random number sources are available on most
operating systems; for example /dev/random on various BSD
flavors, Linux, Mac OS X, IRIX, and Solaris, or CryptGenRandom for
Microsoft Windows.

[edit]
Practical applications and uses of random
numbers

Main article: Applications of
randomness

Random number generators have applications in gambling, statistical
sampling, computer simulation,
cryptography, etc.

Note that, in general, where unpredictability is paramount--such as in
security applications-- hardware generators are generally preferred, where
feasible, over pseudo-random algorithms.

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.

Some applications which appear at first sight to be suitable for
randomization are in fact not quite so simple. For instance, a system that
'randomly' selects music tracks for a background music system must only
appear to be random; a true random system would have no restriction on
the same item appearing two or three times in succession.

[edit]
Activities and demonstrations

The SOCR resource
pages contain a number of hands-on interactive activities and demonstrations of random
number generation using Java applets.

[edit]
"True" random numbers vs. pseudo-random
numbers

Main article: pseudorandom
number generator

There are two principal methods used to generate random numbers. One measures
some physical phenomenon that is expected to be random and then compensates for
possible biases in the measurement process. The other uses computational algorithms
that produce long sequences of apparently random results, which are in fact
completely determined by a shorter initial value, known as a seed or key. The latter type
are often called pseudorandom
number generators.

A "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
famously said "Anyone who uses arithmetic methods to produce random numbers is
in a state of sin." How to distinguish a "true" random number from the output of
a pseudo-random number generator is a very difficult problem. However, carefully
chosen pseudo-random number generators can be used instead of true random
numbers in many applications. Rigorous statistical analysis of the output is
often needed to have confidence in the algorithm.

[edit]
Generating random numbers from physical
processes

Main article: hardware
random number generator

There is general agreement that, if there are such things as "true" random
numbers, they are most likely to be found by looking at physical processes which
are, as far as we know, unpredictable.

A physical random number generator can be based on an essentially random
atomic or subatomic physical phenomenon whose randomness can be traced to the
laws of quantum mechanics. An
example of this are the Atari 8-bit computers,
which used noise from an analog circuit to generate true random numbers. [3]
Other examples include radioactive decay, thermal
noise, shot noise and clock
drift. Even Lava Lamps have been used.

To provide a degree of randomness intermediate between specialized hardware
on the one hand and algorithmic generation on the other, some security related
computer software requires the user to input a lengthy string of mouse
movements, or keyboard input.

[edit]
Post-processing and statistical checks

Even given a source of plausible random numbers (perhaps from a quantum
mechanically based hardware generator), obtaining numbers which are completely
unbiased takes care. In addition, behavior of these generators often changes
with temperature, power supply voltage, the age of the device, or other outside
interference. And 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.

Generated random numbers are sometimes subjected to statistical tests before
use to ensure that the underlying source is still working, and then
post-processed to improve their statistical properties.

See also: Statistical
randomness

[edit]
Other considerations

Random numbers uniformly distributed between 0 and 1 can be used to generate
random numbers of any desired distribution by passing them through the inverse
cumulative
distribution function of the desired distribution. Inverse CDFs are also
called quantile functions. To
generate a pair of independent standard normally
distributed random numbers (x, y), one may first generate the
polar coordinates
(r, θ), where r~χ22
and θ~UNIFORM(0,2π)
(see Box-Muller
transform).

Some 0 to 1 RNGs include 0 but exclude 1, while others include or exclude
both.

The outputs of multiple independent RNGs can be combined (for example, using
a bit-wise XOR
operation) to provide a combined RNG at least as good as the best RNG used. More
details about uncorrelated near random bit streams.

Computational and hardware random number generators are sometimes combined to
reflect the benefits of both kinds. Computational random number generators can
typically generate pseudo-random numbers much faster than physical generators
can generate true randomness.

[edit]
Low-discrepancy sequences as an alternative

Some computations making 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 may, and usually does, leave larger gaps.

[edit]
Generation from a probability distribution

There are a couple of methods to generate a random number based on a probability
distribution function. These methods involve transforming a normal random
number in some way. Because of this, these methods work equally well in
generating both pseudo-random and true random numbers. One method, called the inversion
method, involves integrating up to an area greater than or equal to the
random number (which should be generated between 0 and 1 for proper
distributions). A second method, called the acceptance-rejection
method, involves choosing an x and y value and testing whether the function
of x is greater than the y value. If it is, the x value is accepted. Otherwise,
the x value is rejected and the algorithm tries again. [4]

[edit]
See also

Randomization

Randomized
algorithm

Hardware
random number generator

List of
random number generators

Random
number generator attack

Random password
generator

Randomness

[edit]
External links

Random numbers available over the internet and from parties not
specifically known to and trusted by the user should not be used
cryptographically.

http://www.randomizer.org/

Cryptographically Secure Random number on Windows without using
CryptoAPI from MSDN

Random.org - generate random
bitmaps, flip virtual coins etc. (random numbers generated from atmospheric noise from a radio)

Simple Random Number Generator Software (Uses three different
algorithms]

HotBits: Genuine Random
Numbers (random numbers generated from radioactive decays)

LavaRnd
demonstration (random numbers generated from a webcam CCD chip)

RandomNumbers.info
(random numbers generated by exploiting elementary quantum optics process)

Free
Open-Source Generator (Random number generator with open-source code for
Windows)

KenoRND()
(random numbers generated from results of live keno at real casinos)

http://www.true-random.com/ (random numbers generated from
digital noise and based on the central limit theorem)

True (physical) random
number generators (e.g. with USB interface)

http://www.idquantique.com/products/quantis.htm - True random
number generators based on quantum physics

http://random.mat.sbg.ac.at/ - uniform random number
generators

Generating random numbers Generating random numbers in Embedded Systems

RQube Free software for
generating random sequences for experimental purpose in behavioural
sciences and social sciences.

Glossary
of words concerning true random number generation

Retrieved from "http://en.wikipedia.org/wiki/Random_number_generation"

Categories: Randomness |
Information
theory

Views

Article

Discussion

Edit
this page

History

Personal tools

Sign
in / create account

Navigation

Main page

Contents

Featured
content

Current events

Random article

interaction

About Wikipedia

Community
portal

Recent
changes

Contact Wikipedia

Donate to Wikipedia

Help

Search

Toolbox

What
links here

Related
changes

Upload file

Special pages

Printable
version

Permanent
link

Cite
this article

Languages

Česky

Deutsch

Français

Nederlands

Polski

Svenska

中文

اردو

This page was last modified 16:17, 18 November 2007.

All text is available under the terms of the GNU
Free Documentation License. (See Copyrights
for details.)
Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a
U.S. registered 501(c)(3) tax-deductible
nonprofit charity.

Privacy policy

About Wikipedia

Disclaimers