Phase 13 - Lesson 13.2

Monte Carlo Estimation and Error Analysis

Unbiasedness, the \(1/\sqrt{N}\) standard error, and honest confidence intervals.

⏱ 50 min● Intermediate🔗 Prereqs: 13.1, Central Limit Theorem

↖ Phase 13 hub

Builds on: 13.1 built the samplers; here we turn samples into estimates with error bars.

Learning Objectives

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

Define the Monte Carlo estimator and prove it is unbiased for the target expectation.
Derive the \(1/\sqrt{N}\) convergence of the standard error and interpret its dimension-independence.
Construct and interpret a Monte Carlo confidence interval from the sample standard deviation.
Compute the number of paths needed to reach a target error tolerance.
Estimate a quantity (e.g. an option price or \(\pi\)) and report it with a valid error bar.

Key Vocabulary

Monte Carlo estimator: The sample average \(\hat\theta_N=\tfrac1N\sum_{i=1}^N Y_i\) of i.i.d. draws \(Y_i\) with \(\E[Y_i]=\theta\).

Unbiasedness: An estimator with \(\E[\hat\theta_N]=\theta\) for every \(N\); the sample mean is unbiased by linearity of expectation.

Standard error: The standard deviation of the estimator, \(\mathrm{SE}=\sigma/\sqrt{N}\), estimated by \(s/\sqrt{N}\).

Confidence interval: A random interval \(\hat\theta_N\pm z\,s/\sqrt{N}\) that covers \(\theta\) with the stated probability as \(N\to\infty\).

Sample standard deviation: The estimate \(s\) of \(\sigma\) from the data, using the \(N-1\) (Bessel) denominator.

Root-mean-square error: The overall accuracy \(\sqrt{\E[(\hat\theta_N-\theta)^2]}\), which for an unbiased estimator equals the standard error.

Intuition & Motivation

Intuition

Monte Carlo answers ‘what is \(\E[Y]\)?’ by the most obvious device imaginable: average many samples. The two facts that make it trustworthy are (1) the average is unbiased - centered on the true value for any \(N\) - and (2) its error shrinks like \(1/\sqrt{N}\), independent of dimension. That slow \(\sqrt{N}\) rate is the price and the gift: quadrupling work halves the error, but a 20-dimensional integral costs no more than a 1-D one. Crucially, Monte Carlo hands you its own error bar - the sample standard deviation over \(\sqrt{N}\) - so you never have to guess how accurate the answer is.

The estimator and unbiasedness

Let \(Y_1,\dots,Y_N\) be i.i.d. copies of \(Y\) with \(\theta=\E[Y]\) and \(\sigma^2=\Var(Y)\lt \infty\). The Monte Carlo estimator is the sample mean:

\[\hat\theta_N=\frac1N\sum_{i=1}^N Y_i,\qquad \E[\hat\theta_N]=\frac1N\sum_{i=1}^N\E[Y_i]=\theta.\] (13.4)

By the strong law of large numbers \(\hat\theta_N\to\theta\) almost surely. Unbiasedness holds for every sample size, not just in the limit - a consequence of linearity of expectation alone.

Variance and the \(1/\sqrt{N}\) standard error

Because the draws are independent, variances add:

\[\Var(\hat\theta_N)=\frac1{N^2}\sum_{i=1}^N\Var(Y_i)=\frac{\sigma^2}{N},\qquad \mathrm{SE}=\frac{\sigma}{\sqrt N}.\] (13.5)

Key Idea

The Monte Carlo error decays as \(\sigma/\sqrt N\). To cut the error in half you must quadruple \(N\). This rate does not depend on the dimension of the underlying random vector - the reason Monte Carlo beats grids in high dimensions.

Confidence intervals

By the CLT, \(\sqrt N(\hat\theta_N-\theta)/\sigma\Rightarrow\Normal(0,1)\). Replacing the unknown \(\sigma\) by the sample standard deviation \(s\) gives an asymptotic \(100(1-\alpha)\%\) interval:

\[\hat\theta_N\ \pm\ z_{1-\alpha/2}\,\frac{s}{\sqrt N},\qquad s^2=\frac1{N-1}\sum_{i=1}^N(Y_i-\hat\theta_N)^2.\] (13.6)

For 95% take \(z\approx1.96\). Report the estimate with this half-width; a Monte Carlo number without an error bar is not a result.

Worked Example - How many paths for a target error?

Suppose \(\sigma\approx8\) (payoff standard deviation) and you want a 95% half-width of \(0.05\).

Set \(1.96\,\sigma/\sqrt N\le0.05\), i.e. \(\sqrt N\ge1.96\cdot8/0.05=313.6\).

