Engineering / Mathematics — Probabilistic Algorithms
Reducing the Error Probability
Amplifying the success probability of a randomised algorithm by independent repetition, for one-sided and two-sided error.
Executive summary
Repeating a randomised algorithm with fresh randomness and combining the results reduces the error probability rapidly. For one-sided error it falls geometrically; for two-sided error a majority vote is required and the analysis is a concentration bound.
In both cases the cost is linear in the repetition count while the error falls exponentially, which is an excellent trade.
Learning objectives
- Amplify a one-sided error algorithm and bound the residual error.
- Apply majority voting to two-sided error.
- Choose a repetition count for a target error level.
01One-sided amplification
Geometric error reduction
If a one-sided test errs with probability at most ε per trial, then t independent trials err with probability at most ε^t.
Independence across trials is what allows the probabilities to multiply, and it requires fresh random bits each time. Reusing randomness invalidates the bound entirely.
| Rounds t | Residual error, ε = 1/4 | Bits of confidence |
|---|---|---|
| 1 | 2^{−2} | 2 |
| 10 | 2^{−20} | 20 |
| 32 | 2^{−64} | 64 |
| 64 | 2^{−128} | 128 |
02Two-sided amplification
When either answer may be wrong, no single trial is conclusive. Running t trials and taking the majority succeeds provided fewer than half err.
If each trial is correct with probability 1/2 + δ, the expected number of correct answers exceeds half by δt, and a concentration bound shows the majority is wrong with probability exponentially small in δ²t.
P(majority wrong) ≤ exp(−2δ²t)03Choosing the repetition count
Fix the error budget
Typically 2^{−64} or 2^{−128}, matched to the surrounding system's security level.
Identify the error type
One-sided allows a direct geometric calculation; two-sided needs the concentration bound.
Solve for t
For one-sided, t = log(1/target)/log(1/ε). For two-sided, t = ln(1/target)/(2δ²).
Verify independence
Confirm fresh randomness per round; without it the analysis does not apply.
Amplification is cheap because cost grows linearly while error falls exponentially. Reaching a 2^{−128} error from a one-quarter per-round rate costs only 64 rounds, which is negligible against the cost of the surrounding computation.
04Frequently asked questions
Can amplification be done with fewer random bits?
Yes. Randomness-efficient amplification using expander walks achieves nearly the same error reduction with far fewer bits than independent repetition, which matters when randomness is a scarce resource.
Does amplification help a Las Vegas algorithm?
There is no error to reduce, since the answer is always correct. Repetition there addresses running time variance, and the equivalent technique is restarting after a time bound.
Why is the two-sided case so much worse?
Because no single trial settles anything, so the argument must show the aggregate lands on the right side of a threshold. That is a concentration statement, inherently weaker than multiplying conclusive failures.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 155-156.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.