I was looking at the proof of if $NP \subseteq BPP$ then $NP = RP$ here.

At the end of the proof the author states: "Note that if $M$ always gives correct answers on calls to $M$, then when $\phi$ is satisfiable, $N$ (the newly constructed TM) constructs a satisfying assignment to $\phi$ and hence accepts. The probability that this happens is at least $1 − n2^{− \Omega(n)}$, which is at most 1/2 for large enough n, since the probability that $M$ gives at least one wrong answer is at most $n2^{− \Omega(n)}$ by the union bound."

I am really confused, why is the probability of getting no wrong answer in n invocations $1 − n2^{− \Omega(n)}$? Shouldn't it be $(2^{− \Omega(n)})^n$ since the invocations are independent? I mean, we have $P(X=0)$ where X = {number of wrong answers} and this is basically a binomial distribution, right? What am I not seeing?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.