Not That Abstract
Français English

Computing with chance

The exact statements and the proofs of what the film showed.

How many samples does it take to be right, and how do you prove it?

In 1946, the mathematician Stanislaw Ulam wonders what chance a game of solitaire has of ending in a win. The exact calculation is out of reach; playing a hundred games and counting is not. This chapter turns that sickbed idea into a method of computation, and above all into a verifiable method: we will be able to say how many samples are needed, and with what guarantee.

The chapter follows the film of session 1, “Computing with chance”: Ulam’s problem (Section 1.1), the law of large numbers (Section 1.2), computing an area (Section 1.3), the Monte Carlo estimator and its two textbook cases, the call option and an insurer’s ruin (Section 1.4), the central limit theorem and the confidence interval (Section 1.5), dimension and rare events (Section 1.6).

1.1 Ulam’s problem#

Recovering from encephalitis, in Los Angeles, Ulam plays Canfield solitaire, a card game for one player with 52 cards. He tries to calculate the probability that a deal comes out successfully; but the number of possible orders of the deck is 52!≈52! \approx 8.07×1067\times 10^{67}, and no enumeration is conceivable. He then thinks of laying the cards out “say one hundred times” and counting the successes (Eckhardt 1987). With John von Neumann, he immediately sees that the same idea applies to neutron diffusion at Los Alamos: a problem with countless dimensions, in which an equation can be replaced by a sequence of random operations. The code name, “Monte Carlo”, is suggested by Nicholas Metropolis, in memory of an uncle of Ulam’s who borrowed money from relatives to go gambling at the casino (Metropolis 1987); the first paper on the method appears in 1949 (Metropolis and Ulam 1949).

The question to keep in mind: how many games would Ulam have to play to know his chance to within 1%? It is answered in Section 1.5.

1.2 A probability is a proportion#

1.2.1 The setting#

We work on a probability space (Ω,F,P)(\Omega, \mathcal F, \mathbb{P}). A real random variable XX is a measurable function from Ω\Omega to R\mathbb{R}; its distribution is the image measure PX(B)=P(X∈B)\mathbb{P}_X(B) = \mathbb{P}(X \in B).

Definition 1.1Sample#

Random variables X1,X2,…X_1, X_2, \dots form a sample (or i.i.d. sequence) with distribution μ\mu if they are independent and all have distribution μ\mu. To simulate XX is to produce, on a computer, realisations of such a sample.

A probability is an expected value: for every event AA, P(A)=E[1A]\mathbb{P}(A) = \mathbb{E}[\mathbf{1}_A], and Var⁡(1A)=p(1−p)≤1/4\operatorname{Var}(\mathbf{1}_A) = p(1-p) \le 1/4 if p=P(A)p = \mathbb{P}(A). Estimating a probability therefore means estimating the mean of a variable that equals 1 or 0: the proportion p^N=k/N\htmlClass{c-simu}{\hat p_N} = k/N of successes among NN trials.

1.2.2 Ten tosses: the exact result becomes rare#

In ten tosses of a fair coin, the number of heads S10S_{10} follows the binomial distribution P(S10=k)=(10k)2−10\mathbb{P}(S_{10} = k) = \binom{10}{k} 2^{-10}. There are (105)=252\binom{10}{5} = 252 sequences out of 1,024 that give exactly five heads: only 24.6%. Six heads and four tails, or the reverse, happens 41% of the time. The video opens on six heads and four tails: nothing unusual.

Number of heads in ten tosses: 10,000 simulated series (blue) and the exact binomial distribution (orange).
Figure 1.1 Number of heads in ten tosses: 10,000 simulated series (blue) and the exact binomial distribution (orange).

The simulation of 10,000 series gives 2,470 series with five heads, that is 24.70%; the blue bars land on the orange marks. The larger NN grows, the more improbable “exactly half” becomes, but the more certain “about half” becomes: that is what the law of large numbers says.

1.2.3 The law of large numbers#

Proposition 1.1Bienaymé–Chebyshev inequality#

If E[Y2]<∞\mathbb{E}[Y^2] < \infty, then for all ε>0\varepsilon > 0, P(∣Y−E[Y]∣≥ε)≤Var⁡(Y)/ε2\mathbb{P}(|Y - \mathbb{E}[Y]| \ge \varepsilon) \le \operatorname{Var}(Y)/\varepsilon^2.

Proof

The inequality 1{∣Y−EY∣≥ε}≤(Y−EY)2/ε2\mathbf{1}_{\{|Y - \mathbb{E}Y| \ge \varepsilon\}} \le (Y - \mathbb{E}Y)^2/\varepsilon^2 holds pointwise; take expectations.

Theorem 1.1Weak law of large numbers#

Let X1,X2,…X_1, X_2, \dots be a sample with E[X12]<∞\mathbb{E}[X_1^2] < \infty, μ=E[X1]\mu = \mathbb{E}[X_1] and σ2=Var⁡(X1)\sigma^2 = \operatorname{Var}(X_1). Then the sample mean XˉN=1N∑i=1NXi\bar X_N = \frac1N \sum_{i=1}^N X_i satisfies, for all ε>0\varepsilon > 0, P(∣XˉN−μ∣≥ε)≤σ2Nε2→N→∞0. \mathbb{P}\big(|\bar X_N - \mu| \ge \varepsilon\big) \le \frac{\sigma^2}{N \varepsilon^2} \xrightarrow[N\to\infty]{} 0 .

Proof

By linearity, E[XˉN]=μ\mathbb{E}[\bar X_N] = \mu; by independence, the variances add up: Var⁡(XˉN)=N−2∑iVar⁡(Xi)=σ2/N\operatorname{Var}(\bar X_N) = N^{-2} \sum_{i} \operatorname{Var}(X_i) = \sigma^2/N. Apply Proposition 1.1 to Y=XˉNY = \bar X_N.

