Quiz Study Guide — Appendix A
This deck is a checklist, not a summary. Every slide is phrased as something you should be able to state, derive, or compute without looking it up.
Relationship to Chapter 2
This appendix is the theory; Chapter 2 is how the KSL implements it. Several questions can be answered from either, but the formulas live here.
Pseudo-random numbers
Random variates
You should be able to:
You should be able to:
A deterministic sequence of numbers in \((0,1)\), produced by an algorithm, that nevertheless has the same relevant statistical properties as a true sequence of \(U(0,1)\) random numbers.
Why generators instead of dice, coins, or electronic noise? They are fast, cheap, and reproducible — the same seed gives the same sequence. That reproducibility is what makes debugging, controlled comparison of alternatives, and variance reduction possible.
Re-running a simulation gives identical results because the generator restarts from the same seed. Seeding from the system clock destroys this, so it is recommended against in a simulation study.
\[R_{i+1} = (a R_i + c) \bmod m, \qquad U_i = R_i / m\]
| Parameter | Name and role |
|---|---|
| \(m\) | The modulus — bounds \(R_i\) and caps the achievable period |
| \(a\) | The constant multiplier |
| \(c\) | The increment; when \(c = 0\) the LCG is multiplicative |
| \(R_0\) | The seed — determines the stream |
The period is the length of the cycle of distinct values before the sequence repeats. If it equals \(m\), the LCG has full period.
An LCG achieves full period if and only if all three hold:
Two special cases:
\(m = 2^{31} - 1 = 2{,}147{,}483{,}647\) is common on 32-bit machines because it is the largest representable 2’s-complement integer and it is prime.
| Property | Value |
|---|---|
| Construction | Combination of two MRGs |
| Period | \(\approx 3.1 \times 10^{57}\) |
| Streams | \(\approx 1.8 \times 10^{19}\), each of length \(\approx 1.7 \times 10^{38}\) |
| Initial state | A 6-element seed vector — not a single integer |
Streams are effectively independent as long as they do not overlap, so dedicating a fixed stream per source of randomness synchronizes pseudo-random number use across alternatives.
Trap
Bootstrap resampling is not one of the four. That is the classic distractor.
\[X = F^{-1}(U), \qquad U \sim U(0,1)\]
It is preferred when available because it uses exactly one \(U(0,1)\) per generated \(X\) — which is what makes common random numbers and antithetic variates work cleanly.
For discrete distributions it is a table lookup in the CDF: pick \(x_i\) with \(F(x_{i-1}) < u \leq F(x_i)\). Because \(F\) is non-decreasing, you need only check the upper limit of each interval.
| Distribution | Inverse transform |
|---|---|
| Exponential, rate \(\lambda\) (mean \(1/\lambda\)) | \(X = -\frac{1}{\lambda}\ln(1-U)\) |
| Continuous Uniform\((a,b)\) | \(X = a + U(b-a)\) |
| Discrete Uniform on \(\{a,\dots,b\}\) | \(X = a + \lfloor (b-a+1)U \rfloor\) |
| Weibull, shape \(\alpha\), scale \(\beta\) | \(X = \beta\left[-\ln(1-U)\right]^{1/\alpha}\) |
| Geometric on \(\{0,1,2,\dots\}\) | \(X = \lfloor \ln(1-U)/\ln(1-p) \rfloor\) |
| Shifted geometric on \(\{1,2,3,\dots\}\) | \(X = 1 + \lfloor \ln(1-U)/\ln(1-p) \rfloor\) |
| Bernoulli\((p)\) | \(X = 1\) if \(U \leq p\), else \(X = 0\) |
If interarrival times are exponential with mean \(1/\lambda\), then the count of arrivals in \([0,t]\) is Poisson with mean \(\lambda t\).
Algorithm: generate exponential interarrival times by inverse transform, accumulate them until the cumulative sum first exceeds \(t\), and return the count of arrivals that fell within \([0,t]\).
Conditions of the Poisson process: the probability of more than one event in a small subinterval is zero; the probability of one event is proportional to the subinterval length; subintervals are independent. As \(n \to \infty\) with \(\lambda = np\) held constant, these lead to the Poisson distribution.
Some random variables are the sum of i.i.d. simpler random variables.
| Target | Sum of |
|---|---|
| Binomial\((n,p)\) | \(n\) i.i.d. Bernoulli\((p)\) |
| Negative binomial \((r,p)\) on \(\{0,1,2,\dots\}\) | \(r\) i.i.d. geometric\((p)\) |
| Erlang\((r,\lambda)\) | \(r\) i.i.d. exponentials, each with rate \(\lambda\) |
| Chi-squared | squared independent standard normals |
| Normal | independent normals |
Limitation: convolution is not a general method. It applies only when the target genuinely is such a sum.
The majorizing function must satisfy \(g(x) \geq f(x)\) for all \(x\), and \(c = \int g(x)\,dx < \infty\), so that \(w(x) = g(x)/c\) is a valid PDF that is easy to sample.
The loop: generate \(W \sim w(x)\) and \(U \sim U(0,1)\); accept \(W\) if \(U \cdot g(W) \leq f(W)\); otherwise reject and repeat.
\[P_a = \frac{1}{c}\]
The closer \(g\) is in shape to \(f\), the smaller \(c\), the higher the acceptance probability, and the more efficient the algorithm.
Textbook example. \(f(x) = \tfrac34(1-x^2)\) on \([-1,1]\) with flat \(g(x) = 3/4\).
Mixture. \(F_X(x) = \sum_{i=1}^{k}\omega_i F_{X_i}(x)\), with the \(\omega_i\) behaving as a discrete distribution. Sample an index \(I \sim \omega_i\) first, then sample \(X\) from \(F_{X_I}\) — do not sample every component and average.
The hyper-exponential is a mixture of exponentials with different rates; its defining feature is \(c_v > 1\), useful for high variability — service times with mutually exclusive phases, such as credit-card versus cash checkout.
Truncation to \([a,b]\).
\[F^*(x) = \frac{F(x)-F(a)}{F(b)-F(a)}, \qquad X = F^{-1}\bigl(F(a) + U[F(b)-F(a)]\bigr)\]
Shift. \(Y = X + \delta\) has density \(g(y) = f(y-\delta)\): generate \(X\) by any method and add \(\delta\). A shifted Weibull suits a known minimum, such as a minimum setup time.