Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

On the Number of Runs at the Monte-Carlo Method

Revision en1, by rotavirus, 2020-12-24 18:02:05

We'll consider problems of the kind "Find the probability p of some event with the absolute error up to ε". One of the methods to solve it is the Monte Carlo method: we simulate this experiment N times and estimate its probability as number of successesN. Let's estimate the accuracy of this method.

Let XN be the random variable that denotes the result of running the experiment N times; the probability of getting kN as the result is equal to \binom{N}{k} p^k (1-p)^{N-k}; in other words, it is equal to the binomial distribution divided by N. Its mean is \mu = p and its standard deviation is \sigma^2 = \frac{p(1-p)}{N}.

According to Chebyshev's inequality:

P(wrong \ answer) = P(|X - p| \geqslant \varepsilon) = P(|X - \mu| \geqslant \varepsilon) \leqslant \frac{\sigma^2}{\varepsilon^2} = \frac{p(1-p)}{N \varepsilon^2}

We can bound p(1-p) as \frac{1}{4}:

P(wrong \ answer) \leqslant \frac{1}{4N \varepsilon^2}

So if we want the probability of getting the wrong answer for a single test to be at most 0.05, then we would like to run the experiment 5 \varepsilon^{-2} times, if possible; if we want the probability of getting the wrong answer for a single test to be at most 0.01, then we would like to run the experiment 25 \varepsilon^{-2} times.

Another approach to estimating how accuracy depends on N is assuming X approximates the normal distribution N(\mu,\sigma^2) \approx N(p,\frac{1}{4N}) for big N (sorry for the ambiguity of the notations), that means 2 \sqrt{N}(X-p) approximates the standard normal distribution N(0,1). Thus:

P(wrong \ answer) = P(|X-p| \geqslant \varepsilon) = P(2 \sqrt{N} |X-p| \geqslant 2 \sqrt{N} \varepsilon) \approx P(|N(0,1)| \geqslant 2 \sqrt{N} \varepsilon)

So, if we want the probability of getting the wrong answer for a single test to be equal to w, then:

2 \sqrt{N} \varepsilon = \Phi ^{-1} (\frac{w+1}{2})
N = \left( \frac{\Phi ^{-1} (\frac{w+1}{2})}{2 \varepsilon} \right) ^2

Where \Phi^{-1} is the quantile function of the standard normal distribution. For example, for w=0.05 N = (0.98 \varepsilon ^{-1}) ^ {2} , for w = 0.01 N = (1.4 \varepsilon ^{-1})^{2}. As you can see, this approach gives a better bound on N rather than the previous one.

Epilogue

A problem of the kind "Find the area of the given figure with the relative error up to \varepsilon" can be transformed to the problem "Find the probability of a random point thrown in some bounding figure T belongs to the given figure with the absolute error up to \varepsilon '" with \varepsilon ' \approx \varepsilon.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rotavirus 2020-12-24 18:02:05 2756 Initial revision (published)