Random Numbers

Experimental observations are characterized by sets of distinctive features. These features fall into two groups:

  1. quantitative features, such as results of measurements or calculations

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

Beside 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:

  1. ordinary stochastic differential equations

  2. ordinary differential equations with random entries

  3. boundary value problems for partial differential equations

  4. integral equations

  5. evaluation of high-dimensional integrals including path-dependent integrals.

  6. random variables and order statistics simulation

  7. stochastic processes

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

Para obter mais informações sobre otimizações de compiladores, consulte Aviso sobre otimizações.