4.1 Generating Independent Uniform Observations

We begin with a historically prominent method.

Linear Congruential Generator. To generate a sequence of random numbers, start with (B_0), a starting value that is known as a “seed.” Update it using the recursive relationship
[
B_{n+1} = a B_n + c text{ modulo }m, ~~ n=0, 1, 2, ldots .
]
This algorithm is called a linear congruential generator. The case of (c=0) is called a multiplicative congruential generator; it is particularly useful for really fast computations.

For illustrative values of (a) and (m), Microsoft’s Visual Basic uses (m=2^{24}), (a=1,140,671,485), and (c = 12,820,163) (see http://support.microsoft.com/kb/231847). This is the engine underlying the random number generation in Microsoft’s Excel program.

The sequence used by the analyst is defined as (U_n=B_n/m.) The analyst may interpret the sequence {(U_{i})} to be (approximately) identically and independently uniformly distributed on the interval (0,1). To illustrate the algorithm, consider the following.

Example. Take (m=15), (a=3), (c=2) and (B_0=1). Then we have:

step (n) (B_n) (U_n)
0 (B_0=1)
1 (B_1 =mod(3 times 1 +2) = 5) (U_1 = frac{5}{15})
2 (B_2 =mod(3 times 5 +2) = 2) (U_2 = frac{2}{15})
3 (B_3 =mod(3 times 2 +2) = 8) (U_3 = frac{8}{15})
4 (B_4 =mod(3 times 8 +2) = 11) (U_4 = frac{11}{15})

Sometimes computer generated random results are known as pseudo-random numbers to reflect the fact that they are machine generated and can be replicated. That is, despite the fact that {(U_i)} appears to be i.i.d, it can be reproduced by using the same seed number (and the same algorithm). The ability to replicate results can be a tremendous tool as you use simulation while trying to uncover patterns in a business process.

The linear congruential generator is just one method of producing pseudo-random outcomes. It is easy to understand and is (still) widely used. The linear congruential generator does have limitations, including the fact that it is possible to detect long-run patterns over time in the sequences generated (recall that we can interpret “independence” to mean a total lack of functional patterns). Not surprisingly, advanced techniques have been developed that address some of this method’s drawbacks.

[raw] [/raw]