# Convergence of Monte Carlo integration

In my research, one of the steps is to choose a numerical method to estimate $\int_a^b f(t)dt$, where $f$ is Lipschitz continuous but not differentiable. For simplicity, I used midpoint rule but the overall result is not that good. I was thinking whether the problem came from the fact that I didn't select a correct numerical quadrature rule.

Based on my understanding, to guarantee convergence, most deterministic quadrature rules require the integrand be certain order differentiable. Since in this case, $f$ is not smooth enough, it's reasonable that the mid-point rule can't guarantee convergence.

My supervisor suggested me to use Monte-Carlo integration. But I am not sure about the convergence condition for this numerical method. I only know regardless of the dimension, this method has a $\frac{1}{\sqrt{N}}$ convergence order. Does this result hold for all $L^1$ function? Do we need any additional assumption for integrand $f$ for the convergence? Could you provide me some resources about the convergence analysis for Monte Carlo integration?

• Try a mature, sophisticated quadrature library (like those is scipy, matlab, etc.). Midpoint rule is too primitive to conclude anything meaningful. And don't implement quadrature rules yourself — there are already good libraries out there. Monte Carlo methods would probably converge worse than any of those, they are usually used as a last resort. Is the function particularly nasty? Even non-Lipschitz continuous functions like $\sqrt{x}$ can be integrated without problems. – Kirill Jan 11 '16 at 13:39
• [Also: you asked multiple separate questions in one question — this format on SE works best if you ask single directed questions, like "should I use MC for a specific integrand $f$", "what is MC convergence rate in $L^1$", "what is a good reference on MC" (this is a bit broad), "why doesn't midpoint rule converge" — that's about four separate questions at least.] – Kirill Jan 11 '16 at 13:41
• @Kirill Thanks for your suggestion. What I am asking is whether Lipschitz continuous but non-differentiable $f\in L^1[a,b]$ guarantee the convergence of MC integration? Or what kind of assumption for $f$ we should add in order to have the convergence. – John Jan 11 '16 at 14:25
• @Kirill Correct me if I am wrong. But based on my understanding, we don't prefer MC for lower dimensional integration is it may have slower convergence rate for smooth enough functions compared with other method. But what I am concerning is, for non-differentiable functions, whether MC can still obtain convergence result when the other methods may not be convergent. – John Jan 11 '16 at 14:34

Let the MC integral estimate be $$S_n = \frac{b-a}{n}\sum_{1\leq k\leq n} f(x_k),$$ where $x_k$ are i.u.d. on the interval $[a,b]$. So long as the function $f$ is $L^1$, the mean exists, and $$\mathbb{E}[S_n] = I, \qquad I = \int_a^b f(x)\,dx,$$ so by the law of large numbers $S_n$ will converge to $I$.
To get the $1/\sqrt{n}$ convergence, the function also needs to be square-integrable: $$\mathbb{V}[S_n] = \frac{|b-a|}{n}\int_a^b \big(f(x)-\bar f\big)^2\,dx,$$ (where $\bar f$ is the function average on $[a,b]$), so if $f$ is also $L^2$, then the central limit theorem applies, and $S_n$ would be normally distributed with mean $I$ and variance $n^{-1}|b-a|\mathbb{V}[f]$. When the function is not square integrable, the law of large numbers still applies, but this error distribution is no longer valid, it would have a fat tail.
You don't say what your function $f$ is, but my opinion would be that it has to be pretty pathological (e.g., not differentiable anywhere) before MC methods would outperform a mature quadrature scheme in 1d. Not midpoint, though — you'd never expect that to work well.