rotavirus's blog

By rotavirus, history, 4 years ago, In English

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

  • Vote: I like it
  • +155
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +98 Vote: I do not like it

Haha while(clock()<(TL-TL_EPS)*CLOCKS_PER_SEC) go brrr

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -60 Vote: I do not like it

    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