= Error reduction for a randomized algorithm
Independent repetitions reduce a randomized algorithm's error probability while preserving polynomial running time.
The combining rule depends on the error orientation. For <one-sided error> with false acceptance <probability> at most $p<1$, reject as soon as any trial rejects and accept only if every trial accepts. For $k$ <independent> trials on the same fixed negative <input>, false acceptance has <probability> at most $p^k$. The protected positive <inputs> still always accept. If false rejection is the possible mistake instead, accept as soon as any trial accepts. This uses the decisive answer rather than a majority vote.
For constant $p<1$, $k$ grows only logarithmically in $1/\varepsilon$ to achieve error at most $\varepsilon$. A polynomial number of trials preserves a <polynomial-time algorithm>'s running-time bound. Independence matters: repeating one answer, or evaluating at the same random point each time, supplies no new evidence. The <independent repetition of a polynomial identity test> gives an exact $25$-outcome example.
Back to article page
