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 the instances in $I$. [Edit: For a given instance $s \in I$, we use $P(s)$ to denote the set of correct solutions. We say that a deterministic algorithm $A$ fails on an instance $s$, if the output produced by $A$ given $s$ is not in $P(s)$.]
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.