The weak law says that the error is rarely large; the strong law says that the sequence of estimates, the one we see settling down on a screen, converges.

Theorem 1.2Strong law of large numbers, Kolmogorov#

If X1,X2,…X_1, X_2, \dots is a sample with E∣X1∣<∞\mathbb{E}|X_1| < \infty, then XˉN→E[X1]\bar X_N \to \mathbb{E}[X_1] almost surely.

Proof

We prove the statement under the stronger assumption E[X14]<∞\mathbb{E}[X_1^4] < \infty, which is enough for this whole course; the general case E∣X1∣<∞\mathbb{E}|X_1| < \infty requires a truncation argument (Etemadi 1981; Durrett 2019). Replacing XiX_i by Xi−μX_i - \mu, we may assume μ=0\mu = 0. Write SN=∑i≤NXiS_N = \sum_{i \le N} X_i. When SN4S_N^4 is expanded, the terms that contain some XiX_i to the power 1 have zero expectation by independence; what remains is E[SN4]=N E[X14]+3N(N−1) σ4≤CN2. \mathbb{E}[S_N^4] = N\,\mathbb{E}[X_1^4] + 3N(N-1)\,\sigma^4 \le C N^2 . Markov’s inequality gives P(∣SN/N∣>ε)≤E[SN4]/(N4ε4)≤C/(ε4N2)\mathbb{P}(|S_N/N| > \varepsilon) \le \mathbb{E}[S_N^4]/(N^4\varepsilon^4) \le C/(\varepsilon^4 N^2), the general term of a convergent series. By the Borel–Cantelli lemma, almost surely ∣SN/N∣≤ε|S_N/N| \le \varepsilon from some index onwards. We conclude by taking ε=1/j\varepsilon = 1/j, j∈N∗j \in \mathbb N^* (a countable intersection of almost sure events).

Applied to Xi=1AiX_i = \mathbf{1}_{A_i}, the strong law says that the proportion p^N=k/N\htmlClass{c-simu}{\hat p_N} = k/N converges to p\htmlClass{c-exact}{p}: a probability is a proportion, in the limit. In the video, the proportion of heads is 50.28% after 10,000 tosses and 50.005% after a million.

A million tosses (data from the video). Left: the proportion of heads settles on 1/2 (orange). Right: the gap heads - tails wanders and grows like  n (grey band  n): chance does not even out, it gets diluted.
Figure 1.2 A million tosses (data from the video). Left: the proportion of heads settles on 1/2 (orange). Right: the gap heads −- tails wanders and grows like n\sqrt n (grey band ±n\pm\sqrt n): chance does not even out, it gets diluted.
Proof

Chance does not even out. The gap between the number of heads and the number of tails, Dn=2Sn−nD_n = 2S_n - n, has mean zero and variance nn: it does not tend to 0, it typically grows like n\sqrt n (in the video, it is +94 after a million tosses). By the central limit theorem (Section 1.5), P(∣Dn∣>cn)→2(1−Φ(c))>0\mathbb{P}(|D_n| > c\sqrt n) \to 2(1 - \Phi(c)) > 0. But Dn/n→0D_n/n \to 0: divided by nn, the gap is crushed and the proportion converges. The “gambler’s fallacy”, the belief that after a run of tails heads is “due”, confuses these two scales: the coin has no memory; deviations are not corrected, they are diluted (Tversky and Kahneman 1974).

1.2.4 Simulating on a computer#

A computer does not toss coins: it computes a sequence of numbers u1,u2,⋯∈[0,1)u_1, u_2, \dots \in [0, 1) by a deterministic recursion, whose statistical properties imitate those of a uniform sample. NumPy uses the PCG64 algorithm (O’Neill 2014): np.random.default_rng(seed) creates a generator, and the same seed gives back the same sequence. The code from the video, run here:

rng = np.random.default_rng(2)
faces = rng.random(1_000_000) < 0.5
print(faces.mean())
0.500047

Everything else is built from the uniform distribution. The basic tool is the inversion of the cumulative distribution function.

Theorem 1.3Inversion method#

Let FF be a cumulative distribution function and F−1(u)=inf⁡{x∈R:F(x)≥u}F^{-1}(u) = \inf\{x \in \mathbb{R}: F(x) \ge u\} its generalised inverse. If UU is uniformly distributed on (0,1)(0, 1), then F−1(U)F^{-1}(U) has cumulative distribution function FF.

Proof

FF is non-decreasing and right-continuous, so the set {x:F(x)≥u}\{x : F(x) \ge u\} is a closed interval [F−1(u),+∞)[F^{-1}(u), +\infty). Hence F−1(u)≤x  ⟺  u≤F(x)F^{-1}(u) \le x \iff u \le F(x), and P(F−1(U)≤x)=P(U≤F(x))=F(x)\mathbb{P}(F^{-1}(U) \le x) = \mathbb{P}(U \le F(x)) = F(x).

Example 1.1Exponential claim sizes#

For the exponential distribution with mean mm, F(x)=1−e−x/mF(x) = 1 - e^{-x/m} and F−1(u)=−mln⁡(1−u)F^{-1}(u) = -m\ln(1-u). These are the samples we will use in the next chapter for the insurer’s “twin”: two different distributions obtained from the same uniforms. For the normal distribution, NumPy uses an algorithm faster than inversion (rng.standard_normal).

1.3 An area can be counted#

