<p>Set $\epsilon&#39;_1 := 1/2 - \epsilon_1$. Run $A$ independently $T$ times. If the fraction of accepts exceeds $\epsilon&#39;_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&#39;_1 - \epsilon_2| )$. Therefore as long as $|\epsilon&#39;_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$.</p>

CC BY-SA 3.0
2012-01-27T12:00:29.720Z
The standard and, IMHO, easier to analyze algorithm is to accept iff the fraction exceeds $(\epsilon'_1+\epsilon_2)/2$, with no random guesses.
Emil Jeřábek
CC BY-SA 3.0
2012-01-28T00:44:41.270Z
@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$.
randomizer
CC BY-SA 3.0
2012-01-28T00:50:43.683Z
@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.
randomizer
CC BY-SA 3.0
2012-01-26T23:11:58.790Z
2012-01-27T01:05:22.930Z
2012-01-27T01:05:22.930Z
Mahdi Cheraghchi
<p>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$.</p>

<p>Is there any $\epsilon_1 \ge 0$ and $\epsilon_2 &gt; 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)?</p>

CC BY-SA 3.0
2012-01-26T19:47:48.150Z
You mean P(A(x) accepts) > 1/2 + epsilon in the first case?
Marcin Kotowski
CC BY-SA 3.0
2012-01-26T19:56:05.117Z
You need $\epsilon_1 + \epsilon_2 \leq 1/2 - 1/\mathrm{poly}(n)$.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-01-26T20:55:42.813Z
@MarcinKotowski No. I want to see what happens when its 1/2 or smaller.
randomizer
CC BY-SA 3.0
2012-01-26T21:00:25.143Z
@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.
randomizer
CC BY-SA 3.0
2012-01-26T23:12:21.880Z
I posted a more detailed answer below.
Mahdi Cheraghchi
<complexity-classes><randomized-algorithms>
BPP Error Reduction
randomizer
# BPP Error Reduction

(Asked by: username_0 on 2012-01-26)

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)?

**Tags:** complexity-classes, randomized-algorithms

> **Comments:**
> **username_1**: You mean P(A(x) accepts) > 1/2 + epsilon in the first case?  
> **username_2**: You need $\epsilon_1 + \epsilon_2 \leq 1/2 - 1/\mathrm{poly}(n)$.  
> **username_0**: @MarcinKotowski No. I want to see what happens when its 1/2 or smaller.  
> **username_0**: @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.  
> **username_2**: I posted a more detailed answer below.  

---

## 1 answers

### Answer by username_2 on 2012-01-26. Score: 6 | Accepted answer

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$.

> **Comments:**
> **username_3**: The standard and, IMHO, easier to analyze algorithm is to accept iff the fraction exceeds $(\epsilon'_1+\epsilon_2)/2$, with no random guesses.  
> **username_0**: @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$.  
> **username_0**: @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.  

---

