5.7: Pseudo-random Number Generation

Last updated
Save as PDF

Page ID: 30981

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

All of the random sampling strategies discussed in the previous section require a random sample uniformly distributed in the range (0,1). Fortunately, there are several well known algorithms for generating such samples, called pseudo - random numbers. These algorithms are deterministic. However, the properties of the sequence of pseudo-random numbers make them look random. These properties include the following:

The numbers do not exhibit any statistical correlation with each other.
The numbers appear to be uniformly distributed in the range (0,1).
There are many, many (at least 1,000,000) numbers in sequence.
All possible numbers in the sequence are generated before any number repeats.

Because the pseudo-random number generation algorithms are deterministic, a sequence of numbers can be regenerated whenever necessary. This is important in simulation both for debugging and experimentation using common random numbers. Imagine the difficulty of removing a bug from a model if the results were randomly different each time the model was executed!

A sequence of pseudo-random numbers is called a stream. Having multiple streams of random numbers allows sampling from each particular probability distribution used in a model to be associated with a particular stream. For example in the two stations in a series model, the time between arrivals and the operation time at station A would be assigned different streams. This means for example that if the probability distribution modeling the operation time at station A were changed, the times between arrivals would remain the same.

As in the previous section, one approach to pseudo-random number generation will be presented. Other approaches for generating pseudo-random numbers are given in Banks, Carson, Nelson, and Nicol (2009) as well as Law (2007). Schmeiser (1980) provides a comprehensive survey.

Perhaps the most common type of pseudo-random number generation algorithm, with respect to use in simulation languages, is the linear congruential generator (Lehmer, 1951). The linear congruential generator (LCG) has the form:

\begin{align}Z_{i}=\left(a^{*} Z_{i-1}+c\right) \bmod (m)\tag{5-3}\end{align}

\begin{align}r_{i}=Z_{i} / m\tag{5-4}\end{align}

The Z_i ’s are a set of integers that range from 0 to m-1. The integer Z_i is a remainder and m is the divisor. Other parameters of the generator are a multiplier a, an increment c, and the first integer Z₀. The pseudo-random number r_i is obtained by dividing Z_i by m. Fortunately for our purposes, values for the parameters (a, c, m, and Z₀) that result in the desirable properties listed above are used by commercial simulation languages.

The generator is recursive that is Z_i is a function of Z_i-1 . Note that at most, m distinct Z_i ’s and thus r_i’s (pseudo-random numbers) can be obtained. Once Z₀ is generated a second time, the entire sequence of Z_i’s, and thus r_i’s, will be repeated and in the same sequence as the first time.

Consider the example LCG shown in Table 5-3. The LCG parameter values are shown in the table. Note that the Z_i’s range from 0-8. All nine of the Z_i’s are generated before any value repeats. Thus, the r_i’s appear to be as uniformly distributed in the range (0,1) as nine numbers can be. The statistical correlation between the r_i’s is low, 0.030. Since the number of values generated is only 9, the value of m is too small for an effective LCG. However, it suffices for an example.

Table 5-3: Example LCG
		i	Z_i	r_i
M	9	0	8	0.889
A	4	1	1	0.111
C	5	2	0	0.000
		3	5	0.556
		4	7	0.778
		5	6	0.667
		6	2	0.222
		7	4	0.444
		8	3	0.333
		9	8	0.889
		10	1	0.111
		11	0	0.000
		12	5	0.556