Specifically, their yes answers are always correct. On the other hand, their no answers might sometimes be correct and sometimes wrong. In general, however, probabilistic programs might err on more than one kind of an answer. In such a case, the answer can be arrived at by taking the majority of answers obtained in repeated computations on the given instance. The following lemma analyzes the probability of error in repeated computations to establish an answer by absolute majority.
Proof Let P, x, y, and e be as in the statement of the lemma.
By definition, The probability of having the answer y at and only at the i 1 st, . . . In general, we are interested only in probabilistic programs which run in polynomial time, and which have error probability that can be reduced to a desired constant by executing the program for some polynomial number of times. The following theorem considers the usefulness of probabilistic programs that might err.