### rotavirus's blog

By rotavirus, history, 17 months ago,

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

Let $X_N$ be the random variable that denotes the result of running the experiment $N$ times; the probability of getting $\frac{k}{N}$ 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$.

• +155

 » 17 months ago, # |   +98 Haha while(clock()<(TL-TL_EPS)*CLOCKS_PER_SEC) go brrr
•  » » 17 months ago, # ^ |   -29 Tell it to the problems when you don't know whether to run your solution locally for 30 or 60 minutes
•  » » 17 months ago, # ^ |   -60 I ask everyone to downvote this unfunny clown who either has bad sense of humor or doesn't know the world isn't limited with cp
•  » » » 17 months ago, # ^ |   +140
•  » » » » 17 months ago, # ^ |   +22 Is this a face reveal?
 » 17 months ago, # |   +36