Return to Revisions

Different runs of the algorithm $A$ are independent, so if $A$ is right with probability $p = 1/2 + \epsilon$, with $\epsilon > 0$, the number of times $A$ is right over $N$ runs has binomial distribution $B(N,p)$. So $$ \mathrm{Pr}[A \text{ is wrong more than } N/2 \text{ times}]\le \mathrm{Pr}[B(N,p)\le N/2] $$ This last probability is the kind of thing that you can analyze with Chernoff bounds. In particular, it implies that a polynomial number of repetitions of $A$ is sufficient for the majority outcome to be right with probability $1-1/n$.