Phase 13 - Lesson 13.1

Random-Number Generation and Sampling

From a stream of uniforms to any distribution: inverse transform, acceptance–rejection, and Box–Muller.

⏱ 50 min● Intermediate🔗 Prereqs: Probability (Phase 7), basic calculus

↖ Phase 13 hub

Leads to: Every Monte Carlo estimator downstream consumes the samples built here.

Learning Objectives

Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.

Explain what a pseudo-random uniform generator is and why period, uniformity, and reproducibility matter.
Derive and implement the inverse-transform method and prove it produces the target distribution.
Implement acceptance–rejection sampling and compute its expected acceptance rate.
Derive the Box–Muller transform for generating standard normal variates.
Diagnose sampler correctness with moment and empirical-CDF checks.

Key Vocabulary

Pseudo-random number generator (PRNG): A deterministic recursion that, seeded once, emits a stream statistically indistinguishable from i.i.d. uniforms on \([0,1)\).

Period: The number of draws before a PRNG’s output sequence repeats; must vastly exceed the sample size used.

Inverse-transform method: Sampling \(X=F^{-1}(U)\) with \(U\sim\mathrm{Unif}(0,1)\) to realize any CDF \(F\).

Acceptance–rejection: Sample from an easy proposal \(g\), keep points with probability \(f(x)/(Mg(x))\) to hit target \(f\).

Box–Muller transform: A pair of uniforms mapped to a pair of independent standard normals via polar coordinates.

Reproducibility (seed): Fixing the generator’s initial state so a stochastic run can be replayed exactly for debugging and testing.

Intuition & Motivation

Intuition

Almost every simulation is built on one primitive: a faucet of numbers that behave like independent draws from \(\mathrm{Unif}(0,1)\). They are not truly random - a deterministic recursion produces them - but a good generator is statistically indistinguishable from randomness over any run you will ever make. Given that faucet, the whole game is transformation: bend uniforms into normals, exponentials, or whatever the model needs. The inverse-CDF is the universal bender; rejection handles densities you cannot invert; Box–Muller is a clever closed-form shortcut for the normal, the workhorse of finance.

Uniform pseudo-random generators

A PRNG is a map \(s_{n+1}=T(s_n)\) on an internal state with an output function \(u_n=G(s_n)\in[0,1)\). Given one seed \(s_0\), the entire stream is fixed - that is a feature: it makes runs reproducible. A usable generator needs a huge period, near-perfect equidistribution, and no low-order correlations. Modern defaults (e.g. the Mersenne–Twister or PCG family behind NumPy’s default_rng) pass these tests; the ancient linear-congruential toys do not and must be avoided for serious work.

Key Idea

Treat the uniform stream as the only true source of randomness. Everything else - normals, paths, prices - is a deterministic function of uniforms. This is why fixing a seed reproduces an entire pricing run exactly.

Inverse-transform method

Let \(F\) be a CDF with generalized inverse \(F^{-1}(u)=\inf\{x:F(x)\ge u\}\). The claim is simple and exact:

Theorem - Inverse-transform (probability integral transform)

If \(U\sim\mathrm{Unif}(0,1)\) then \(X=F^{-1}(U)\) has CDF \(F\). Conversely, if \(X\) is continuous with CDF \(F\), then \(F(X)\sim\mathrm{Unif}(0,1)\).

Proof of the forward direction, for strictly increasing continuous \(F\):

\[\Prob(X\le x)=\Prob\big(F^{-1}(U)\le x\big)=\Prob\big(U\le F(x)\big)=F(x),\] (13.1)

using monotonicity of \(F\) and \(\Prob(U\le u)=u\) for \(u\in[0,1]\). For the exponential, \(F(x)=1-e^{-\lambda x}\) inverts to \(X=-\tfrac1\lambda\ln(1-U)\) (or \(-\tfrac1\lambda\ln U\), since \(1-U\sim U\)).

Worked Example - Sampling an exponential by inverse transform

Target CDF: \(F(x)=1-e^{-\lambda x}\) for \(x\ge0\).

Solve \(u=1-e^{-\lambda x}\) for \(x\): \(e^{-\lambda x}=1-u\ \Rightarrow\ x=-\tfrac1\lambda\ln(1-u)\).

Draw \(U\sim\mathrm{Unif}(0,1)\), return \(X=-\tfrac1\lambda\ln(1-U)\).

Check: \(\E[X]=1/\lambda\) and \(\Var(X)=1/\lambda^2\); verify empirically that the sample mean matches.

Acceptance–rejection

When \(F^{-1}\) has no closed form, sample from an easy proposal density \(g\) that dominates the target \(f\): find \(M\) with \(f(x)\le M\,g(x)\) for all \(x\). Repeat: draw \(Y\sim g\) and \(U\sim\mathrm{Unif}(0,1)\); accept \(Y\) if \(U\le f(Y)/(M\,g(Y))\).

Proposition - Correctness and efficiency of rejection

Accepted draws have exactly density \(f\), and each proposal is accepted with probability \(1/M\), so the expected number of proposals per accepted sample is \(M\). Choose \(g\) and \(M\) to keep \(M\) close to 1.

