<p>This feels like a typical university exam and here is not the best place to answer this. EDIT: Here is a detailed answer.</p>
<p>Let us consider <span class="math-container">$M_n$</span> that given <span class="math-container">$w$</span>, runs <span class="math-container">$n$</span> times <span class="math-container">$M$</span> and returns <span class="math-container">$1$</span> when
the number of accepting runs is over <span class="math-container">$n\times (b+a)/2$</span>.</p>
<p>Let us consider <span class="math-container">$w\in L$</span>. Because <span class="math-container">$P(M \text{ accepts } w)\geq b &gt; (b+a)/2$</span> we know from the central limit theorem that the probability <span class="math-container">$P(M_n \text{ accepts } w)$</span> tends towards 1 and therefore there exists <span class="math-container">$n_b$</span> such that for all <span class="math-container">$n\geq n_b$</span>, <span class="math-container">$P(M_n \text{ accepts } w)&gt;2/3$</span>.</p>
<p>In the same manner, for <span class="math-container">$w\not\in L$</span>, we can find <span class="math-container">$n_a$</span> such that for all <span class="math-container">$n\geq n_a$</span>, <span class="math-container">$P(M_n \text{ accepts } w)&lt;1/3$</span>. Now we see that <span class="math-container">$L$</span> is in <span class="math-container">$BPP$</span> by considering the program <span class="math-container">$M_{max(n_a,n_b)}$</span>.</p>

CC BY-SA 4.0
2022-03-15T11:18:16.747Z
Thanks for your input, it was very appreciated. I am sorry if this was was not the proper place to ask such a "standard" question. Anyway I think I understand why the probability of getting a wrong answer becomes less than 1/2, but not why the probability of getting a right answer should become greater than 1/2 (in particular if we consider the case in which both a and b are less than 1/2).
John Mayer
CC BY-SA 4.0
2022-03-15T13:45:18.457Z
Compute the probability of having more than $n×(a+b)/2$ accepting runs after $n$ runs of $M$ on $w$ depending on whether $w$ should be accepted or not (not an exact computation but the limit when $n\rightarrow \infty$ depending on whether $w$ is accepted or not).
Louis
CC BY-SA 4.0
2022-03-15T16:41:45.840Z
Thank you, but I am actually kind of lost. Suppose we have $[(a+b)/2]>1/2$. If $w \in L$  we have $p>[(a+b)/2]>1/2$, and everything is fine according to the definition of $BPP$. But if $w \notin L$ we have $p<[(a+b)/2]$ and $[(a+b)/2]>1/2$, how can this language be in $BPP$? I don't see how we can use the amplification lemma if $p$ is greater than $1/2$. Maybe it helps if I link the source from which I am trying to self-study these concepts and where I found this exercise: https://axon.cs.byu.edu/Dan/252/misc/252-ProbTMs.pdf. It is the exercise 3.2, there is also a small suggestion.
John Mayer
CC BY-SA 4.0
2022-03-16T07:06:50.390Z
This is indeed an example of amplification. I have edited my answer to make it more detailed.
Louis
CC BY-SA 4.0
2022-03-16T14:01:51.177Z
The central limit theorem was the missing piece for me. It made sense in my head that the probability would tend towards 1 after a big number of tests, but I was not able to formally explain why. Thank you for helping me, these arguments are not very easy to self-study.
John Mayer
CC BY-SA 4.0
2022-03-15T09:19:00.180Z
2022-03-16T07:06:12.870Z
2022-03-16T07:06:12.870Z
Louis
<p>Good morning everyone, I just started studying the BPP complexity class and the amplification lemma. There is one exercise about BPP that I don't understand, I hope that you can help me.</p>
<p>Let <span class="math-container">$L$</span> be a language over a finite alphabet and <span class="math-container">$M$</span> a <span class="math-container">$PPT$</span> (Probabilistic Turing Machine) such that:</p>
<ul>
<li><span class="math-container">$w \in L \rightarrow P(M\ accepts\ w) \ge b$</span></li>
<li><span class="math-container">$w \notin L \rightarrow P(M\ accepts\ w) \le a$</span></li>
</ul>
<p>where <span class="math-container">$0&lt;a&lt;b&lt;1$</span>.</p>
<p>I have to prove that the language <span class="math-container">$L$</span> is in <span class="math-container">$BPP$</span>. This should be a fairly easy exercise, but I've tried several approaches and no one was successful. To &quot;match&quot; the definition of a language in <span class="math-container">$BPP$</span>, I should have <span class="math-container">$b$</span> greater than <span class="math-container">$\frac{1}{2}$</span> and <span class="math-container">$a$</span> less than <span class="math-container">$\frac{1}{2}$</span>, but the text of the exercise does not say so, we only know that <span class="math-container">$0&lt;a&lt;b&lt;1$</span>.</p>
<p>Thank you in advance</p>