Let U=(U1,U2)U = (U_1, U_2) be uniform on the square [0,1]2[0,1]^2. For every measurable subset AA of the square, P(U∈A)=area⁡(A)\mathbb{P}(U \in A) = \operatorname{area}(A). With the quarter disc A={x2+y2≤1}A = \{x^2 + y^2 \le 1\}, of area π/4\pi/4: π4=P(U12+U22≤1)=E[1{U12+U22≤1}],π^n=4kn →n→∞a.s. π, \htmlClass{c-exact}{\frac{\pi}{4}} = \mathbb{P}(U_1^2 + U_2^2 \le 1) = \mathbb{E}\big[\mathbf{1}_{\{U_1^2 + U_2^2 \le 1\}}\big], \qquad \htmlClass{c-simu}{\hat\pi_n} = \frac{4k}{n}\ \xrightarrow[n\to\infty]{\text{a.s.}}\ \htmlClass{c-exact}{\pi}, where kk is the number of points, out of nn, that land in the quarter disc. This is the strong law of large numbers applied to an indicator: an area can be counted.

The 3,200 darts of the video (left): in blue, those in the quarter disc. Right: the estimate 4k/n as a function of the number of points (logarithmic scale) closes in on the exact value π (orange), more and more slowly.
Figure 1.3 The 3,200 darts of the video (left): in blue, those in the quarter disc. Right: the estimate 4k/n as a function of the number of points (logarithmic scale) closes in on the exact value π\pi (orange), more and more slowly.

Of the video’s 3,200 darts, 1,582 land below the diagonal (49.4%, for an area of ½) and 2,505 in the quarter disc: π^=\htmlClass{c-simu}{\hat\pi} = 3.131. With 10410^4, 10610^6 and 10810^8 points, the estimate is 3.1256, 3.1405 and 3.1415: each digit costs about a hundred times more points than the previous one. The reason is given in Section 1.5.

More generally, every integral over the unit cube is an expected value: ∫[0,1]dg(x) dx=E[g(U)]\int_{[0,1]^d} g(x)\,dx = \mathbb{E}[g(U)] with UU uniform on [0,1]d[0,1]^d. This is the starting point of Monte Carlo numerical integration.

Example 1.2Buffon’s needle#

Buffon poses the following problem in 1733, and publishes it in 1777 (Buffon 1777): a needle of length ℓ\ell falls at random on a plank floor whose cracks are ℓ\ell apart; what is the probability that it crosses a crack? Let XX be the distance from its centre to the nearest crack, uniform on [0,ℓ/2][0, \ell/2], and Θ\Theta its angle with the cracks, uniform on [0,π/2][0, \pi/2], the two being independent. The needle crosses a crack if and only if X≤ℓ2sin⁡ΘX \le \frac{\ell}{2}\sin\Theta, hence P(crossing)=∫0π/2ℓsin⁡θ/2ℓ/2 dθπ/2=2π. \mathbb{P}(\text{crossing}) = \int_0^{\pi/2} \frac{\ell \sin\theta / 2}{\ell / 2}\,\frac{d\theta}{\pi/2} = \frac{2}{\pi}. Laplace turns the question around in 1812 (Laplace 1812): drop nn needles, count the kk crossings, and 2n/k2n/k estimates π\pi. (A famous experiment of 1901 claimed six correct decimal places with 3,408 needles: a result almost certainly obtained by stopping at the right moment, which is exactly what a confidence interval forbids.)

1.4 An expected value is an average#

1.4.1 The Monte Carlo estimator#

Definition 1.2Monte Carlo estimator#

Let XX be a random variable with values in Rd\mathbb{R}^d, f:Rd→Rf : \mathbb{R}^d \to \mathbb{R} measurable with E∣f(X)∣<∞\mathbb{E}|f(X)| < \infty, and I=E[f(X)]I = \mathbb{E}[f(X)]. For a sample X1,…,XNX_1, \dots, X_N with the same distribution as XX, the Monte Carlo estimator is I^N=1N∑i=1Nf(Xi)  ≈  E[f(X)]. \htmlClass{c-simu}{\hat I_N} = \frac1N \sum_{i=1}^{N} f(\htmlClass{c-simu}{X_i}) \;\approx\; \htmlClass{c-exact}{\mathbb{E}[f(X)]} .

This is the formula from the video, read symbol by symbol: XX is the outcome of chance (the die, the coin, the price of a share tomorrow), ff is what we look at in that outcome (the number showing, a gain, a loss), E\mathbb{E} is the long-run average we are after, X1,…,XNX_1, \dots, X_N are the computer’s NN samples; we add them up and divide by NN. The average we want is roughly the average of what we observe by simulating.

Proposition 1.2Properties of the estimator#
  1. I^N\hat I_N is unbiased: E[I^N]=I\mathbb{E}[\hat I_N] = I; it is strongly consistent: I^N→I\hat I_N \to I a.s. (Theorem 1.2).
  2. If moreover E[f(X)2]<∞\mathbb{E}[f(X)^2] < \infty and σ2=Var⁡(f(X))\sigma^2 = \operatorname{Var}(f(X)), then Var⁡(I^N)=σ2/N\operatorname{Var}(\hat I_N) = \sigma^2/N: the typical error (the standard deviation of the estimator) is σ/N\sigma/\sqrt N.
Proof

Linearity of expectation, the strong law applied to the f(Xi)f(X_i), which are i.i.d. and integrable, and additivity of the variance for independent variables.

For a fair die, E[X]=(1+⋯+6)/6=3.5\mathbb{E}[X] = (1 + \dots + 6)/6 = 3.5, a value that no roll ever gives; the average of 10,000 simulated rolls is 3.5088.

def monte_carlo(Y):
    """Estimate and half-width of the asymptotic 95% confidence interval, from the samples Y = f(X_i)."""
    Y = np.asarray(Y, dtype=float)
    return Y.mean(), 1.96 * Y.std(ddof=1) / np.sqrt(len(Y))

1.4.2 Finance case: the call option#

