Pseudo Random Number Generator

You don't want to use a computer which does random things like a cat. Basically computers are not good at random things. But we need random numbers (or random variables) for stochastic simulations. We have already used a pseudo-random number generator drand48() to generate some random looking sequence of numbers. Let's take a look at how to generate uniform pseudo-random numbers in more details.

• Early method by von Neumann: ``middle square''
  1. starting from a number (e.g. 8653)
  2. square it (74874409)
  3. take the middle 4 digits to create a new random number (8744)
  4. example sequence
     8653, 8744, 4575, 9306 6016 1922, 6940, ...

• A sequence of pseudo-random numbers is a deterministic sequence of numbers with the same relevant statistical propoerties as a sequence of random numbers.
• There are tests of ``randomness'': e.g, uniformly dispersed, not predictable. ``middle square'' method is not really good.
• A better, classic PRNG: linear congruential generator
  
  
  $$X_i = (a X_{i-1} + c) \% M$$
  
  
  • Given a seed ($X_0$), we can calculate the next pseudo-random number.
    srand48(integer) was giving this initial value.
  • Example sequences:
    
    1. M=13, a=2, c=0, seed = 4
       
       
       
       
    2. M=16, a=3, c=0, seed = 1
       1, 3, 9, 11, 1, ...
    3. M=16, a=3, c=0, seed = 2
       2, 6, 2, ...
  • periodic with a period $k \le M$
    Some seeds can give shorter periods.
    Longer period is desirable (Larger M).
  • But longer period is not the only requirement.
    For example, a = c = 1, Large M can produce the full period of k = M.
    0, 1, 2, 3, 4, ..., M-1, 0, ...
  • This PRNG is well studied and seems to be good as long as a, c, M are carefully chosen.
  • drand48() uses this algorithms and returns $X_i / M$ to convert the range to be [0,1).
• There are many ``improved'' PRNGs were proposed, but many failed the tests of desirable randomness.
• In some simulations, you need to draw many numbers from PRNG, so high period and high speed is desirable.
• Mersenne twister MT 19937 (Matsumoto and Nishimura 1997) seems to be the current standard
  
  • long period $2^{19937} - 1$ (cf, period of drand48() is less than $2^{48}$)
  • Passes stringent randomnes tests.
  • Pretty fast