Random Numbers
Experimental observations are characterized by sets of distinctive features. These
features fall into two groups:
- quantitative features, such as results of measurements or calculations
- qualitative features, such as the color of the object, occurrence or non-occurrence
Qualitative results may be presented as quantitative if some appropriate
conventions have been developed and applied. Thus, a number can express the result
even if the result is a particular quality feature. If the result is a random
phenomenon, such number is called random.
Besides data from experimental observations, numerical methods produce imitations
of a large amount of random numbers for various computational areas [Knuth81]. Methods that use random numbers to
perform a simulation of phenomena are called Monte Carlo methods. Monte Carlo
methods perform the most complex simulations in natural and social sciences,
financial analysis, physics of turbulence, rarefied gas and fluid simulations,
physics of high energies, chemical kinetics and combustion, radiation transport
problems, and photorealistic rendering.
Monte Carlo methods can help you solve various numerical problems, such as:
- ordinary stochastic differential equations
- ordinary differential equations with random entries
- boundary value problems for partial differential equations
- integral equations
- evaluation of high-dimensional integrals including path-dependent integrals.
- random variables and order statistics simulation
- stochastic processes
- random samplings and permutations
For various reasons [Brat87], random number generation based on completely deterministic
algorithms has become most common. It is obvious, however, that numbers obtained in
a strictly deterministic way cannot be considered truly random as they only imitate
randomness. In fact, such numbers are pseudorandom. Ideally, pseudorandom numbers
imitate "truly" random numbers so well that without knowing the method of
pseudorandom number generation and judging only by the output sequence, you cannot
distinguish it within a reasonable time from a "truly" random sequence with more
than 50% probability [L'Ecu94]. The output
sequence of most pseudorandom number generators is easily predictable. This is
acceptable because practical applications may not require strict unpredictability.
However, there are certain applications for which most now existing pseudorandom
generators are useless and at times simply dangerous. For example, the applications
dealing with geometrical behavior of high-dimensional random vectors. Most of the
existing pseudorandom generators should never be used for cryptographic
purposes.
Pseudorandom number generators imitate finite sequences of independent identically
distributed (i.i.d.) random numbers. However, some numerical methods do not really
require independence between random numbers in a sequence. Such methods (for
example, a numerical integration and optimization) fill the space with numbers as
close to a given distribution as possible at the expense of independence. Such
sequences do not look random at all and are called quasi-random (or low-discrepancy)
sequences. The respective generators are called quasi-random number generators, and
Monte Carlo methods dealing with quasi-random numbers are called Quasi-Monte Carlo
methods.
Unlike pseudo- and quasi-random number generators based on deterministic
algorithms, non-deterministic random number generators rely on physical phenomena,
such as metastability, thermal noise in resistors, quantum or atmospheric noise. The
most important feature of non-deterministic random number generators is
unpredictability specified in terms of forward and backward resistance [NIST800-22]. Such generators are primarily used in
cryptographic applications, gambling and other games of chance. High quality
non-deterministic random number generators may be also applied in scientific
simulations, especially those that are sensitive to multidimensional structure of
random vectors.
Hereinafter, the term "random number generator", or RNG, refers to pseudo-, quasi-,
and non-deterministic random number generators, unless the difference between them
is important in the context.