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

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Monte Carlo Methods in Financial Engineering (Paul Glasserman, 2004) foundational - Ch. 1 - Ch. 1: Monte Carlo principles - unbiased estimation, standard error, confidence intervals, and the \(1/\sqrt N\) rate.
Probability: Theory and Examples (Rick Durrett, 5th ed.) current - Ch. 2 - Law of large numbers and the central limit theorem underpinning convergence and interval coverage.

← 13.1 Next: 13.3 →