# Distributional error probability of deterministic algorithm implies error probability of randomized algorithm? Consider some problem $$P$$ and let’s assume we sample the problem instance u.a.r. from some set $$I$$. Let $$p$$ be a lower bound on the distributional error of a deterministic algorithm on $$I$$, i.e., every deterministic algorithm fails on at least a $$p$$-fraction of $$I$$.

Does this also imply that every randomized algorithm $$\mathcal{R}$$ must fail with probability $$p$$ if, again, we sample the inputs u.a.r. from $$I$$?

My reasoning is as follows: Let $$R$$ be the random variable representing the random bits used by the algorithm. \begin{align} \Pr[ \text{ \mathcal{R} fails}] &= \sum_\rho \Pr[ \text{ \mathcal{R} fails and R=\rho }] \ &= \sum_\rho \Pr[ \text{ \mathcal{R} fails} \mid R=\rho] \Pr[ R=\rho ] \ &\ge p \sum_\rho \Pr[ R=\rho ] = p. \end{align} For the inequality, I used the fact that once we have fixed $$R = \rho$$, we effectively have a deterministic algorithm.

I can’t find the flaw in my reasoning, but I would be quite surprised if this implication is true indeed. Posted on Categories proxies