by Nikolai V. Shokhirev

Up: ** Stochastic Labs**

- Pseudorandom numbers

- Probability transformation

- Diffusion, Wiener process

- Geometric Brownian motion

- Ornstein-Uhlenbeck process

In this lab we will take a closer look on various types of pseudorandom numbers.

LCG is one of the oldest and best-known family of pseudorandom number generator (PGNG) algorithms (see links below). They are simple and fast. The algorithms are defined by the recurrence relation:

*X* _{n+1} = ( *a* *X* * _{n}* +

The quality of random numbers is defined by the constants *a*,* c*
and *m* (see some sets of constants
here).
Borland C++ and Delphi PRNG belong to this family of algorithms.

Borland PGN uniform distribution.

These algorithms can be used in simple applications. However, they are not suitable for Monte Carlo simulations (especially multidimensional) because of the serial correlations.

The algorithm is fast and generates high quality random numbers suitable for stochastic processes simulations (Monte Carlo, Diffusion, etc.). In the picture below the sum of 12 random numbers models the normal distribution.

Mersenne twister "Normal" distribution.

Below is the same distribution averaged over 5 bins.

Smoothed normal distribution

A *n*-dimensional low-discrepancy sequence (LDS) is represents uniformly
distributed points in the *n*-dimensional cube (see definitions in the
links below). In the 1D case it produces almost perfect rectangular distribution:

Sobol 1D sequence.

The use of LDSs accelerates the Monte Carlo methods (e.g. integration). However, because of their "regularity", they should not be used for simulation of certain random processes. For example, the sum of two (pseudo)-random uniformly distributed numbers has the triangular distribution:

Triangular (*x _{i}* +

However the sum of two consecutive Sobol numbers has the rectangular distribution again:

Rectangular (*x _{i}* +

Feel free to download the program Test Random and play (at your own risk) with various PRN. I am adding several new features, please check later.

- Linear congruential generator, http://en.wikipedia.org/wiki/Linear_congruential_generator
- Mersenne twister. http://en.wikipedia.org/wiki/Mersenne_twister
- Mersenne Twister Home Page. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
- Mersenne Twister in Pascal/Delphi http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/PASCAL/pascal.html
- Scientific Computing FAQ: Random Number Generators (RNGs) http://www.mathcom.com/corpdir/techinfo.mdir/q210.html
- Pseudorandom number generator. http://en.wikipedia.org/wiki/Pseudorandom_number_generator
- R B Davies, Newran02C - a random number generator library, http://www.robertnz.net/nr02doc.htm
- Random number generation. http://en.wikipedia.org/wiki/Random_number_generator
- Netlib: Random Number Generators. http://www.netlib.org/random/
- Random Number Generation. http://www.taygeta.com/random.xml
- NIST: Random Number Generation and Testing. http://csrc.nist.gov/rng/
- Uniform Random Number Generators: A REVIEW, Pierre L'Ecuyer. http://www.informs-cs.org/wsc97papers/0127.PDF
- ParkMiller random number generator. http://en.wikipedia.org/wiki/Park-Miller_RNG
- List of random number generators. http://en.wikipedia.org/wiki/List_of_random_number_generators
- Uniform random number generators assembly library, by Agner Fog http://www.agner.org/random/randoma.htm
- Low-discrepancy sequence. http://en.wikipedia.org/wiki/Low-discrepancy_sequence
- Fast Generation of Low-Discrepancy Sequences. http://parallel.bas.bg/~emanouil/sequences.html
- The Sobol Quasirandom Sequence. http://people.scs.fsu.edu/~burkardt/f_src/sobol/sobol.html
- The Niederreiter Quasirandom Sequence. http://people.scs.fsu.edu/~burkardt/f_src/niederreiter/niederreiter.html
- TOMS738, Niederreiter's Low Discrepancy Sequence. http://people.scs.fsu.edu/~burkardt/f_src/toms738/toms738.html

©Nikolai V. Shokhirev, 2007-2008