3
$\begingroup$

A famous example of Monte Carlo integration is the Monte Carlo estimate of $\pi$.

The unit disk $\{ (x, y) : x^2 +y^2 \le 1 \}$ is inscribed in the square $[ 1, 1] \times [ 1, 1]$, which has area $4$. If we generate a large number of points that are Uniform on the square, the proportion of points falling inside the disk is approximately equal to the ratio of the disk’s area to the square’s area, which is $\frac{\pi}4$. Thus, to estimate $\pi$ we can take the proportion of points inside the circle and multiply by $4$.

How close is estimate to the actual value of $\pi$?

All help are appreciated. Thanks in advance.

$\endgroup$
1
  • $\begingroup$ That would depend on the details of the large number of points. The difference between a sum and an integral can be estimated by Koksma's inequality, which see. $\endgroup$ Dec 3, 2015 at 6:31

1 Answer 1

1
$\begingroup$

We cannot have certainty, so let's deal with a $99\%$ confidence interval (which in this context is highly unsatisfactory).

Every time we increase the number of iterations by a factor of $100$, the width of the $99\%$ confidence interval shrinks by a factor of $10$. The width of the confidence interval for $\pi/4$ when $n=100$ is of order of magnitude $0.1$. So $1$ million iterations give us about $4$ decimal places. One million million iterations (which take a while!) give us about $7$, at the unsatisfactory $99\%$ level. It is decidedly not a good way to proceed.

$\endgroup$
5
  • $\begingroup$ Hi thanks for the explanation. I'm still confused. So if we set n=1000 with 1 million iteration, is there an upper bound for the error? $\endgroup$
    – justin
    Dec 3, 2015 at 16:42
  • $\begingroup$ The number of iterations is usually called $n$, so I am puzzled by the notation in your question. As to upper bound on the error, it is conceivable that because of terrible "luck" the estimate is far from the truth. So one cannot give a non-trivial absolute upper bound for the error. That's where the $99\%$ confidence interval (or if you want, $99.99\%$ comes in. In my answer I gave somewhat rough estimates (they are actually not far off). What I wanted to concentrate on is the crucial fact that at a fixed confidence level, the width of the confidence interval behaves like (More) $\endgroup$ Dec 3, 2015 at 16:53
  • $\begingroup$ (More) $\frac{k}{\sqrt{m}}$, where $m$ is the number of "darts" you throw at the target, the number of trials. So if $m$ trials give you $k$ decimal places (at a certain confidence level) then it takes $100m$ trials to give $k+1$ decimal places at the same confidence level. Practically this means that accuracy is terribly expensive. To get $30$ decimal places at $99\%$ confidence level would require all the computers on Earth, and more. $\endgroup$ Dec 3, 2015 at 16:58
  • $\begingroup$ for k/sqrt(m) , what is k? $\endgroup$
    – justin
    Dec 3, 2015 at 17:20
  • $\begingroup$ For $99\%$ confidence level $k$ is approximately $2.57\sqrt{\pi/4(1-\pi/4)}$, so order of magnitude $1$. And by the way this is for estimating $\pi/4$. The $k$ for the estimate of $\pi$ is $4$ times as large. Not that it really matters, the crucial thing is that $\sqrt{m}$ grows much more slowly than $m$. $\endgroup$ Dec 3, 2015 at 17:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .