Monte Carlo simulation — law of large numbers basis: Exercises

This page is a self-test ladder for the parent topic. Work each problem before opening its solution. Levels climb from recognising the machinery to synthesising whole estimators. Every number you'll be asked for is checked in the vault's verify block, so trust the answers.

Reused constants throughout: the standard error $SE = σ_{g} / n$ (spread of the estimate), and for a yes/no (Bernoulli) count, $σ_{g}^{2} = p (1 - p)$ .

Level 1 — Recognition

L1.1

The quantity $θ = \int_{0}^{1} cos (x) d x$ is to be estimated by Monte Carlo. Rewrite $θ$ as an expectation and name the distribution you sample from.

Recall Solution

WHAT we do: match $\int_{0}^{1} g (x) d x$ to the expectation template. WHY: the Uniform $(0, 1)$ density is exactly $1$ on $[0, 1]$ , so $\int_{0}^{1} g (x) d x = \int_{0}^{1} g (x) \cdot 1 d x = E [g (U)], U \sim Unif (0, 1) .$ Here $g (x) = cos x$ , so $θ = E [cos U], U \sim Unif (0, 1) .$ You would draw $U_{1}, \dots, U_{n}$ and average $cos U_{i}$ .

L1.2

A Monte Carlo run gives sample standard deviation $\overset{σ}{^}_{g} = 0.5$ with $n = 2500$ samples. Write the standard error.

Recall Solution

$SE = \frac{σ ^ _{g}}{n} = \frac{0.5}{2500} = \frac{0.5}{50} = 0.01.$ WHY $n$ not $n$ : the variance of the sample mean is $σ_{g}^{2} / n$ ; taking a square root to get a standard deviation (an error in the same units as $θ$ ) introduces the $n$ .

Level 2 — Application

L2.1

You estimate $π$ by the dart method: $X = 1 {U_{1}^{2} + U_{2}^{2} \leq 1}$ , $\overset{π}{^} = 4 \overset{ˉ}{X}_{n}$ . Using $p = π /4 \approx 0.785$ , compute $SE (\overset{π}{^})$ for $n = 10000$ .

Recall Solution

Step 1 — variance of one dart. $X$ is Bernoulli $(p)$ , so $σ_{g}^{2} = p (1 - p) = 0.785 \times 0.215 \approx 0.1688$ . Step 2 — SE of the mean $\overset{ˉ}{X}_{n}$ . $σ_{g}^{2} / n = 0.1688/10000 = 1.688 \times 1 0^{- 5} \approx 0.004109$ . Step 3 — scale by 4 (because $\overset{π}{^} = 4 \overset{ˉ}{X}_{n}$ and $Var (4 Y) = 16 Var (Y)$ , so SE multiplies by 4): $SE (\overset{π}{^}) = 4 \times 0.004109 \approx 0.01644.$ So $\overset{π}{^}$ is good to about $\pm 0.016$ — roughly two decimals. Look at the figure: only the fraction of dots inside the red arc carries information.

L2.2

For the same $π$ estimator, how many samples $n$ do you need so that $SE (\overset{π}{^}) \leq 0.001$ ?

Recall Solution

Set $4 p (1 - p) / n \leq 0.001$ . Solve for $n$ : $\frac{p ( 1 - p )}{n} \leq \frac{0.001}{4} = 2.5 \times 1 0^{- 4} \Rightarrow \frac{p ( 1 - p )}{n} \leq 6.25 \times 1 0^{- 8} .$ $n \geq \frac{0.1688}{6.25 \times 1 0 ^{- 8}} \approx 2.70 \times 1 0^{6} .$ WHY so large: shrinking the L2.1 error ( $0.016$ ) by $16 \times$ needs $1 6^{2} = 256 \times$ more samples. That's the $1/ n$ tax.

Level 3 — Analysis

L3.1

Two runs estimate the same $θ$ : run A uses $n_{A} = 400$ , run B uses $n_{B} = 3600$ . Assuming the same $σ_{g}$ , by what factor is B's standard error smaller than A's?

Recall Solution

$\frac{SE _{A}}{SE _{B}} = \frac{σ _{g} / n _{A}}{σ _{g} / n _{B}} = \frac{n _{B}}{n _{A}} = \frac{3600}{400} = 9 = 3.$ B is 3× more accurate, even though it used 9× the samples. See the figure below: error falls along the $1/ n$ curve, which flattens — later samples buy less.

L3.2

Use Chebyshev's Inequality to bound the probability that a Monte Carlo estimate $\hat{θ}_{n}$ with $Var (\hat{θ}_{n}) = σ_{g}^{2} / n$ deviates from $θ$ by at least $ε$ . Then evaluate the bound for $σ_{g}^{2} = 0.25$ , $n = 10000$ , $ε = 0.05$ .

Recall Solution

Chebyshev says $P (∣ Y - E Y ∣ \geq ε) \leq Var (Y) / ε^{2}$ . With $Y = \hat{θ}_{n}$ : $P (∣ \hat{θ}_{n} - θ ∣ \geq ε) \leq \frac{σ _{g}^{2}}{n ε ^{2}} .$ Plug in: $\frac{0.25}{10000 \times ( 0.05 ) ^{2}} = \frac{0.25}{10000 \times 0.0025} = \frac{0.25}{25} = 0.01.$ So at most a 1% chance the estimate is off by $0.05$ or more. This is exactly Step 3 of the WLLN proof made numeric.

Level 4 — Synthesis

L4.1

Design a Monte Carlo estimator for the double integral $θ = \int_{0}^{1} \int_{0}^{1} (x + y)^{2} d x d y .$ State the estimator, its exact mean $θ$ , and explain why the $1/ n$ error is unchanged by moving from 1-D to 2-D.

Recall Solution

