Finding the error probability of a Monte Carlo algorithm

Question

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.

Thank you in advance.

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.

Answer 1

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