4
$\begingroup$

Suppose we are using Monte Carlo simulation to estimate the pi. You draw $n$ random sample $(x,y)$ within $(-1,1)$ and you count the number of $x^2 + y^2 < 1$. If you want to estimate to the kth digits of Pi using this method, how many sample do you need? Is there a statistical way to give a boundary?

$\endgroup$
3
$\begingroup$

The area of a Circle is $\pi\times r^2$ and the Area of a square on the coordinates $(\pm1 , \pm1)$ is $4$. The ratio of the area of the square indicated to the circle is $\pi/4$ because the radius of the circle is $1$. Now if we sample from the unit square and only accept the points inside the unit square we get accept the sample $\pi/4$ percent of the time ($\pi/4$ is less than $1$). A consistent and unbiased estimator is the sample mean of the the indicators (random variables that take the value $1$ when inside the circle) from this sampling scheme. The sample mean has variance $p(1-p)/n$ where $p=\Pr(X^2+Y^2<1)=\pi/4$. A rough approximation would be to say that the binomial variance, $p(1-p) < 1/4$, then use the multiplier of the normal distribution approximation to get $1.96$ to get an upper point of the confidence interval $\bar{x}_n + \frac{1.96}{4\sqrt{n}}$ to within your desired level of accuracy. Suppose your accuracy is $10^{-k}$ for some $k\in\{1,2,3,\dots \}$. Then bound the upper deviation of the confidence interval upper limit point to be less than the desired accuracy:

$$\frac{0.7}{\sqrt{n}}\leq 10^{-k}.$$

Solving the inequality for $k$ gives you $n \geq 0.49 \times 100^{k}$. If instead you prefer to use a more accurate approximation for $p=\Pr(X^2+Y^2<1)=\pi/4$, then replace $0.7$ above with $1.96\times p(1-p)$ and solve for $n$. Therefore here if you want $k=2$ digits of accuracy (at $95\%$ confidence) you need your sample to be greater than $0.49\times 100^2=4900.$ Note you might still be inaccurate $5\%$ of the time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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