3. Random Number Generation

Every random variate in a simulation is built from i.i.d. U(0,1) numbers; these notes cover where those numbers come from and what makes a generator good.

Motivation. Consider simulating an $M/M/1$ queue (Markovian, i.e. exponential, interarrival times; exponential service times; one server). We must repeatedly generate $X \sim \text{Exp}(\lambda)$, whose c.d.f. is $F(x) = 1 - e^{-\lambda x}$, $x \ge 0$. This can be done from a single uniform random number:

1. Generate $U \sim U(0,1)$.
2. Return $X = -\dfrac{1}{\lambda}\ln U$.

Why it works: setting $U = F(X)$ and solving for $X$ gives $X = F^{-1}(U) = -\frac{1}{\lambda}\ln(1-U)$; since $1-U \sim U(0,1)$ as well, we may use $\ln U$ instead. Then

$$P(X \le x) = P\left(-\tfrac{1}{\lambda}\ln U \le x\right) = P\left(U \ge e^{-\lambda x}\right) = 1 - e^{-\lambda x} = F(x).$$

The same idea applies to other distributions: every random variate in a simulation is built from i.i.d. $U(0,1)$ numbers.

Goal of this chapter. Produce a sequence of i.i.d. $U(0,1)$ random numbers, i.e. numbers with p.d.f.

$$f(x) = \begin{cases} 1, & 0 \le x \le 1, \\ 0, & \text{otherwise.} \end{cases}$$

Three alternative sources of “random” numbers

1. True random numbers (from physical experiments)

• Draw numbered balls from an urn.
• Electrical circuits: a hardware random number machine, e.g. ERNIE (Electronic Random Number Indicator Equipment).
• Disadvantages:
  • Not reproducible. Reproducibility matters in simulation: it makes debugging easier, and it gives sharper comparisons when two alternative systems are run on the same random inputs.
  • Difficult to implement.
  • Slow.

2. Pseudo-random numbers — a completely deterministic sequence that is statistically indistinguishable from a true random sequence. This is what simulation uses in practice, and what the rest of the chapter is about.

3. Quasi-random numbers (used in Monte Carlo integration rather than in simulation)

An integral over $[0,1]$ is an expectation under $U(0,1)$, because the $U(0,1)$ p.d.f. equals $1$ there:

$$\int_0^1 g(x)\,dx = \int_0^1 g(x)\cdot 1\,dx = \mathbf{E}[g(X)], \qquad X \sim U(0,1).$$

So generate $X_1, \dots, X_n \overset{\text{i.i.d.}}{\sim} U(0,1)$ and estimate the integral by

$$\bar{g}(n) = \frac{1}{n}\sum_{i=1}^n g(X_i) \;\longrightarrow\; \mathbf{E}[g(X)].$$

By the CLT the error of this estimator is of order $1/\sqrt{n}$. The idea of quasi-random numbers is to replace the random sequence by a deterministic sequence that covers $[0,1]$ more evenly; this improves the error rate to order $(\ln n)/n$. Such sequences are not i.i.d., so they are useless as simulation inputs, but for integration the even coverage is exactly what helps.

3.1 Random Number Generators (RNGs)

Desired properties of an RNG

1. Uniformity: the sequence should appear to be uniformly distributed on $(0,1)$.
2. Independence: terms in the sequence should not be correlated.
3. Reproducibility: one must be able to reproduce a particular stream of random numbers (e.g. from a seed).
4. Fast, with low memory usage.
5. Long period. A deterministic generator eventually loops. The segment of non-repeating numbers is called a cycle, and its length is the period of the RNG.

flowchart LR
    u1(("u₁")) --> u2(("u₂")) --> u3(("u₃")) --> d[". . ."] --> uP(("u_P")) --> u1

The sequence repeats after $P$ terms, so the period must be far longer than the number of random numbers a simulation will consume.