Why Monte Carlo Error Shrinks at the Square Root of Sample Size

# Monte Carlo Convergence


# Monte Carlo Convergence












Let $\{X_i\}$ be an i.i.d. sample of $X$ with $E(X) = \mu$ and $Var(X) = \sigma^2$. We know a MC estimate converges to the true value almost surely by the SLLN. That is, $$ \bar{X}_n \to \mu, \text{ a.s.} $$ This doesn't tell us anything about the convergence rate. To get that, it seems we consider the CLT, for which we have $$ \bar{X}_n - \mu \to^d \mathcal{N}\left(0, \frac{\sigma^2}{n}\right), $$ where "$\to^d$" is convergence in distribution. Thus, an approximate 95% confidence interval for $\mu$ is $$ \bar{X}_n \pm 1.96\frac{\sigma}{\sqrt{n}}, $$ and I suppose now I can see where the statement, "Monte Carlo converges at the rate $\frac{1}{\sqrt{n}}$" comes from. What people mean by this is, the half-width of the approximate confidence interval decreases at the rate $\frac{1}{\sqrt{n}}$.

Is this correct? If so, this seems like a very different notion of convergence than I'm used to. For example, look at the $L^2$ norm, which gives $$ E((\bar{X}_n - \mu)^2) = Var(\bar{X}_n) = \frac{\sigma^2}{n} \to 0 \text{ as } n \to \infty, $$ so we also get that $\bar{X}_n \to \mu$ in $L^2$, which is not expected in general solely from the a.s. convergence. However, I don't see how this implies a convergence rate of $\frac{1}{\sqrt{n}}$ as advertised; rather, it says $\bar{X}_n \to \mu$ in $L^2$ at a rate $\frac{1}{n}$. Now this seems like a rigorous notion of the convergence rate - we've shown the sense of convergence, and know exactly the rate at which it does so.

So why do we insist on using the CLT-implied "convergence" rate of $\frac{1}{\sqrt{n}}$, when it is just an approximation to begin with, and the weakest form of convergence to boot?

## Answer by Mark Joshi (score 1)

https://quant.stackexchange.com/a/21622

for the L2 norm you have to take a square root and then you get $1/\sqrt{n}$ convergence as before.