3
$\begingroup$

I have been reading about a method for approximating $\pi$ using two uniform distributions and the ratio of points that lie within the circle compared to the square formed by the two uniform distributions.

e.g.

$X,Y \sim U(0,1)$, then we take the ratio of points that lie within the circle of radius $1/2$ by the total number of points generated by the uniform distributions.

Namely, $(x-1/2)^2 + (y-1/2)^2 \leq 1/4$

If we take these points and divide them by the number of all points $(x,y)$, we approximate $\pi/4$.

Question: I wanted to ask about the rate of convergence for this Monte Carlo simulation. I am reading that it is $n^{-1/2}$ by the Central Limit Theorem but I do not understand why. Could someone explain this? $n^{1/2}$ is in the denominator of CLT that would allow us to approximate the standard normal distribution but why do we care about the standard normal here?

$\endgroup$

1 Answer 1

3
$\begingroup$

Let $n$ be the number of samples and $\hat{I}_n = \frac{\text{Number of samples in the circle}}{n}$ be the estimator for $\frac\pi4$. The central limit theorem (CLT) states that (under weak assumptions, that should be fulfilled here) the distribution of the error $\hat{I}_n - \frac\pi4$ converges weakly to a mean-zero Normal distribution, as $n \rightarrow \infty$.

Intuition: As $n$ increases the variance of this normal distribution tends to 0. If the variance goes to zero, the error is 0 and hence one convergences.

More particular: Let $Z$ be the random variable that is one, if the sample $(X,Y)$ lies in the circle and zero otherwise. The distribution of $Z$ is given by $P(Z = 1) = \frac\pi4$ and $P(Z= 0) = 1- \frac\pi4.$ The mean of $Z$ is $E[Z] = \frac\pi4$ and the variance is $\mathrm{Var}(Z) = \frac\pi4(1- \frac\pi4)$. The estimator $\hat{I}_n$ is the sample mean of $n$ samples of $Z$. Then $$\sqrt{n}\left(\hat{I}_n-\frac\pi4\right) \rightarrow \mathrm{N}(0, \mathrm{Var}(Z)),$$ weakly as $n \rightarrow \infty$. The $\sqrt{n}$ goes to infinity, but the right-hand side is independent of $n$ and constant, hence the standard deviation of $\left(\hat{I}_n-\frac\pi4\right)$ has to go to zero, as fast as $\sqrt{n}$ goes to infinity.

$\endgroup$
1
  • $\begingroup$ That's great, thank you for the great explanation! $\endgroup$
    – ggmp
    Aug 2, 2018 at 10:22

You must log in to answer this question.

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