How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $

Question

I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ Can any body explain this to me in simple terms. Any help on this is highly appreciated.

Answer 1

The key idea is that because the probability of error is less than one half you can decrease that probability further by repeatedly running the algorithm a polynomial number of times and accepting the majority result. For example, using the standard definition of $BPP$ which has a 1/3 probability of error, if you wanted a 99% probability of getting a correct answer, you would need to run the algorithm enough times that the probability of getting a majority wrong answer is less than 1%. For n runs the probability of a majority of runs producing the wrong answer is $1 / 3^{(n/2)+1}$. Solving for $n$:

$$ \begin{align*} \frac{1}{3^{(n/2)+1}} &< \frac{1}{100} \\ 3^{(n/2)+1} &> 100 \\ \frac{n}{2}+1 &> log_3 100 \\ \frac{n}{2} &> (log_3 100) - 1 \\ n &> 2(log_3 100 - 1) \\ n &> 2(4.19 - 1) \\ n &> 6.38 \\ \end{align*} $$

So 7 runs should produce a majority correct answer with 99% certainty. As the overall formula indicates, you can always do this sort of amplification with a number of runs that has a logarithmic relationship to the degree of certainty required.