1
$\begingroup$

In numerical mathematics, we have to approximate the value of $\pi$ using three different methods. One of the three methods is the Monte-Carlo method, i.e. I let Matlab produce $n$ random numbers within the unit square, then I counted the numbers which were within the unit circle and looked at the quotient of those two numbers.

Afterwards, an exercise states that we are to calculate the error of each of the three methods. As the other two methods were infinite sums, I assumed that I was to express the error in terms of $n$. However, I have no idea how I would calculate the formal error in terms of $n$ of the Monte-Carlo method.

Is it actually possible to do so, or at least to approximate that error? Or is it only statistics?

Thanks for any help.

1 Answers 1

4

See my second (according to date) answer to this question.

Elaborating (based on results from the aforementioned thread, and using the same notation).

Let $\bar Z_n = \frac{{\sum\nolimits_{i = 1}^n {Z_i } }}{n}$ be the corresponding quotient approximating $\pi/4$ (with probability $1$, $\bar Z_n \to \pi/4$ as $n \to \infty$). It has expectation and variance given by $ {\rm E}[\bar Z_n ] = \frac{\pi }{4}, \;\; {\rm Var}[\bar Z_n ] = \frac{\pi }{{4n}}\Big(1 - \frac{\pi }{4}\Big) < \frac{{10}}{{59n}}, $ leading to the following probabilistic error bound: $ {\rm P}\bigg[\bigg|\bar Z_n - \frac{\pi }{4} \bigg| \geq \varepsilon \bigg] < \frac{{10}}{{59n\varepsilon ^2 }}. $ Thus, for example, $ {\rm P}\bigg[\bigg|\bar Z_{10^6} - \frac{\pi }{4} \bigg| \geq 10^{-2} \bigg] < \frac{{1}}{{590 }}. $ Further, the central limit theorem leads to the following approximation (in distribution): $ \bar Z_n - \frac{\pi }{4} \approx \frac{\sigma }{{\sqrt n }}\xi, $ where $ \sigma^2 = {\rm Var}[Z_1] = \frac{\pi }{4} \Big(1 - \frac{\pi }{4}\Big) < \frac{10}{59} $ (hence $\sigma \approx 0.41$) and $\xi \sim {\rm Normal}(0,1)$. For example, for $n=10^6$, this gives $ \bar Z_{10^6} - \frac{\pi }{4} \approx 4.1 \times 10^{-4} \xi. $ Now, you can use a Normal Distribution Calculator to get a probabilistic estimate of the error. For example, ${\rm P}(|\xi| \leq 1) \approx 0.682689$, ${\rm P}(|\xi| \leq 2) \approx 0.9545$, and ${\rm P}(|\xi| \leq 3) \approx 0.9973$. Hence, with high probability, the absolute error $|\bar Z_{10^6} - \pi/4|$ will be less than, say, $10^{-3}$.

Finally, it is interesting to compare the above approximation with the following one (see my first answer to the related question). Let $\bar Y_n = \frac{{\sum\nolimits_{i = 1}^n {\sqrt {1 - U_i^2 } } }}{n}$, where $U_i$ are independent uniform$[0,1]$ variables (it too converges, with probability $1$, to $\pi / 4$ as $n \to \infty$). $\bar Y_n$ has expectation and variance given by $ {\rm E}[\bar Y_n ] = \frac{\pi }{4}, \;\; {\rm Var}[\bar Y_n ] = \frac{1}{n} \bigg \{ \frac{2}{3} - \frac {{\pi ^2 }}{{16}}\bigg\} < \frac{1}{{20n}}, $ leading to $ {\rm P}\Big[\Big|\bar Y_n - \frac{\pi }{4} \Big| \geq \varepsilon \Big] < \frac{1}{{20n\varepsilon ^2 }}. $ As before, the central limit theorem leads to the approximation $ \bar Y_n - \frac{\pi }{4} \approx \frac{\sigma }{{\sqrt n }}\xi $ (with $\xi \sim {\rm Normal}(0,1)$), but this time $ \sigma^2 = {\rm Var}[Y_1] = \frac{2}{3} - \frac{{\pi ^2 }}{{16}} < \frac{1}{20} $ (hence $\sigma \approx 0.223$). Note that the variance in this case is considerably smaller than the one in the previous case.

  • 0
    @Huy: I'll address your questions in an elaborated answer (all for the approximation of $\pi / 4$).2011-03-01