A European call option (a call for short) with strike KK and maturity TT gives the right, but not the obligation, to buy the share at time TT at the price KK. Its payoff at maturity is (ST−K)+=max⁡(ST−K,0)(S_T - K)^+ = \max(S_T - K, 0). Arbitrage pricing theory (see the stochastic calculus course) shows that its price today is the expected value of the discounted payoff under the risk-neutral probability Q\mathbb Q: C=e−rT EQ[(ST−K)+]. \htmlClass{c-exact}{C} = e^{-rT}\, \mathbb{E}_{\mathbb Q}\big[(S_T - K)^+\big] . In the Black–Scholes model (Black and Scholes 1973; Merton 1973), the price follows a geometric Brownian motion and, under Q\mathbb Q, ST=S0exp⁡ ⁣((r−σ2/2)T+σT Z)S_T = S_0 \exp\!\big((r - \sigma^2/2)T + \sigma\sqrt T\, Z\big) with Z∼N(0,1)Z \sim \mathcal{N}(0, 1), where rr is the risk-free rate and σ\sigma the volatility (the annual standard deviation of returns). The price is an expected value: it can be simulated (Boyle 1977). For this simple case, we also know the exact value, which will serve as the judge.

Lemma 1.1Call option on a lognormal variable#

If W∼N(m,v2)W \sim \mathcal{N}(m, v^2) with v>0v > 0 and K>0K > 0, then E[(eW−K)+]=em+v2/2 Φ(d1)−K Φ(d1−v),d1=m−ln⁡K+v2v. \mathbb{E}\big[(e^{W} - K)^+\big] = e^{m + v^2/2}\,\Phi(d_1) - K\,\Phi(d_1 - v), \qquad d_1 = \frac{m - \ln K + v^2}{v}.

Proof

