ZPP ⊆ RP

Inclusion · folklore

Statement

ZPP $\subseteq$ RP — folklore.

Sketch

Replace the output $?$ by reject: the machine never accepts a no-instance and accepts a yes-instance with probability at least $1/2$. For the expected-polynomial-time formulation, first truncate the run at twice the polynomial bound on its expected running time and output $?$ on timeout; by Markov’s inequality this happens with probability at most $1/2$, and every non-$?$ answer is correct.

Notes

• Replacing $?$ by accept instead gives $\mathbf{ZPP}\subseteq \mathbf{coRP}$, and $\mathbf{ZPP}=\mathbf{RP}\cap \mathbf{coRP}$ — Gil77.