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:

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

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:

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

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$$$.

Haha

`while(clock()<(TL-TL_EPS)*CLOCKS_PER_SEC)`

go brrrTell it to the problems when you don't know whether to run your solution locally for 30 or 60 minutes

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

Is this a face reveal?

https://en.wikipedia.org/wiki/Hoeffding%27s_inequality