# Finding the error probability of a Monte Carlo algorithm

Let's say I have a Monte Carlo algorithm $$A$$ that gives the correct answer with a probability $$p$$ > $$1/2$$. I don't have any information on if it's decisional or not.

I understand that I can make another algorithm $$A'$$ that runs $$A$$ for a number of times $$k$$ and returns the average (or the most repeated answer of $$A$$). Considering this, I need to find the value of $$k$$ so that the error probability is at most $$\epsilon$$.

What I don't fully understand is what the error probability of $$A'$$ would be in this case. I have done other Monte Carlo exercises where the error probability would be $$(1-p)^k$$ after repeating $$k$$ times, but those were biased in the way that you could know that if $$A$$ returned specifically true or false, depending on the problem, the answer would be correct. Would the error probability still be $$(1-p)^k$$ in this case?

I've seen in other questions that I can use the Chernoff bounds for this, but since this is an exercise for my algorithmics class in university, and I don't recall having seen the Chernoff bounds or anything similar at all, I'm somewhat reluctant to using it. Also, I don't really understand how to work from that. I would like to know if I need to use Chernoff in this case to find $$k$$ for the error probability to be at most $$\epsilon$$ or if there's another simpler way.

Edit 1: Looking at some old classes from my teacher it looks like she says that we could use the Chebyshev inequality for this same case, but she never showed how to continue with that, and my statistics and probability theory knowledge is very rusty.

• Just to be clear: you don't (necessarily) have a way to check whether the returned answer is correct. Is that right? Also, is there only a single correct answer? Commented Oct 28, 2023 at 12:18
• @Steven With the information I'm given I assume I can't know whether the answer is correct or not, and there is only a single correct answer, yes. I just know it returns the correct answer with a probability of p > 1/2. That's why I've thought of averaging all the results returned by A and returning that, since the bigger k is, the closer the average should be to the correct answer. Commented Oct 28, 2023 at 12:31

Run the algorithm $$A$$ a total of $$2k$$ times and take the most popular answer. Then if this aggregate answer is wrong, this means that at least $$k$$ answers were wrong. This happens with probability: $$r:=\sum_{i=k}^{2k}\binom{2k}{i}(1-p)^{i}p^{2k-1}$$.

You could also bound that by $$r\leq e^{-k(2p-1)^2}$$, for example.

To do so, let $$S$$ be the random variable denoting the number of wrong answers. Then $$S$$ is a sum of $$2k$$ i.i.d. variables with values in $$[0,1]$$ and $$S$$ has expected value $$\mu = 2k(1-p)$$.

We have $$r = \Pr(S\geq k) = \Pr(S-\mu \geq k-\mu) = \Pr(S-\mu \geq k(2p-1)).$$

Let $$t = k(2p-1)$$. Hoeffding's inequality tells us that $$\Pr(S-\mu \geq t) \leq e^{-\frac{2t^2}{2k}} = e^{-\frac{t^2}{k}} = e^{-k(2p-1)^2}.$$

With this bound, we can conclude that taking $$k\geq -\frac{\ln(\epsilon)}{(2p-1)^2}$$ gives you an error probability of at most $$\epsilon$$.

• My probability knowledge is a bit rusty, can you guide me on how to go from that binomial to the other expressions you've described below through Hoeffding's inequality? Commented Oct 28, 2023 at 15:11
• @diegodr02 I fleshed it out a bit. Commented Oct 29, 2023 at 8:02
• That works for me, thank you very much! Commented Oct 29, 2023 at 10:11