Suppose we have a BPP algorithm $A$ s.t. its running time is random and is $O(n^2)$ in expectation. How do we create a new BPP algorithm $B$ to solve the same problem s.t. it has deterministic running time $O(n^2)$?
My effort: Denote the running time of $A$ as $T$. Suppose $E(T)\leq T(n)=O(n^2)$.
But I just proved that this cannot be a BPP algorithm for any $q$... Any hint please?
Derandomization is the process in which a randomized algorithm is converted to an equivalent deterministic algorithm. This is not what this exercise is asking you to do. The algorithm $B$ is still randomized – only its running time is deterministic.
Suppose that $A$ decides the problem $L$, in the following sense: if $x \in L$ then $\Pr[A(x) = 1] \geq 2/3$, and if $x \notin L$ then $\Pr[A(x) = 0] \geq 2/3$. Moreover, there is a function $f(n) = O(n^2)$ such that the expected running time of $A$ on $x$ is always at most $f(|x|)$. We want to construct a new algorithm $B$ with the same behavior regarding to $L$, and with the following additional property: there is a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$.
Suppose that $f(n) = Cn^2$, and consider your solution with $K = 3C$ and $q=1/2$. If we're careful, then there will exist a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$. What about the other property?
Suppose that $x \in L$ has size $|x|=n$. The expected running time of $A$ on $x$ is at most $f(n) = Cn^2$, and so $A$ terminates within $Kn^2$ steps with probability $p \geq 2/3$. If this happens, the probability that $B$ outputs $1$ is at least $2/3$. Otherwise, the probability that $B$ outputs $1$ is $1/2$. In total, $$\Pr[B(x) = 1] \geq p \cdot \frac{2}{3} + (1-p) \cdot \frac{1}{2} = \frac{1}{2} + p \cdot \frac{1}{6} \geq \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{6} = \frac{11}{18} > \frac{1}{2}.$$ Similarly, if $x \notin L$ then $\Pr[B(x) = 0] \geq 11/18$. This is almost what we want – we want $11/18$ to be replaced by $2/3$.
In order to enhance the success probability ("error reduction"), we need to run $A$ several times and take a majority vote. By running $A$ enough times and by increasing the value of $K$, we get drive the error probability of $B$ down to any positive constant. Details left to you.
