I found this proof in Wikipedia, but one of the most important steps in it doesn't make any sense to me. I'll explain:
By the definition of PP there is a polynomial-time probabilistic algorithm A with the property that ${x\in L\Rightarrow \mathrm {Pr} [A(x) = 1]>\frac{1}{2}} $ and ${x\not \in L\Rightarrow \mathrm {Pr} [A(x) = 1]\leq \frac{1}{2}}$.
Let $f(|x|)$ be the polynomial upper bound on the running time of A on input x. Thus A makes at most $f(|x|)$ random coin flips during its execution. In particular, $ x\in L\Rightarrow {\mathrm {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$.
I understand that:
- By definition of PP, ${x\in L\Rightarrow \mathrm {Pr} [A(x) = 1]>\frac{1}{2}} $. It means that if indeed $x \in L$, more than half of the possible coin flip combinations would cause the algorithm to accept.
- The algorithm's running time is bound by $f(|x|)$, then the probability of getting some specific combination of coin tosses (that accepts or rejects, we do not know) is bound by $(\frac{1}{2})^{f(|x|)} = \frac{1}{2^{{f(|x|)}}}$.
But why is it so obvious that $ x\in L\Rightarrow {\mathrm {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$?
That one specific combination of coin flips could easily be one of the half that was already counted in the definition of PP, and in that case, it would not make any sense add together "half of the possible coin flip combinations and one specific combination". What am I missing here?