(eW−K)+=eW1{W>ln⁡K}−K1{W>ln⁡K}(e^W - K)^+ = e^W \mathbf{1}_{\{W > \ln K\}} - K \mathbf{1}_{\{W > \ln K\}}. On the one hand, KP(W>ln⁡K)=KΦ((m−ln⁡K)/v)=KΦ(d1−v)K\mathbb{P}(W > \ln K) = K\Phi\big((m - \ln K)/v\big) = K\Phi(d_1 - v). On the other hand, writing φm,v\varphi_{m,v} for the density of N(m,v2)\mathcal{N}(m, v^2), completing the square shows that ewφm,v(w)=em+v2/2 φm+v2,v(w)e^{w}\varphi_{m,v}(w) = e^{m + v^2/2}\,\varphi_{m+v^2, v}(w); hence E[eW1{W>ln⁡K}]=em+v2/2 P(W′>ln⁡K)\mathbb{E}[e^W \mathbf{1}_{\{W > \ln K\}}] = e^{m + v^2/2}\,\mathbb{P}(W' > \ln K) with W′∼N(m+v2,v2)W' \sim \mathcal{N}(m + v^2, v^2), that is, em+v2/2Φ(d1)e^{m+v^2/2}\Phi(d_1).

Corollary 1.1Black–Scholes formula#

With m=ln⁡S0+(r−σ2/2)Tm = \ln S_0 + (r - \sigma^2/2)T and v=σTv = \sigma\sqrt T, we obtain C=S0 Φ(d1)−Ke−rT Φ(d2)C = S_0\,\Phi(d_1) - K e^{-rT}\,\Phi(d_2), with d1=ln⁡(S0/K)+(r+σ2/2)TσTd_1 = \frac{\ln(S_0/K) + (r + \sigma^2/2)T}{\sigma\sqrt T} and d2=d1−σTd_2 = d_1 - \sigma\sqrt T.

For S0=K=100S_0 = K = 100, r=5%r = 5\%, σ=20%\sigma = 20\%, T=1T = 1 year, the judge is C=\htmlClass{c-exact}{C} = €10.4506. The following code simulates a million futures:

S0, K, r, sig, T = 100.0, 100.0, 0.05, 0.20, 1.0
rng = np.random.default_rng(1973)
Z = rng.standard_normal(1_000_000)
ST = S0 * np.exp((r - sig**2 / 2) * T + sig * np.sqrt(T) * Z)
prix, demi = monte_carlo(np.exp(-r * T) * np.maximum(ST - K, 0))
print(f"Monte Carlo: {prix:.3f} ± {demi:.3f}   |   Black–Scholes: {bs_call(S0, K, r, sig, T):.4f}")
Monte Carlo: 10.426 ± 0.029   |   Black–Scholes: 10.4506
Estimated price of the call option as a function of the number of simulated futures (data from the video), with its 95% confidence band (pale blue), and the Black–Scholes price (orange).
Figure 1.4 Estimated price of the call option as a function of the number of simulated futures (data from the video), with its 95% confidence band (pale blue), and the Black–Scholes price (orange).

In the video, a million futures give €10.46 with a typical error of €0.015, against €10.45 for Black–Scholes. The point of simulation is not to recover a known formula: it is to keep working when there is no formula left (options on averages, on several assets, stochastic volatility models). The judge serves to validate the method in the case where it exists.

1.4.3 Insurance case: ruin#

The Cramér–Lundberg model describes an insurer’s reserve: U(t)=u+c t−∑j=1N(t)Xj, U(t) = u + c\,t - \sum_{j=1}^{N(t)} X_j , where uu is the initial reserve, cc the premium rate, NN a Poisson process with intensity λ\lambda (the claim times) and XjX_j i.i.d. claim sizes with mean mm, independent of NN. The premium includes a safety loading θ>0\theta > 0: c=(1+θ)λmc = (1 + \theta)\lambda m. The ruin probability is ψ(u)=P(∃t≥0:U(t)<0)\psi(u) = \mathbb{P}(\exists t \ge 0 : U(t) < 0), once again the expected value of an indicator.

Proposition 1.3Ruin with exponential claims#

If the claim sizes are exponential with mean mm, then ψ(u)=11+θexp⁡ ⁣(−θ u(1+θ) m)\htmlClass{c-exact}{\psi(u)} = \dfrac{1}{1+\theta}\exp\!\Big(-\dfrac{\theta\, u}{(1+\theta)\,m}\Big).

The proof (by a renewal argument, or with Lundberg’s exponential martingale) is classical (Asmussen and Albrecher 2010, chap. IV). It provides the orange judge of the video.

To simulate, note that the reserve can only fall below zero at the moment of a claim. Writing EjE_j for the times between claims (exponential with parameter λ\lambda), the reserve just after the kk-th claim is the random walk Rk=u+∑j≤k(cEj−Xj)R_k = u + \sum_{j \le k}(c E_j - X_j), and ruin is the event {min⁡kRk<0}\{\min_k R_k < 0\}. We truncate the horizon at n=1,000n = 1{,}000 claims.

def ruine(rng, N, u, theta, n_sinistres=1000):
    """Cramér–Lundberg (λ = 1, Exp claims with mean 1, c = 1 + θ): ruin before n_sinistres claims, and final reserve."""
    R = np.full(N, float(u))
    ruinee = np.zeros(N, dtype=bool)
    for _ in range(n_sinistres):
        R += (1 + theta) * rng.exponential(1.0, N) - rng.exponential(1.0, N)
        ruinee |= R < 0
    return ruinee, R

ruinee, R = ruine(np.random.default_rng(1903), 10_000, u=17, theta=0.2)
p, demi = monte_carlo(ruinee)
print(f"simulated ruin: {p:.4f} ± {demi:.4f}   |   exact: {ruine_exacte(17, 0.2):.4f}")
simulated ruin: 0.0501 ± 0.0043   |   exact: 0.0490

These are exactly the samples used in the video (same seed, same order): 501 ruins out of 10,000, that is 5.01% ± 0.43%, while the exact value is 4.90%.

Proof

The truncation bias can be measured. The estimator targets ψn(u)=P(ruin before n claims)\psi_n(u) = \mathbb{P}(\text{ruin before } n \text{ claims}), not ψ(u)\psi(u). By the strong Markov property, the difference is ψ(u)−ψn(u)=E[ψ(Rn) 1{no ruin before n}]\psi(u) - \psi_n(u) = \mathbb{E}\big[\psi(R_n)\, \mathbf{1}_{\{\text{no ruin before } n\}}\big], which we estimate on the same paths thanks to the exact formula for ψ\psi: we find about 2.4×10−82.4 \times 10^{-8}, negligible compared with the statistical error. Predict, simulate, verify: even the approximations of the algorithm can be checked.

Forty futures of an insurer (u = 17,  = 20\,\%, data from the video): the reserve rises with the premiums and drops at each claim; the path that falls below zero is in red.
Figure 1.5 Forty futures of an insurer (u=17u = 17, θ=20 %\theta = 20\,\%, data from the video): the reserve rises with the premiums and drops at each claim; the path that falls below zero is in red.

1.5 How many samples?#

1.5.1 The result is itself random#

Three estimates of π\pi with 1,000 points each give 3.140, 3.204 and 3.128: the estimator is a random variable. Its distribution describes the error. The weak law gave a bound; the central limit theorem gives its shape.

Theorem 1.4Central limit theorem, Lindeberg–Lévy#

Let Y1,Y2,…Y_1, Y_2, \dots be a sample with E[Y12]<∞\mathbb{E}[Y_1^2] < \infty, μ=E[Y1]\mu = \mathbb{E}[Y_1] and σ2=Var⁡(Y1)>0\sigma^2 = \operatorname{Var}(Y_1) > 0. Then N YˉN−μσ→N→∞LN(0,1),that isP(N YˉN−μσ≤x)→Φ(x) for all x∈R. \sqrt N\,\frac{\bar Y_N - \mu}{\sigma} \xrightarrow[N\to\infty]{\mathcal{L}}\mathcal{N}(0, 1), \qquad\text{that is}\qquad \mathbb{P}\Big(\sqrt N\,\frac{\bar Y_N - \mu}{\sigma} \le x\Big) \to \Phi(x) \text{ for all } x \in \mathbb{R}.

Proof

Let Zi=(Yi−μ)/σZ_i = (Y_i - \mu)/\sigma, the standardised variables, and ϕ(t)=E[eitZ1]\phi(t) = \mathbb{E}[e^{itZ_1}]. Since E[Z12]<∞\mathbb{E}[Z_1^2] < \infty, we may differentiate twice under the expectation (dominated convergence): ϕ\phi is of class C2C^2, with ϕ(0)=1\phi(0) = 1, ϕ′(0)=iE[Z1]=0\phi'(0) = i\mathbb{E}[Z_1] = 0, ϕ′′(0)=−E[Z12]=−1\phi''(0) = -\mathbb{E}[Z_1^2] = -1, hence ϕ(t)=1−t2/2+o(t2)\phi(t) = 1 - t^2/2 + o(t^2). By independence, the characteristic function of TN=N−1/2∑i≤NZiT_N = N^{-1/2}\sum_{i \le N} Z_i is ϕ(t/N)N\phi(t/\sqrt N)^N.

Lemma. If a1,…,aN,b1,…,bNa_1, \dots, a_N, b_1, \dots, b_N are complex numbers of modulus at most 1, then ∣∏ai−∏bi∣≤∑∣ai−bi∣|\prod a_i - \prod b_i| \le \sum |a_i - b_i| (by induction on NN: ∏i≤Nai−∏i≤Nbi=aN(∏i<Nai−∏i<Nbi)+(aN−bN)∏i<Nbi\prod_{i \le N} a_i - \prod_{i \le N} b_i = a_N(\prod_{i<N} a_i - \prod_{i<N} b_i) + (a_N - b_N)\prod_{i<N} b_i).

For fixed tt and N≥t2/2N \ge t^2/2, apply the lemma to ai=ϕ(t/N)a_i = \phi(t/\sqrt N) and bi=1−t2/(2N)b_i = 1 - t^2/(2N): ∣ϕ(t/N)N−(1−t22N)N∣≤N ∣ϕ(t/N)−1+t22N∣=N o(t2/N)→N→∞0. \Big|\phi(t/\sqrt N)^N - \big(1 - \tfrac{t^2}{2N}\big)^N\Big| \le N\,\Big|\phi(t/\sqrt N) - 1 + \tfrac{t^2}{2N}\Big| = N\, o\big(t^2/N\big) \xrightarrow[N\to\infty]{} 0 . Since (1−t2/(2N))N→e−t2/2(1 - t^2/(2N))^N \to e^{-t^2/2}, the characteristic function of TNT_N converges at every point to that of N(0,1)\mathcal{N}(0,1), and Lévy’s continuity theorem (Durrett 2019, sect. 3.3) gives convergence in distribution.

2,000 estimates of π for n = 100, 400 and 1,600 points (data from the video): each time n is multiplied by 4, the bell curve becomes twice as narrow. In orange, the normal densities predicted by the central limit theorem.
Figure 1.6 2,000 estimates of π\pi for n=100n = 100, 400 and 1,600 points (data from the video): each time nn is multiplied by 4, the bell curve becomes twice as narrow. In orange, the normal densities predicted by the central limit theorem.

For the estimator of π\pi, one sample is 41{U12+U22≤1}4\mathbf{1}_{\{U_1^2 + U_2^2 \le 1\}}, with standard deviation σπ=4p(1−p)=\sigma_\pi = 4\sqrt{p(1-p)} = 1.642 where p=π/4p = \pi/4. The standard deviations measured over 2,000 repetitions in the video are:

points nn measured standard deviation predicted σπ/n\sigma_\pi/\sqrt n
100 0.1637 0.1642
400 0.0808 0.0821
1,600 0.0412 0.0411
10,000 0.0164 0.0164

Four times as many points halve the error; a hundred times as many points gain one digit. This is the golden rule of the method, and the reason why the digits of π\pi arrived so slowly in Section 1.3.

1.5.2 The confidence interval#

In practice σ\sigma is unknown: we replace it by the sample standard deviation, defined by σ^N2=1N−1∑i≤N(Yi−YˉN)2\hat\sigma_N^2 = \frac{1}{N-1}\sum_{i \le N}(Y_i - \bar Y_N)^2, which converges almost surely to σ2\sigma^2 (strong law applied to the YiY_i and to the Yi2Y_i^2). The substitution is justified by the following lemma.

Lemma 1.2Slutsky#

If TN→TT_N \to T in distribution and AN→aA_N \to a in probability (aa a constant), then ANTN→aTA_N T_N \to aT in distribution.

Theorem 1.5Asymptotic confidence interval#

Under the assumptions of Theorem 1.4, for α∈(0,1)\alpha \in (0, 1) and q=Φ−1(1−α/2)q = \Phi^{-1}(1 - \alpha/2), P(μ∈[YˉN−q σ^NN, YˉN+q σ^NN])→N→∞1−α. \mathbb{P}\Big(\mu \in \Big[\htmlClass{c-simu}{\bar Y_N} - q\,\frac{\hat\sigma_N}{\sqrt N},\ \htmlClass{c-simu}{\bar Y_N} + q\,\frac{\hat\sigma_N}{\sqrt N}\Big]\Big) \xrightarrow[N\to\infty]{} 1 - \alpha . For α=5%\alpha = 5\%, q=1.96q = 1.96: this is the interval “estimate ± 1.96 σ^/N\pm\, 1.96\,\hat\sigma/\sqrt N”.

Proof

σ^N→σ>0\hat\sigma_N \to \sigma > 0 a.s., so σ/σ^N→1\sigma/\hat\sigma_N \to 1 in probability; by Lemma 1.2 and Theorem 1.4, TN=N(YˉN−μ)/σ^N→N(0,1)T_N = \sqrt N(\bar Y_N - \mu)/\hat\sigma_N \to \mathcal{N}(0,1) in distribution. The event in question is {∣TN∣≤q}\{|T_N| \le q\}; the limit distribution puts no mass on the boundary {±q}\{\pm q\}, so P(∣TN∣≤q)→Φ(q)−Φ(−q)=1−α\mathbb{P}(|T_N| \le q) \to \Phi(q) - \Phi(-q) = 1 - \alpha.

A hundred 95% confidence intervals for π, each with 1,000 points (data from the video): in blue those that contain π (orange), in red those that miss it.
Figure 1.7 A hundred 95% confidence intervals for π\pi, each with 1,000 points (data from the video): in blue those that contain π\pi (orange), in red those that miss it.

1.5.3 The answer to Ulam#

For a proportion, σ2=p(1−p)≤1/4\sigma^2 = p(1-p) \le 1/4. With NN games, the half-width of the 95% interval is therefore at most 1.96×0.5/N1.96 \times 0.5/\sqrt N: with a hundred games, Ulam would have known his chance to within 9.8 percentage points, in the worst case. To get down to ε=1%\varepsilon = 1\%, we need N≥(1.96×0.50.01)2=9,604 games. N \ge \Big(\frac{1.96 \times 0.5}{0.01}\Big)^2 = 9{,}604 \text{ games.} Dividing the error by ten costs a hundred times more samples: the price of a digit.

Proof

A non-asymptotic guarantee. Theorem 1.5 is asymptotic. For variables bounded in [a,b][a, b], Hoeffding’s inequality (Hoeffding 1963) gives a guarantee that holds for every NN: P(∣YˉN−μ∣≥ε)≤2exp⁡(−2Nε2/(b−a)2)\mathbb{P}(|\bar Y_N - \mu| \ge \varepsilon) \le 2\exp\big(-2N\varepsilon^2/(b-a)^2\big). For Ulam (b−a=1b - a = 1), an error of at most 1% with probability at least 95% is guaranteed as soon as N≥ln⁡(40)/(2×0.012)N \ge \ln(40)/(2 \times 0.01^2), that is 18,445 games: the price of certainty is about twice the asymptotic price.

1.6 Why finance loves it#

1.6.1 Dimension#

To compute an integral over [0,1]d[0,1]^d, one can also use a grid: nn points per axis, N=ndN = n^d points in all. For a function of class C2C^2, the midpoint rule has an error of O(n−2)=O(N−2/d)O(n^{-2}) = O(N^{-2/d}) (second-order Taylor expansion in each cell: the first-order term cancels out by symmetry). Monte Carlo has an error of order σN−1/2\sigma N^{-1/2}, regardless of dd. The grid wins in dimension 1, 2 or 3; it loses as soon as d>4d > 4, and it becomes impractical well before that: ten points per axis in dimension 50 make 105010^{50} points, the order of magnitude of the number of atoms in the Earth. This is the curse of dimensionality.

dimension dd 1 2 3 10 50
points in a grid with 10 points per axis 10 100 1,000 101010^{10} 105010^{50}
Monte Carlo error for NN samples σ/N\sigma/\sqrt N σ/N\sigma/\sqrt N σ/N\sigma/\sqrt N σ/N\sigma/\sqrt N σ/N\sigma/\sqrt N

In finance, the dimension is the number of random quantities in a scenario: a path of 48 steps has 48 dimensions, a portfolio of 50 shares over 12 months has 600. This is the real reason for the method’s success. The constant σ\sigma, on the other hand, can depend on dd: that is the subject of session 2 (reducing it) and of challenge 2 of the practical.

1.6.2 The Achilles’ heel: the rare event#

For a small probability pp, the relative error of p^N\hat p_N is σ/Np=1−pNp≈1Np, \frac{\sigma/\sqrt N}{p} = \sqrt{\frac{1-p}{Np}} \approx \frac{1}{\sqrt{Np}} , which depends only on the number NpNp of events observed. For a relative error of 10%, about a hundred events must be observed, hence N≈100/pN \approx 100/p samples. Picture an insurer with enough reserves for ruin to happen, someday, only about once in two hundred: in the model of Section 1.4, an initial reserve u=31u = 31 gives an exact ruin probability of 0.475%. That is the order of magnitude of the Solvency II directive, which calibrates an insurer’s capital so that its ruin within one year has only a 0.5% chance of happening (Parlement européen et Conseil 2009); but these are two different probabilities: the directive looks at a single year, the model at the whole future. With 100 simulations, no ruin at all is observed with probability (1−p)100≈(1 - p)^{100} \approx 0.62. With 1,000 simulations, the video observes 6: 0.6% ± 0.5%, which tells us almost nothing; it takes a hundred thousand to obtain 0.49% ± 0.04%. Session 3 will teach us to aim where it counts.

1.6.3 Historical landmarks#

Fermi was already practising statistical sampling in Rome in the early 1930s, without publishing; Ulam does not invent the idea, he marries it to the computer.

On 11 March 1947, von Neumann sends Robert Richtmyer, at Los Alamos, a plan for a statistical computation of neutron diffusion (Eckhardt 1987). The first simulations run on the ENIAC in the spring of 1948; Klára Dán von Neumann writes most of the programs (Haigh et al. 2014). The first paper, “The Monte Carlo Method”, appears in 1949 (Metropolis and Ulam 1949). In finance, Phelim Boyle introduces simulation into option pricing in 1977 (Boyle 1977).

1.7 What to remember#

  1. A probability is a proportion: p^N=k/N→p\htmlClass{c-simu}{\hat p_N} = k/N \to \htmlClass{c-exact}{p} almost surely (strong law of large numbers); chance does not even out, it gets diluted.
  2. An expected value is an average, and an average can be simulated: I^N=1N∑f(Xi)≈E[f(X)]\htmlClass{c-simu}{\hat I_N} = \frac1N\sum f(\htmlClass{c-simu}{X_i}) \approx \htmlClass{c-exact}{\mathbb{E}[f(X)]}, unbiased, with variance σ2/N\sigma^2/N.
  3. The error shrinks like σ/N\sigma/\sqrt N: one digit costs a hundred times more samples; always report the estimate with its interval ±1.96 σ^/N\pm 1.96\,\hat\sigma/\sqrt N, which contains the true value 95 times out of a hundred.

The program from the video, in seven lines, run here:

import numpy as np
rng = np.random.default_rng(21)
x, y = rng.random(1_000_000), rng.random(1_000_000)
dedans = (x**2 + y**2 <= 1)
pi_hat = 4 * dedans.mean()
erreur = 1.96 * 4 * dedans.std() / 1000
print(round(pi_hat, 4), '±', round(erreur, 4))
3.1407 ± 0.0032

Practice#

  1. Show that the Buffon–Laplace estimator 2n/k2n/k is biased (Jensen’s inequality), then compute its typical error by the delta method. Compare it, for the same number of samples, with the darts estimator.
  2. We estimate p=P(A)p = \mathbb{P}(A) with NN samples. How many are needed for a relative error of 10% (at 95%) if p=10−2p = 10^{-2}? If p=10−5p = 10^{-5}?
  3. Write the algorithm that simulates ruin in continuous time (claim times included) and check that it gives the same probability as the random walk RkR_k. Why?
  4. Show that for YiY_i with values in {0,1}\{0, 1\}, σ^N2=NN−1p^N(1−p^N)\hat\sigma_N^2 = \frac{N}{N-1}\hat p_N(1 - \hat p_N).

Going further#

  • Rate in the central limit theorem. The Berry–Esseen inequality bounds the distance between the distribution of the normalised error and N(0,1)\mathcal{N}(0,1) by C E∣Y−μ∣3/(σ3N)C\,\mathbb{E}|Y - \mu|^3/(\sigma^3\sqrt N): the less skewed the distribution of YY, the faster the bell curve is reached (Durrett 2019).
  • Intervals for a proportion. When NpNp is small, the Wald interval p^±1.96p^(1−p^)/N\hat p \pm 1.96\sqrt{\hat p(1 - \hat p)/N} has poor coverage (it is [0,0][0, 0] when no success is observed); the Wilson and Clopper–Pearson intervals remedy this.
  • Quasi-Monte Carlo. Replacing the random samples by low-discrepancy sequences (Sobol, Halton) gives an error close to N−1N^{-1} for smooth integrands, at the cost of a more delicate error estimate (Glasserman 2004, chap. 5).
  • Reading. Glasserman (2004) (chap. 1 and 2) for finance, Asmussen and Glynn (2007) for the general theory, Lapeyre et al. (1998) in French, Owen (2013) in open access.

References

  1. Asmussen, Søren, and Hansjörg Albrecher. 2010. Ruin Probabilities. 2nd edn. World Scientific.
  2. Asmussen, Søren, and Peter W. Glynn. 2007. Stochastic Simulation: Algorithms and Analysis. Springer.
  3. Black, Fischer, and Myron Scholes. 1973. ‘The Pricing of Options and Corporate Liabilities’. Journal of Political Economy 81 (3): 637–54.
  4. Boyle, Phelim P. 1977. ‘Options: A Monte Carlo Approach’. Journal of Financial Economics 4 (3): 323–38.
  5. Buffon, Georges-Louis Leclerc. 1777. Essai d’arithmétique Morale. IV. Supplément à l’histoire Naturelle. Imprimerie royale.
  6. Durrett, Rick. 2019. Probability: Theory and Examples. 5th edn. Cambridge University Press.
  7. Eckhardt, Roger. 1987. ‘Stan Ulam, John von Neumann, and the Monte Carlo Method’. Los Alamos Science 15: 131–37.
  8. Etemadi, Nasrollah. 1981. ‘An Elementary Proof of the Strong Law of Large Numbers’. Zeitschrift Für Wahrscheinlichkeitstheorie Und Verwandte Gebiete 55: 119–22.
  9. Glasserman, Paul. 2004. Monte Carlo Methods in Financial Engineering. Springer.
  10. Haigh, Thomas, Mark Priestley, and Crispin Rope. 2014. ‘Los Alamos Bets on ENIAC: Nuclear Monte Carlo Simulations, 1947–1948’. IEEE Annals of the History of Computing 36 (3): 42–63.
  11. Hoeffding, Wassily. 1963. ‘Probability Inequalities for Sums of Bounded Random Variables’. Journal of the American Statistical Association 58 (301): 13–30.
  12. Hoekstra, Rink, Richard D. Morey, Jeffrey N. Rouder, and Eric-Jan Wagenmakers. 2014. ‘Robust Misinterpretation of Confidence Intervals’. Psychonomic Bulletin & Review 21 (5): 1157–64.
  13. Lapeyre, Bernard, Étienne Pardoux, and Rémi Sentis. 1998. Méthodes de Monte-Carlo Pour Les Équations de Transport Et de Diffusion. Vol. 29. Mathématiques Et Applications. Springer.
  14. Laplace, Pierre-Simon. 1812. Théorie Analytique Des Probabilités. Courcier.
  15. Merton, Robert C. 1973. ‘Theory of Rational Option Pricing’. Bell Journal of Economics and Management Science 4 (1): 141–83.
  16. Metropolis, Nicholas. 1987. ‘The Beginning of the Monte Carlo Method’. Los Alamos Science 15: 125–30.
  17. Metropolis, Nicholas, and Stanislaw Ulam. 1949. ‘The Monte Carlo Method’. Journal of the American Statistical Association 44 (247): 335–41. https://doi.org/10.1080/01621459.1949.10483310.
  18. O’Neill, Melissa E. 2014. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. HMC-CS-2014-0905. Harvey Mudd College.
  19. Owen, Art B. 2013. Monte Carlo Theory, Methods and Examples.
  20. Parlement européen et Conseil. 2009. Directive 2009/138/CE Sur l’accès Aux Activités de l’assurance Et de La Réassurance Et Leur Exercice (Solvabilité II), Article 101. Journal officiel de l’Union européenne, L 335.
  21. Tversky, Amos, and Daniel Kahneman. 1974. ‘Judgment Under Uncertainty: Heuristics and Biases’. Science 185 (4157): 1124–31.
Esc

    Type to search the course notes, the transcripts and the practicals.

    ↑ ↓ selectEnter open

    Keyboard shortcuts

    Everywhere

    / Ctrl K
    Search the whole course
    g h
    Home
    g 1…7
    Go to a session
    n p
    Next, previous session
    ?
    This help

    Video

    Space k
    Play, pause
    j l
    Back, forward 10 s
    ← →
    Back, forward 5 s
    [ ]
    Previous, next chapter
    c
    Subtitles
    f
    Full screen
    m
    Mute
    < >
    Speed
    0…9
    Jump to 0%, 10%… 90%

    Practicals in the browser

    Shift Enter
    Run the cell
    Ctrl Enter
    Run without moving on