# Prove that $BPP^{BPP} = BPP$

Prove that $BPP^{BPP} = BPP$.

Obviously $BPP\subseteq BPP^{BPP}$. So we're left with proving $BPP^{BPP} \subseteq BPP$. Let's consider $L\in BPP^{BPP}$. Then, there's a PTM $M$ to decide $L$ for some $BPP(\alpha, \beta)$ which uses an oracle for some language $O\in BPP$. $O$ also has a $PTM\in BPP$, let's denote it $M_o$. So we could create $M'$, a PTM which behaves exactly as $M$, but everytime $M$ uses the oracle, it simulate $M_o$ on the given input for the oracle.

Now, I want to show that $M\in BPP$. By definition, $BPP=BPP(1/3, 1/3)$, so every time $M$ calls $M_o$ it takes a probabilistic risk basing a deciion upon $M_o$ answer.

We've learned in class that $BPP = BPP(1/3, 1,3) = BPP\left(\frac{1}{3^n}, \frac{1}{3^n} \right)$ and I think I shall explain that even though $M_o$ may return false answers, $M_o$ is still in $BPP$.

Can you help me with doing that?

Thanks

EDIT:
Basically, I want to give a lower bound for the probability of $M$, answering correctly. Let's assume that $M$ queries the oracle $n^c$ times for some $n\in\mathbb{N}$. I think the lower bound is $\frac{1}{3^{n^c}}$.

My explanation is that we're assuming the worst case. That is, if the oracle is returning a false answer then we are returning a false answer.

Is that right?

EDIT2
I'm not sure it's $100\%$ correct, since I didn't take into account the probabilistic behavior of $M$ itself.

## migrated from math.stackexchange.comMay 27 '17 at 12:33

This question came from our site for people studying math at any level and professionals in related fields.

Here's a sketch: you seem to be on the right track. Let $L\in BPP^{BPP}$ be decided by a BPP machine $M$ that makes queries to an oracle $A\in BPP$ decided by a $BPP$ machine $M'$. Let $E$ be the error for $M$, $E'$ the error for $M'$ (that is, the probability that the BPP machines fail is at most $E, E'$). We will choose $E, E'$ appropriately via error reduction.
Now, fix a string $z$ to use as randomness for all queries to $M'$. There are at most polynomially many queries to $M'$, say at most $|x|^k$, since $M$ is a ppt TM. Thus, $$\operatorname{Pr}[\text{an error occurs in some query to } M']\le |x|^k\cdot E'$$ So the overall probability of error by $M$ in deciding $L$ is at most $|x|^k\cdot E' + E$, so if we choose $E=\frac{1}{6}$ and $E'=\frac{1}{6|x|^k}$ (which we may do by the standard BPP error reduction), we get an overall probability of error $\le\frac{1}{3}$, so the procedure described is a $BPP^P\subseteq BPP$ procedure.
By the same proof we have the more general statement that $BPP^{BPP^A}\subseteq BPP^A$.
• but aren't the errors coupled with each other? I mean, $E$ is dependent on $E'$ – Covvar Jun 4 '17 at 10:00
• i.e. an error of $M'$ could lead to a correct answer of $M$ – Covvar Jun 4 '17 at 10:00