I do not understand Which is more accurate, the hit-and-miss method or the improved Monte-Carlo method?
Here it is written that that the hit-and-miss has a higher variance but they showed (variance of improved Monte-Carlo) - (variance of hit-and-miss method) > 0
$$\sigma^2_M-\sigma^2_H>0$$
Doesn't it imply improved Monte-Carlo method has a higher variance?
Can you please explain it experimentally to me with an easy example (such as for a small integration)?
First, they compare crude (M) and hit-or-miss (H) there; they don't mention 'improvements' until after that section where the comparison is done.
The page apparently contains a typographical error.
The crude estimate ($M$) has a smaller variance, $\sigma^2_M$ than the hit-and-miss estimate's ($H$) variance, $\sigma^2_H$. That is, $\sigma^2_M<\sigma^2_H$
As requested, I will illustrate this via a simple example. Consider using both methods on the following integration problem:
that is, $\int_0^1 f(x) dx$ where $f(x)=x,\quad 0<x<1$.
Here's the results of 1000 simulations with 1000 points of each kind of estimator:
As you see, $\sigma^2_M$ has the smaller variance, so the claim from the page that $\sigma^2_M-\sigma^2_H>0$ is a mistake.
I did the simulations in R:
x=matrix(runif(1000000),nr=1000)
y=matrix(runif(1000000),nr=1000)
crude=colMeans(x)
mean(crude)
[1] 0.5001032
sd(crude)
[1] 0.009110159
hitmiss=colSums(y<x)/1000
mean(hitmiss)
[1] 0.500518
sd(hitmiss)
[1] 0.01622797
We can also calculate the variance of the two algebraically.
The variance of the crude estimate for my example problem is simply $\frac{1}{n} \text{Var}(X)$ where $X$ is uniform on $(0,1)$; that is, it should be 1/(12n) for this problem.
The variance of the hit-or-miss estimate is given here. For our problem, $\theta=1/2$, so the variance for this problem should be 1/(4n).
The standard deviations for $n=1000$ should then be about 0.00913 for the crude and about 0.0158 for the hit-and-miss. The above simulations came out pretty close to those values (0.00911 vs 0.0162).
Note that the integral they give there, $\frac{1}{n}\int_0^1 f(u)(1-f(u))du$ works out to be 1/(6n) for our toy problem here... which happens to be the same as 1/(4n) - 1/(12n) ... which is $\sigma^2_H-\sigma^2_M$ in our example. That's no accident, and - as I said at the start - apparently it's just a typo.
That is, they just got the subscripts backward; they actually prove that $\sigma^2_H-\sigma^2_M >0$ (edit: their result isn't true in all circumstances; they must elsewhere restrict the class of functions)
I would have said this as comment, except I don't have enough rep.
As Glen_b already pointed out, the claim contains a typo. It should really be $$\begin{align}\sigma^2_M-\sigma^2_H&={1\over n} E(f^2)-{\theta^2\over n}-{\theta\over n} +{\theta^2\over n}\\&={1\over n}(E(f^2)-\theta)\\&={1\over n}(E(f^2)-E(f))\\&={1\over n}\int^1_0 f(u)(f(u)-1)du\end{align}$$ Therefore $$\sigma^2_H-\sigma^2_M={1\over n}\int^1_0 f(u)(1-f(u))du$$ Moreover, the next claim that $${1\over n}\int^1_0 f(u)(1-f(u))du>0$$ is neither always true nor false. Consider as example $f(u)=Ku$ where $K$ is just a constant. Then $${1\over n}\int^1_0 f(u)(1-f(u))du={K\over 2}-{K^2\over 3}>0 \iff 0<K<{3\over 2}$$ So that claim is only sometimes true, and $f(u)=Ku$ is only one class of functions of $u$.
