Having difficulty with a homework problem, so just looking for some guidance.
For a function $f(x)$ in BPP defined on strings x in $\Sigma^{*}$, we know there is a constant c > 0 and a randomized algorithm A(x, R) with running time bounded by $|x|^{c}$ with the following property: For each x let R be a random string of length $|x|^c$, then $P( A(x, R) \neq f (x)) < 1/3$.
Show that there is also a polynomial algorithm $B(x, R)$ that uses the same common random bit sequence R for all strings x of the same length: $$P\{\exists x \in \Sigma^{n} B(x, R) \neq f (x)\} < \frac{1}{3}. $$
In other words, show the probability that there is a string x of length n where $B(x, R) \neq f(x) < \frac{1}{3}$. We're given a hint: First drive down the failure probability to exponentially small, using repetition, then apply the union bound.
I understand how to reduce the failure probability to be insignificant with repetition, as this is a BPP problem. However, I'm not sure where or how I'd apply the union bound.
(hints only)
Any "$\exists$" corresponds to a union. The event "$\exists x(\text{x is bad})$" is the union over $x$ of the events "$\text{x is bad}$". The relevant union bound is therefore
$$\mathbb{P}[\exists x\in\Sigma^n \cdot (B(x,R)\neq f(x))]\leq \sum_{x\in\Sigma^n}\mathbb{P}[B(x,R)\neq f(x)]$$
You need to bound this. It might be useful to first bound it by $|\Sigma|^n \cdot \max_{x\in\Sigma^n}\mathbb{P}[B(x,R)\neq f(x)].$