Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
I didn't know whether to ask you here or in the other thread, I hope it's okay that I'm doing it here. In your answer, as far as I understand, you give a formula to calculate the probability of $\bar{Z}_n$ being at least $\varepsilon$ far away from $\mu$, depending on $n$, the amount of random numbers you use. What I am looking for is a formula to calculate rough boundaries for the error. Is it $\frac{10}{59}$? Or how would I have to transform your final formula? I apologize in case my question is redundant, but I only had statistics in high school up to now... –  Huy Mar 1 '11 at 18:45
    
Could I work with the standard deviation $\sigma(\bar{Z}_n) = \sqrt{\frac{\sigma^2}{n}}$? Wikipedia says 99.7% of all random numbers to be at the most $3 \sigma$ far away from $\mu$, that seems to be a good bound. The value also makes sense with my simulations so far, for $n = 10^3$, I get a standard deviation of $\sigma(\bar{Z}_n) \approx 0.039$ whereas my approximated result equals $3.1280$ (an error of $0.0136$). –  Huy Mar 1 '11 at 19:01
    
@Huy: I'll address your questions in an elaborated answer (all for the approximation of $\pi / 4$). –  Shai Covo Mar 1 '11 at 19:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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