4
$\begingroup$

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?

$\endgroup$

1 Answer 1

6
$\begingroup$

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$.

$\endgroup$
8
  • $\begingroup$ Could you explain why my case's variance is $\mu(1 - \mu) \leq 1/4$? $\endgroup$
    – J. Schmidt
    Nov 2, 2021 at 13:32
  • $\begingroup$ 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$). $\endgroup$ Nov 2, 2021 at 13:37
  • $\begingroup$ 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$. $\endgroup$
    – J. Schmidt
    Nov 2, 2021 at 13:42
  • 1
    $\begingroup$ By assumption, the mean of $X$ is $\mu$ (that was the definition of $\mu$). Does this help you determine $p_0,p_1$? $\endgroup$ Nov 2, 2021 at 14:02
  • 1
    $\begingroup$ You can prove statements of the form "with probability $1-\epsilon$, the value of $\bar{X}$ is within $\delta$ of the true answer $\mu$". $\endgroup$ Nov 2, 2021 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.