\[\Prob(\text{accept}\mid Y=y)=\frac{f(y)}{M\,g(y)},\qquad \Prob(\text{accept})=\int \frac{f(y)}{M\,g(y)}g(y)\,dy=\frac1M.\] (13.2)

Box–Muller for normals

The normal CDF has no elementary inverse, but a pair of independent normals has a rotationally symmetric density that is easy in polar form. Draw \(U_1,U_2\sim\mathrm{Unif}(0,1)\) and set

\[Z_1=\sqrt{-2\ln U_1}\,\cos(2\pi U_2),\qquad Z_2=\sqrt{-2\ln U_1}\,\sin(2\pi U_2).\] (13.3)

Then \(Z_1,Z_2\sim\Normal(0,1)\) independently. Intuition: \(R^2=-2\ln U_1\sim\mathrm{Exp}(\tfrac12)=\chi^2_2\) is the squared radius and \(\Theta=2\pi U_2\) the uniform angle - exactly the polar law of a 2-D standard normal.

Interactive: build and test an inverse-transform sampler

Common Mistakes to Avoid

Using a low-quality generator (bare LCG, or reusing random.seed mid-stream) so draws are correlated; always use a vetted PRNG and one seeded generator object.
Forgetting that \(F^{-1}\) needs the proper inverse on \([0,1]\); feeding \(\ln U\) without the minus sign gives negative-rate garbage.
In rejection sampling, picking \(M\) too large (slow) or too small so \(f\le Mg\) fails and the output is biased.
Assuming Box–Muller needs only one uniform - it consumes two and returns two normals; discarding \(Z_2\) wastes half your entropy.

Quant Practitioner Tips

Seed one rng = np.random.default_rng(seed) and thread it everywhere - reproducibility is a debugging superpower.
For the normal, prefer the library’s rng.standard_normal (fast, vectorized) unless you specifically need Box–Muller for teaching or low-discrepancy inputs.
Validate any new sampler with three cheap checks: sample mean, sample variance, and a couple of ECDF points against the theoretical CDF.

Practice this in the Euler Lab

Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.

Applied:
#493 Under the Rainbow (18%, tier B)

Challenge:
#567 Reciprocal Games I (53%, tier C) #568 Reciprocal Games II (61%, tier C)

9 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.

Knowledge Check

Q1 Medium

The inverse-transform method sets \(X=F^{-1}(U)\) with \(U\sim\mathrm{Unif}(0,1)\). Why does \(X\) have CDF \(F\)?

Because \(F\) is always linear

Because \(\Prob(F^{-1}(U)\le x)=\Prob(U\le F(x))=F(x)\) by monotonicity

Because \(U\) is normal

Because \(F^{-1}\) is random

Q2 Medium

In acceptance–rejection with \(f\le Mg\), the expected number of proposals per accepted sample is:

\(1\)

\(M\)

\(1/M\)

\(M^2\)

Q3 Easy

Box–Muller consumes and produces how many values?

One uniform, one normal

Two uniforms, two independent normals

One uniform, two normals

Two normals, one uniform

Practical Exercise

(a) Derive the inverse-transform sampler for the standard Cauchy density \(f(x)=\tfrac1{\pi(1+x^2)}\), whose CDF is \(F(x)=\tfrac12+\tfrac1\pi\arctan x\). (b) Explain why the sample mean of Cauchy draws does not stabilize as \(n\) grows.

▶ Show full solution

(a) Invert \(u=\tfrac12+\tfrac1\pi\arctan x\): \(\arctan x=\pi(u-\tfrac12)\), so \(X=\tan\big(\pi(U-\tfrac12)\big)\) with \(U\sim\mathrm{Unif}(0,1)\).

(b) The Cauchy has no finite mean (its density’s tails decay like \(1/x^2\), so \(\int|x|f(x)\,dx=\infty\)). The law of large numbers requires a finite mean; without it the running average of samples wanders indefinitely and never converges. This is a vivid warning that Monte Carlo silently fails when moments do not exist.

After the reveal, answer for yourself: Which of the three methods (inverse, rejection, Box–Muller) would you reach for to sample a truncated normal, and why?

Lesson Summary

Every simulation rests on a good uniform PRNG; transformations turn uniforms into any distribution. The inverse-transform \(X=F^{-1}(U)\) is exact whenever \(F^{-1}\) is available; acceptance–rejection handles intractable inverses at cost \(M\) proposals per sample; Box–Muller gives normals in closed form. Always validate a new sampler against theoretical moments and CDF points.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: State the inverse-transform method and why it works.
A: Draw \(U\sim\mathrm{Unif}(0,1)\) and return \(X=F^{-1}(U)\). Then \(\Prob(X\le x)=\Prob(U\le F(x))=F(x)\) by monotonicity of \(F\).

Q: What is the acceptance probability and cost of rejection sampling with envelope constant \(M\)?
A: Each proposal accepts with probability \(1/M\); the expected number of proposals per accepted draw is \(M\), so tighter envelopes (smaller \(M\)) are cheaper.

Completion Checklist

I can explain the core ideas in my own words
I worked the derivations/examples by hand
I completed the interactive workbench(es)
I passed the knowledge check

Confidence / mastery rating

Personal notes

← 12.6 Next: 13.2 →