# Understanding Monte Carlo Probabilities

I am trying to get a good grasp on Monte Carlo (MC) algorithms, but I feel I am missing something fundamental.

What I don't understand is how MC improves its confidence of giving the correct solution by running more executions.

So please correct me if I am wrong and assume that $Pr[false] \leq 0.5$. Assume we need to find the number of executions so that $Pr[false] \leq 0.125$, thus improving confidence.

Is it true that the number of needed executions is $3$, since $0.5^3=0.125$?

The probability that the above algorithm returns an incorrect answer is thus at most 1/2. Now, the key idea is to understand that successive runs of the algorithm produce answers that are independent of each other - hence, on running it twice, the probability that the algorithm returns an incorrect answer both times is at most $$(\frac{1}{2})^2$$. Thus, after $$k$$ iterations, the probability of an incorrect answer reduces to at most $$(\frac{1}{2})^k$$. Thus, if we adopt the scheme that the algorithm returns false if the any of the first $$k$$ runs give an output of false, else return true, then the probability that our scheme returns an incorrect answer is at most $$1 - (\frac{1}{2})^k$$, which can be driven down to $$0$$ for large values of $$k$$.