# Prove or refute: BPP(0.90,0.95) = BPP

I'd really like your help with the proving or refuting the following claim: $BPP(0.90,0.95)=BPP$. In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most $\frac{1}{3}$ for all instances. $BPP=BPP(\frac{1}{3},\frac{2}{3})$.

It is not immediate that any of the sets are subset of the other, since if the probability for an error is smaller than $0.9$ it doesn't have to be smaller than $\frac{1}{3}$ and if it is bigger than $\frac{2}{3}$ it doesn't have to be bigger than $0.905$.

I'm trying to use Chernoff's inequality for proving the claim, I'm not sure exactly how. I'd really like your help. Is there a general claim regarding these relations that I can use?

• I'm not sure what the notation BPP(x, y) means. Is it that a string not in the language is accepted with probability no greater than x and a string in the language is accepted with probability greater than y? – Matt Lewis Jan 7 '13 at 22:17
• Exactly, You are correct. – Numerator Jan 7 '13 at 22:21
• Hint: if you run $n$ trials on a string that isn't in your language, what's the probability that more than e.g. $.9\ n+c\sqrt{n}$ of them accept the string? If you run $n$ trials on a string that is in the language, what's the probability that fewer than $.95\ n-c\sqrt{n}$ of them reject the string? What happens to your acceptance/rejection probabilities if you run $n$ trials and say 'accept any string that is accepted by more than $.925\ n$ runs', as $n\to\infty$? – Steven Stadnicki Jan 7 '13 at 23:49
• Steven Stadnicki's hint is for showing that $BPP(0.9,0.95) \subseteq BPP(1/3,2/3)$. For the other direction, show that $BPP(1/3,2/3) \subseteq BPP(\epsilon,1-\epsilon)$ for every $\epsilon$. In the same way you can show that $BPP = BPP(\alpha,\beta)$ for any constants $0<\alpha<\beta<1$. – Yuval Filmus Jan 8 '13 at 0:50

To expand out my comment into an answer: the multiplicative form of Chernoff's bound says that if the expectation $X=\sum_{i=0}^n X_i$ for the sum of independent random binary variables is $\mu$, then the probability of straying 'too far' from that expectation goes as: $Pr(X\gt (1+\delta)\mu) \lt \left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$.
Now, imagine a procedure where, given a string $\sigma$ to test, we run $n$ trials of our $BPP(0.90, 0.95)$ algorithm (for some $n$ to be chosen later) and accept iff at least $0.925n$ of those trials accept $\sigma$. We can use Chernoff's bound to find the probability of failure in terms of $n$ as follows:
Let $X_i$ denote the outcome of the $i$th trial, and thus $X=\sum X_i$ the number of trials that succeed. We can assume conservatively that our probability for false positives is $.9$; this means that if we make $n$ independent trials on a string $\sigma\notin L$, the expected number of successes is $\mu = E(X) = 0.9n$. (Note that a false positive probability less than $.9$ will lead to an even lower expected value and thus to even tighter bounds on the estimates to come.) Now, let's look at the probability that we have more than $0.925n$ false positives (i.e., that $X\gt 0.925n$). We take $\delta = \left(\frac{0.925}{0.9}\right)-1 =\frac{1}{36}$; then $\left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right) \approx.99961\lt \frac{2999}{3000}$ and so we have $Pr(X\gt 0.925n)\lt\left(\frac{2999}{3000}\right)^{0.9n}$.
From here it should be clear that by taking $n$ large enough we can reduce this probability to $\lt\frac{1}{3}$. Thus, for this sufficiently large $n$, if we accept the string $\sigma$ only if the number of successful trials on $\sigma$ is greater than $.925n$, then our probability of accepting a string $\sigma\notin L$ drops below $\frac{1}{3}$. Note that this $n$ is constant, not dependent on our problem size; since we're running our polynomial $BPP(0.9, 0.95)$ algorithm a constant number of times, the total running time of our new procedure is still polynomial. A similar analysis going the other direction will show that the probability of a 'false negative' (that $X\lt.925n$ for a string that is in our language) will be bounded by $c^n$ for some $c$, and so again we can take $n$ large enough to bound the probability of a false negative by $\frac{1}{3}$ (or, in other words, to ensure at least $\frac{2}{3}$ probability of accepting on a string $\sigma\in L$). This shows that $BPP(.9, .95)\subseteq BPP(\frac13, \frac23) \equiv BPP$, and Yuval's comment shows how to prove the reverse equivalence through a similar procedure.