Archive for June, 2007

Random Number Generators

June 8, 2007

Generating random numbers is a very challenging task. The result of any algorithm at best will be pseudo-random.

Linear Congruential Generators:

By choosing carefully three integer parameters, A, B and M, we can generate a sequence of random numbers, X_i

X_i= {1 \over M}\left( A \, X_{i-1} + B \right) \mod M

One of the shortcoming of such a method is that it has at most a period of order M. In addition, the sequence can be highly correlated. In order to correct these problems we can extend this method to higher dimensions.

Combined Linear Congruential Generators:

A collection of n carefully assigned triplets, A_a, B_a and M_a can be used to build a sequence of random numbers with a period of order $\prod_a M_a$. First we build $n$ parallel sequence of random numbers

x^a_i = \left( A_a \, x_{i-1}^a + B_a \right) \mod M_a

then out of them we build a sequence of random numbers with better quality.

X_i= {1 \over M}\left( \prod_a x^a_i \right) \mod M

were M is defined as \max(M_a). Also a extra shuffling procedure can reduce the correlation in any sequence.

Lagged Fibonacci Generators:

We can use more than one of the previous number in building the next number in the sequence, e.g. X_i = {1\over M} \left( \sum_{k=0}^K A_k X_{i-k} +B \right) \mod M. Finally they don’t need to be even sequential and can lag by any predetermined integers. For the Fibonacci generator to work properly we need a starter generator of other kind to build the first K random number (maximum lag) needed for Fibonacci algorithm.

Posted in Stochastic Processes | Leave a Comment »