Is there some kind of expected error margin for my Monte Carlo algorithm?

Question

My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the other circles, through iteratively testing random points of the larger circle.

On this site it is stated that Monte Carlo algorithms' error decreases with the square root of the number of trials. Would it thus be correct to state that, since my expected error is upper bounded in the beginning by 100%, after 100 iterations, the error would be upper bounded by 10%, and after 10000 iterations, this would be only 1% and so on?

Answer 1

Suppose that you are trying to estimate some quantity $\mu$ by performing some random experiment $X$ with mean $\mu$ and variance $\sigma^2$. In order to obtain a better estimate, you can repeat the experiment $n$ times and take the average $\bar{X} = \frac{X_1+\cdots+X_n}{n}$, which also has mean $\mu$ but its variance is only $\sigma^2/n$. This means that $$ \mathbb{E}[(\bar{X} - \mu)^2] = \frac{\sigma^2}{n}. $$ Moreover, under mild assumptions, the distribution of $\bar{X}$ will be "close" to a normal distribution with mean $\mu$ and variance $\sigma^2/n$.

The standard deviation is the square root of the variance, which is $\sigma/\sqrt{n}$; this decreases like square root of $n$. The standard deviation is a standard measure for error. If you approximate the distribution of $\bar{X}$ by a Gaussian, then the width of the Gaussian scales like the standard deviation, and so it has inverse square root behavior (as a function of the number of experiments).

---

In your case, the experiment $X$ has two possible answers, 0ドル$ and 1ドル$, and so its variance is $\mu(1-\mu) \leq 1/4$, and its standard deviation is at most 1ドル/2$. Taking the average of $n$ experiments gives us a standard deviation of at most 1ドル/(2\sqrt{n})$.

Therefore if you average over 100 iterations, your standard deviation will be at most 1ドル/20$. This doesn't mean that you will be 1ドル/20$ away from the true value. No such guarantee is possible — if you're unlucky then all $X_i$'s will be equal to 0ドル$ or all of them to 1ドル$, one of which will result in an error of at least 1ドル/2$. It means that the distribution of the output will look roughly like a standard Gaussian scaled down a factor or 20, and centered around the true answer $\mu$.

• J. Schmidt: Could you explain why my case's variance is $\mu(1 - \mu) \leq 1/4$?
• Yuval Filmus: You can compute the variance using the formula. If you do so, you'll get $\mu(1-\mu),ドル which is at most 1ドル/4$ (the maximum of the quadratic is attained at $\mu = 1/2$).
• J. Schmidt: Using the formula for the variance of a discrete random variable found on en.wikipedia.org/wiki/Variance , I find that it equals $p_0 \mu^2 + p_1 (1-\mu)^2$.
• Yuval Filmus: By assumption, the mean of $X$ is $\mu$ (that was the definition of $\mu$). Does this help you determine $p_0,p_1$?
• Yuval Filmus: You can prove statements of the form "with probability 1ドル-\epsilon,ドル the value of $\bar{X}$ is within $\delta$ of the true answer $\mu$".