Prove that $BPP^{BPP} = BPP$

Question

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.

Answer 1

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

• Covvar: but aren't the errors coupled with each other? I mean, $E$ is dependent on $E'$
• Covvar: i.e. an error of $M'$ could lead to a correct answer of $M$