# Prove Rate of Convergence of Monte Carlo

Let $$X_1, X_2, \ldots$$ be i.i.d. random variables with mean $$\mu$$ and variance $$\sigma^2$$. How does

$$$$\mathbb E\left[\,\left|\frac{1}{N} \sum_{i=1}^n X_i - \mu\, \right|\,\right] \to O\left(\frac{1}{\sqrt N}\right)$$$$

follow from the central limit theorem? We easily get

$$$$\mathbb E\left[\left(\frac{1}{N} \sum_{i=1}^n X_i - \mu\, \right)^2\right] = \frac{\sigma^2}{N},$$$$

but how to get the first one?

EDIT: Actually, any proof would do $$-$$ does not have to use the central limit theorem.

Since $$r\mapsto(\mathsf{E}|\cdot|^r)^{1/r}$$ is nondecreasing,
$$\mathsf{E}|\bar{X}_N-\mu|\le \frac{\sigma}{\sqrt{N}}.$$
• For $0<r\le s$, $(\mathsf{E}|\cdot|^r)^{1/r}\le(\mathsf{E}|\cdot|^s)^{1/s}$. – d.k.o. Feb 7 at 3:57
• But this only implies $\lim_{N \to \infty} \sqrt N\;\mathbb E|\bar X_N - \mu| \leq \sigma$. This does not prevent the limit from being $0$. In particular, this means that the case $\mathbb E|\bar X_N - \mu| \to O(1/N)$ is not excluded. We need to bound $\lim_{N \to \infty} \mathbb E|\bar X_N - \mu|$ strictly away from $0$. – user3749105 Feb 7 at 7:01
• This is what you need. Big $O(N^{-1/2})$ notation means that there is a constant $M$ s.t. $\sqrt{N}\mathsf{E}|\bar{X}_N-\mu|\le M$ for all $N$ large enough. – d.k.o. Feb 7 at 7:18
Use Jensen's inequality: $$\phi(\mathbb{E}[Y])\le \mathbb{E}[\phi(Y)]$$ for any convex function $$\phi$$. Take $$Y=|\overline{X}_N-\mu|$$ and $$\phi(x)=x^2$$.