Consider the class of all languages $L$ that have a randomized algorithm $A$ that runs in worst-case polynomial time such that for any input $x$ if $x \in L$ then $Pr[A(x)\quad \textrm{accepts}] \ge 1/2 - \epsilon_1$; otherwise $Pr[A(x) \quad \textrm{accepts}] \le \epsilon_2$.

Is there any $\epsilon_1 \ge 0$ and $\epsilon_2 > 0$ that make this class equal to BPP? If it is, what are the largest values $\epsilon_1$ and $\epsilon_2$ that we can get (perhaps, relative to each other)?

  • $\begingroup$ You mean P(A(x) accepts) > 1/2 + epsilon in the first case? $\endgroup$ Commented Jan 26, 2012 at 19:47
  • $\begingroup$ You need $\epsilon_1 + \epsilon_2 \leq 1/2 - 1/\mathrm{poly}(n)$. $\endgroup$ Commented Jan 26, 2012 at 19:56
  • $\begingroup$ @MarcinKotowski No. I want to see what happens when its 1/2 or smaller. $\endgroup$
    – randomizer
    Commented Jan 26, 2012 at 20:55
  • $\begingroup$ @MCH I was suspecting that $\epsilon_2 < 1/2-\epsilon_1$ (almost the same as what you said), but I couldn't prove it. I got confused in the middle of my proof idea. $\endgroup$
    – randomizer
    Commented Jan 26, 2012 at 21:00
  • $\begingroup$ I posted a more detailed answer below. $\endgroup$ Commented Jan 26, 2012 at 23:12

1 Answer 1


Set $\epsilon'_1 := 1/2 - \epsilon_1$. Run $A$ independently $T$ times. If the fraction of accepts exceeds $\epsilon'_1$ (falls below $\epsilon_2$), then accept (reject). Otherwise output a random guess. Use Chernoff bounds to show that the probability of ending up with a wrong value is exponentially small in $T$, more precisely the error probability can be upper bounded by $\exp(-T |\epsilon'_1 - \epsilon_2| )$. Therefore as long as $|\epsilon'_1 - \epsilon_2| \geq 1/\mathrm{poly}(n)$ (in other words, $\epsilon_1 + \epsilon_2 \leq 1/2 - 1/\mathrm{poly}(n)$), you can choose a polynomially bounded $T$ to bring the error probability below $1/3$.

  • 2
    $\begingroup$ The standard and, IMHO, easier to analyze algorithm is to accept iff the fraction exceeds $(\epsilon'_1+\epsilon_2)/2$, with no random guesses. $\endgroup$ Commented Jan 27, 2012 at 12:00
  • $\begingroup$ @EmilJeřábek I know what you mean, but the above algorithm highlights that it doesn't matter how your algorithm answers when the fraction is between $\epsilon_2$ and $\epsilon'_1$. $\endgroup$
    – randomizer
    Commented Jan 28, 2012 at 0:44
  • 1
    $\begingroup$ @MCH Thanks. I was trying to use majority to decide while here the natural generalization to majority idea was to use the fraction to decide. $\endgroup$
    – randomizer
    Commented Jan 28, 2012 at 0:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.