Algorytmy probabilistyczne - Lista 2.

ZPP \subseteq RP\cap coRP
Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO.
\Pr(t \geq a) \leq \frac{\textrm{E}(t)}{a}. ⇒ \Pr(t \geq 2E(t)) \leq \frac{1}{2}.

RP\cap coRP \subseteq ZPP
Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co-RP algorithm B.
Given an input in L, run A on the input. If it returns YES, the answer must be YES. Otherwise, run B on the input. If it returns NO, the answer must be NO. If neither occurs, repeat this step.
P(X = k) = (1-\frac 1 2)^{k-1}\frac 1 2 = 2^{-k} (X - liczba rund, rozklad geometryczny)
E(X) = 2
E(t) = t_1E(X) = \mathrm{poly}