16.2 Random numbers and random variates
Computers produce pseudo-random numbers: deterministic sequences that pass statistical tests of uniformity and independence. The classical linear congruential generator is \(x_{k + 1} = (ax_k + c) \bmod m\), \(u_k = x_k/m\); with \(m = 2^{31} - 1\), \(a = 16\,807\), \(c = 0\) (Park and Miller’s minimal standard) its period is \(m - 1\). Modern libraries use generators with far longer periods and better high-dimensional uniformity (NumPy’s default is PCG64), but the principle is the same, and a fixed seed makes a simulation reproducible.
Other distributions are obtained from uniforms.
Theorem 16.2.1 (Inverse transform). If \(F\) is a distribution function and \(U\) is uniform on \((0, 1)\), then \(X = F^{-1}(U)\), with \(F^{-1}(u) = \inf \{x : F(x) \geq u\}\), has distribution function \(F\).
Proof. For every \(x\), \(F^{-1}(u) \leq x\) if and only if \(u \leq F(x)\), by the definition of \(F^{-1}\) and the right-continuity of \(F\). So \(P(X \leq x) = P(U \leq F(x)) = F(x)\). □
For the exponential distribution with rate \(\lambda \), \(F(x) = 1 - e^{-\lambda x}\) and \(X = -\ln (1 - U)/\lambda \). For a discrete distribution the method searches the cumulative probabilities. When \(F^{-1}\) has no closed form, acceptance–rejection draws from a simpler density \(g\) with \(f \leq cg\) and accepts a draw \(Y\) with probability \(f(Y)/cg(Y)\); the accepted values have density \(f\), and on average \(c\) draws are needed per value. Normal variates are produced by the Box–Muller transform or by specialised rejection methods.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.