Compute value of $\pi$ up to 8 digits

Question

I am quite lost on how approximate the value of $\pi$ up to 8 digits with a confidence of 99% using Monte Carlo. I think this requires a large number of trials but how can I know how many trials?

I know that a 99% confidence interval is 3 standard deviations away from the mean in a normal distribution. From the central limit theorem the standard deviation of the sample mean (or standard error) is proportional to the standard deviation of the population $\sigma_{\bar X} = \frac{\sigma}{\sqrt{n}}$

So I have something that relates the size of the sample (i.e. number of trials) with the standard deviation, but then I don't know how to proceed from here. How does the "8 digit precision" comes into play?

UPDATE

Ok I think I am close to understand it. From CLT we have $\displaystyle \sigma_{M} = \frac{\sigma}{\sqrt{N}}$ so in this case $\sigma = \sqrt{p(1-p)}$ therfore $\displaystyle \sigma_{M} = \frac{\sqrt{p(1-p)}}{\sqrt{N}}$

Then from the Bernoulli distribution, $\displaystyle \mu = p = \frac{\pi}{4}$ therefore

$$\sigma_{M}=\frac{\sqrt{\pi(4-\pi)}}{\sqrt{N}}$$ but what would be the value of $\sigma_{M}$? and then I have $\pi$ in the formula but is the thing I am trying to approximate so how does this work? and still missing the role of the 8 digit precision.

Answer 1

I may completely off the mark, but I guess that Monte Carlo here refers to approximating some integral by a random process, and that the integral must be chosen in a way that knowing its value allows us to calculate $\pi$.

Let's guess that the integral we are interested in is $$ \frac\pi4=\int_0^1\sqrt{1-x^2}\,dx $$ giving the probability that a random point in the square $[0,1]\times[0,1]$ (so $x$ and $y$ independent and uniformly distributed in $[0,1]$) is also in the unit disk.

Assume that we generate $N$ such points $(x,y)$ and record the number of successes (points in the unit disk) $M$. We know from crude estimates for $\pi$, say $3<\pi<4$, that the success rate $p$ of an individual point is between $3/4$ and $1$. Therefore the standard deviation of $M$ is bounded from above by $$\sigma(M)=\sqrt{Np(1-p)}<\frac{\sqrt{3N}}4.$$

We approximate $$ \pi\approx\frac{4M}N. $$ This has SD $\sigma(\pi)<4\sigma(M)/N=\sqrt{3/N}$.

For 99% confidence we want $3\sigma(\pi)<10^{-8}$ or equivalently $\sqrt{N}>3\sqrt{3}\cdot 10^8$. This suggests that generating $N\approx 27\cdot10^{16}$ random points on the unit square would do the trick :-)

After this gedankenexperiment I quite appreciate Machin's formula. Even the alternating series for $\arctan 1$ beats this.

So this leaves open the possibility that something completely different was wanted?

Answer 2

The usual trick is to use the approximation of 355/113, repeating multiples of 113, until the denominator is 355. This version of $\pi=355/113$ is the usual implied value when eight digits is given.

Otherwise, the approach is roughly $\sqrt{n}$

Answer 3

The statistical analysis given in the other answer seems fine.

But the discussion of integrals is unnecessary, I think. The standard Monte-Carlo technique for estimating $\pi$ is to generate $N$ random points in a square centered at the origin -- say the square $[-1,1] \times [-1,1]$. After generating each point $(x,y)$, you can check to see if $x^2 + y^2 < 1$, which tells you whether that point lies in the unit circle. You keep track of the fraction $k$ of random points that lie within the unit circle. As $N$ gets larger, this fraction $k$ gives increasingly accurate estimates of the ratio $\text{(area of circle)} / \text{(area of square)}$. In other words $k \approx \pi/4$, when $N$ is large, so $\pi \approx 4k$.

The statistical analysis given in the other answer tells you how large $N$ must be in order to achieve the desired accuracy with a desired probability.

There is a fairly good explanation on this web page.

And another one on this page.