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