So \(N\ge313.6^2\approx98{,}345\); round up to \(N=10^5\).

Halving the tolerance to \(0.025\) quadruples this to \(\approx4\times10^5\) paths - the \(1/\sqrt N\) tax.

Interactive: Monte Carlo the Black–Scholes call with an error bar

Common Mistakes to Avoid

Reporting a Monte Carlo estimate with no error bar; without \(s/\sqrt N\) you cannot tell signal from noise.
Expecting the error to fall like \(1/N\); it falls like \(1/\sqrt N\), so 100× the work buys only 10× the accuracy.
Using the population denominator \(N\) for \(s^2\) on small samples; use the unbiased \(N-1\) (Bessel) correction.
Treating the CLT interval as exact for tiny \(N\) or heavy-tailed payoffs; coverage is only asymptotic and degrades when \(\Var(Y)\) is huge or infinite.

Quant Practitioner Tips

Always print \(\hat\theta_N\pm1.96\,s/\sqrt N\); the half-width tells you when to stop simulating.
The \(1/\sqrt N\) rate is dimension-free - this is why Monte Carlo, not quadrature, prices high-dimensional baskets.
If the payoff variance is large, do not just add paths - reach for variance reduction (next lesson) to shrink \(\sigma\) itself.

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.

Warm-up:
#59 XOR Decryption (4%, tier A) #79 Passcode Derivation (7%, tier A) #102 Triangle Containment (8%, tier A) #54 Poker Hands (9%, tier A)

Applied:
#938 Exhausting a Colour (16%, tier B) #816 Shortest Distance Among Points (17%, tier B) #323 Bitwise-OR Operations on Random In (18%, tier B)

Challenge:
#375 Minimum of Subsequences (41%, tier C) #666 Polymorphic Bacteria (41%, tier C)

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

Knowledge Check

Q1 Easy

The Monte Carlo estimator \(\hat\theta_N=\tfrac1N\sum Y_i\) is unbiased because:

The \(Y_i\) are normal

Linearity gives \(\E[\hat\theta_N]=\theta\) for every \(N\)

It uses the \(N-1\) denominator

The CLT applies

Q2 Medium

To reduce the Monte Carlo standard error by a factor of 3, you should multiply the number of samples by:

\(3\)

\(\sqrt3\)

\(9\)

\(27\)

Q3 Medium

A key advantage of Monte Carlo over grid-based quadrature for high-dimensional integrals is that its error rate:

Improves with dimension

Is exactly zero

Does not depend on the dimension

Falls like \(1/N\)

Practical Exercise

You run \(N=10^4\) simulations of a discounted payoff and obtain sample mean \(\hat\theta=9.41\) and sample standard deviation \(s=8.0\). (a) Give the standard error and a 95% confidence interval. (b) How many paths would you need to shrink the 95% half-width to \(0.02\)?

▶ Show full solution

(a) \(\mathrm{SE}=8.0/\sqrt{10^4}=8.0/100=0.08\).

95% interval: \(9.41\pm1.96\times0.08=9.41\pm0.157\), i.e. \([9.25,\,9.57]\).

(b) Need \(1.96\cdot8/\sqrt N\le0.02\), so \(\sqrt N\ge1.96\cdot8/0.02=784\) and \(N\ge784^2\approx6.15\times10^5\). Round up to about \(6.2\times10^5\) paths - roughly 62× more work for an 8× tighter bar, the \(1/\sqrt N\) penalty in action.

After the reveal, answer for yourself: If instead the payoff had \(s=40\), how would your required \(N\) change, and what would you do about it?

Lesson Summary

The Monte Carlo estimator is the sample mean of i.i.d. payoff draws: unbiased by linearity, convergent by the law of large numbers, with standard error \(\sigma/\sqrt N\) that is independent of dimension. Report every estimate as \(\hat\theta_N\pm1.96\,s/\sqrt N\). Because error falls only as \(1/\sqrt N\), brute force is expensive - motivating the variance-reduction methods of the next lesson.

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: Give the Monte Carlo standard error and its dependence on \(N\) and dimension.
A: \(\mathrm{SE}=\sigma/\sqrt N\), falling like \(1/\sqrt N\) and independent of the problem’s dimension - quadrupling \(N\) halves the error.

Q: Write a 95% Monte Carlo confidence interval.
A: \(\hat\theta_N\pm1.96\,s/\sqrt N\), where \(s\) is the sample standard deviation (Bessel \(N-1\) denominator); valid asymptotically by the CLT.

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

← 13.1 Next: 13.3 →