Continue on: Prove that $BPP^{BPP} = BPP$

Question

regarding the following post: Prove that $BPP^{BPP} = BPP$

Let $L\in BPP^{BPP}$, by definition $BPP^{BPP} =\bigcup_{O\in BPP}BPP^O $, therefore there exists a language $A\in BPP$ such that $L\in BPP^{A}$.
This means that there exists a $\mathsf{PTM} $ $M^{A}(x,r)$ such that $\mathbb{P}_{r}(M(x,r)\neq L(x))\leq \frac{1}{3}$, and $M^A$ runs in polinomial time.
In addition, since $A\in BPP_{[\frac{1}{3},\frac{2}{3}]} \subset BPP_{[2^{-n},1-2^{-n}]}$, there exists a $\mathsf{PTM} $ $M'(x,r)$ such that $\mathbb{P}_{r}(M'(x,r)\neq L(x))\leq 2^{-n}$, and $M'$ runs in polinomial time.
I defiened a $\mathsf{PTM}$ $N$, that on input $x$ does the following:
Simulate $M^A$ on $x$ and every time we need to do an orcale quarey $\alpha_i$, we would simulate $M'$ on $\alpha_i$ and the answer to the query would be the answer of $M'$.

I understand why $N$ runs in polynomial time, but I was stuck in the probabilistic analysis.
This is what I have so far:
If $x\in L$ then $N$ answer correctly iff $M^A$ answer correctly and $M'$ answer correctly about every query, therefore I got:
$\mathbb{P}_{r}(N(x,r)= 1)= \mathbb{P}_{r}(M(x,r)= 1)\mathbb{P}_{r}(\forall i, M'(\alpha_i,r)$is correct$)\geq \frac{2}{3} \prod_{i}(1-\frac{1}{2^{|\alpha_i|}}) $

How can I prove from here that $\mathbb{P}_{r}(N(x,r)= 1) \geq \frac{2}{3}$?
Would appreciate your help:)

• Yuval Filmus: (1) Replace $|\alpha_i|$ with $n,ドル (2) use the union bound.
• Emma: 1) Why can I say that $|\alpha_i| \geq n, \forall i$? I know that $|\alpha_i| =O(n^c)$ for some $c\in \mathbb{N},ドル but do I know it's length is at least n? 2) Why can I use the union bound? $\forall i$ doesn't mean intersection?
• Yuval Filmus: You cannot say it. But you don't have to say it. You can reduce the error probability to 2ドル^{-n}$ even if $|\alpha_i|$ is small.
• Emma: I'm not sure I fully understand why, can you please elaborate? And about the union bound- is it because $\mathbb{P}_{r}(\forall i, M'(\alpha_i,r)$is correct$)=1- \mathbb{P}_{r}(\exists i, M'(\alpha_i,r)$is wrong$)\geq 1-\Sigma_{i}\mathbb{P}_{r}( M'(\alpha_i,r)$is wrong$)$?
• Yuval Filmus: You have a BPP algorithm with error probability 1ドル/3$. By repeating it polynomially many times, you can reduce the error probability to 2ドル^{-n},ドル say. Since you are making only polynomially many queries, the union bound shows that you will get an error in any of your BPP oracle calls is extremely small.

Answer 1

Your BPP algorithm makes polynomially many queries to the BPP oracle, and assuming that all these queries are answered correctly, has error probability at most 1ドル/3$, say.

In order to simulate this algorithm without appealing to the oracle, we replace each oracle call with the BPP algorithm itself. By repeating the BPP algorithm polynomially many times, we can reduce the error probability of each oracle call to 2ドル^{-n}$, say. The union bound then implies that all oracle calls are answered correctly with probability 1ドル-o(1)$, and so the entire algorithm has error probability at most 1ドル/3+o(1)$, which suffices to put the language in BPP.