Build it. The joint density of $(U_{1}, U_{2}) \sim Unif ([0, 1]^{2})$ is $1$ , so $θ = E [(U_{1} + U_{2})^{2}] .$ Estimator: draw pairs $(U_{1}^{(i)}, U_{2}^{(i)})$ and average $g_{i} = (U_{1}^{(i)} + U_{2}^{(i)})^{2}$ : $\hat{θ}_{n} = \frac{1}{n} \sum_{i = 1}^{n} (U_{1}^{(i)} + U_{2}^{(i)})^{2} .$ Exact value (for checking): expand and integrate, $θ = \int_{0}^{1} \int_{0}^{1} (x^{2} + 2 x y + y^{2}) d x d y = \frac{1}{3} + 2 \cdot \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{3} = \frac{1}{3} + \frac{1}{2} + \frac{1}{3} = \frac{7}{6} \approx 1.1 \overline{6} .$ Why dimension doesn't hurt: the error formula $σ_{g} / n$ depends only on the variance of the scalar $g$ and the count $n$ — never on the dimension of $X$ . A grid method would need $m^{2}$ points for a 2-D grid; Monte Carlo keeps the same $1/ n$ . That is the numerical-integration payoff.

L4.2

For the estimator in L4.1, the variance of a single $g = (U_{1} + U_{2})^{2}$ is $σ_{g}^{2} = \frac{197}{180} - (\frac{7}{6})^{2}$ . Compute $σ_{g}^{2}$ (leave 4 decimals) and the SE at $n = 5000$ .

Recall Solution

First $E [g^{2}] = E [(U_{1} + U_{2})^{4}] = \frac{197}{180} \approx 1.09444$ (a moment integral). Then $σ_{g}^{2} = \frac{197}{180} - (\frac{7}{6})^{2} = 1.09444 - 1.36111 = - 0.26667.$ A variance cannot be negative — so $E [g^{2}]$ was mis-stated. Recompute honestly: $E [g^{2}] = E [(U_{1} + U_{2})^{4}]$ . With $S = U_{1} + U_{2}$ , $E [S^{4}] = \frac{197}{90} \approx 2.18889$ . Then $σ_{g}^{2} = 2.18889 - 1.36111 = 0.82778.$ $SE = \frac{0.82778}{5000} = 1.6556 \times 1 0^{- 4} \approx 0.01287.$ Lesson baked in: if your variance comes out negative, a moment was wrong — variance is $E [g^{2}] - (E g)^{2} \geq 0$ always.

Level 5 — Mastery

L5.1 — When the LLN fails

You try to estimate the mean of a Cauchy-like variable whose density has tails so heavy that $E ∣ X ∣ = \infty$ . Explain, using the proof structure of the WLLN, exactly which step breaks and what you observe if you plot $\overset{ˉ}{X}_{n}$ vs $n$ .

Recall Solution

Which step breaks: the WLLN derivation needs a finite variance $σ^{2}$ (Step 2) — and even the weaker strong law needs $E ∣ X ∣ < \infty$ . For a Cauchy, the integral defining $E [X]$ diverges, so there is no $μ$ to converge to. Step 3 (Chebyshev) is vacuous because $Var (\overset{ˉ}{X}_{n}) = \infty/ n = \infty$ . What you observe: the running average $\overset{ˉ}{X}_{n}$ never settles — it keeps getting knocked around by occasional gigantic samples. Plot it and you see wild jumps forever, not a flattening curve. Always check the integrand's tails before trusting Monte Carlo.

L5.2 — Variance reduction budget

Two estimators target the same $θ$ . Estimator A has $σ_{A}^{2} = 4$ ; a smarter importance-sampling estimator B has $σ_{B}^{2} = 0.25$ . How many samples $n_{A}$ does A need to match the error B achieves with $n_{B} = 1000$ ?

Recall Solution

Match standard errors: $\frac{σ _{A}^{2}}{n _{A}} = \frac{σ _{B}^{2}}{n _{B}}$ . $n_{A} = n_{B} \cdot \frac{σ _{A}^{2}}{σ _{B}^{2}} = 1000 \times \frac{4}{0.25} = 1000 \times 16 = 16000.$ Why this is the whole point of variance reduction: cutting variance by $16 \times$ is worth 16× fewer samples for the same accuracy. Cleverness in $σ_{g}^{2}$ beats brute force in $n$ — because the two enter the error as a ratio $σ_{g}^{2} / n$ .

L5.3 — Confidence interval, full pipeline

A run of $n = 400$ samples of $g$ gives sample mean $\hat{θ} = 2.00$ and sample standard deviation $\overset{σ}{^}_{g} = 1.5$ . Report the 95% confidence interval (use $z = 1.96$ , CLT).

Recall Solution

Step 1 — SE: $\overset{σ}{^}_{g} / n = 1.5/ 400 = 1.5/20 = 0.075$ . Step 2 — half-width: $z \cdot SE = 1.96 \times 0.075 = 0.147$ . Step 3 — interval: $θ \in 2.00 \pm 0.147 = [1.853, 2.147] .$ WHY the CLT: it tells us $\hat{θ}$ is approximately Normal for large $n$ , and $\pm 1.96$ standard errors captures the middle 95% of a Normal. A point estimate without this interval hides the randomness.

Recall Rapid self-check (cover the answers)

Standard error formula? ::: $σ_{g} / n$ . To halve the error you multiply $n$ by...? ::: 4. Which property makes $Var (\overset{ˉ}{X}_{n}) = σ^{2} / n$ ? ::: independence of the samples. What condition must the integrand satisfy for the LLN to hold? ::: finite mean $E ∣ X ∣ < \infty$ (finite variance for the clean rate). Cutting variance by $16 \times$ saves how many samples for equal accuracy? ::: $16 \times$ .