<cc.complexity-theory><complexity-classes><probabilistic-computation><probabilistic-complexity>
Question about BPP complexity class
John Mayer
# Question about BPP complexity class

(Asked by: username_0 on 2022-03-15)

Good morning everyone, I just started studying the BPP complexity class and the amplification lemma. There is one exercise about BPP that I don't understand, I hope that you can help me.

Let $L$ be a language over a finite alphabet and $M$ a $PPT$ (Probabilistic Turing Machine) such that:

* $w \in L \rightarrow P(M\ accepts\ w) \ge b$
* $w \notin L \rightarrow P(M\ accepts\ w) \le a$

where $0.

I have to prove that the language $L$ is in $BPP$. This should be a fairly easy exercise, but I've tried several approaches and no one was successful. To "match" the definition of a language in $BPP$, I should have $b$ greater than $\frac{1}{2}$ and $a$ less than $\frac{1}{2}$, but the text of the exercise does not say so, we only know that $0.

Thank you in advance

**Tags:** cc.complexity-theory, complexity-classes, probabilistic-computation, probabilistic-complexity

---

## 1 answers

### Answer by username_1 on 2022-03-15. Score: 0 | Accepted answer

This feels like a typical university exam and here is not the best place to answer this. EDIT: Here is a detailed answer.

Let us consider $M\_n$ that given $w$, runs $n$ times $M$ and returns $1$ when
the number of accepting runs is over $n\times (b+a)/2$.

Let us consider $w\in L$. Because $P(M \text{ accepts } w)\geq b > (b+a)/2$ we know from the central limit theorem that the probability $P(M\_n \text{ accepts } w)$ tends towards 1 and therefore there exists $n\_b$ such that for all $n\geq n\_b$, $P(M\_n \text{ accepts } w)>2/3$.

In the same manner, for $w\not\in L$, we can find $n\_a$ such that for all $n\geq n\_a$, $P(M\_n \text{ accepts } w)<1/3$. Now we see that $L$ is in $BPP$ by considering the program $M\_{max(n\_a,n\_b)}$.

> **Comments:**
> **username_0**: Thanks for your input, it was very appreciated. I am sorry if this was was not the proper place to ask such a "standard" question. Anyway I think I understand why the probability of getting a wrong answer becomes less than 1/2, but not why the probability of getting a right answer should become greater than 1/2 (in particular if we consider the case in which both a and b are less than 1/2).  
> **username_1**: Compute the probability of having more than $n×(a+b)/2$ accepting runs after $n$ runs of $M$ on $w$ depending on whether $w$ should be accepted or not (not an exact computation but the limit when $n\rightarrow \infty$ depending on whether $w$ is accepted or not).  
> **username_0**: Thank you, but I am actually kind of lost. Suppose we have $[(a+b)/2]>1/2$. If $w \in L$  we have $p>[(a+b)/2]>1/2$, and everything is fine according to the definition of $BPP$. But if $w \notin L$ we have $p<[(a+b)/2]$ and $[(a+b)/2]>1/2$, how can this language be in $BPP$? I don't see how we can use the amplification lemma if $p$ is greater than $1/2$. Maybe it helps if I link the source from which I am trying to self-study these concepts and where I found this exercise: https://axon.cs.byu.edu/Dan/252/misc/252-ProbTMs.pdf. It is the exercise 3.2, there is also a small suggestion.  
> **username_1**: This is indeed an example of amplification. I have edited my answer to make it more detailed.  
> **username_0**: The central limit theorem was the missing piece for me. It made sense in my head that the probability would tend towards 1 after a big number of tests, but I was not able to formally explain why. Thank you for helping me, these arguments are not very easy to self-study.  

---

