Randomized Algorithms
Randomized algorithms use random choices during execution to gain speed or simplicity, at the cost of some uncertainty.
Using coin flips
A randomized algorithm makes decisions based on random values as it runs. Randomness can make an algorithm faster, simpler, or able to avoid worst-case inputs that an adversary might otherwise exploit. The output or the running time then depends on the random choices, not just the input.
Two kinds
- Las Vegas: always correct, running time is random (e.g. randomized quicksort)
- Monte Carlo: running time is bounded, output is correct with high probability
Error you can drive down
A Monte Carlo algorithm with, say, a 1-in-3 chance of error can be run many times and the majority answer taken. Independent repetitions make the failure probability shrink exponentially, so you can reach any confidence you like, such as an error smaller than the chance of a hardware fault.
A worked example: primality
The Miller-Rabin test checks if a number is prime by picking random witnesses. A composite number is exposed by most witnesses, so a few random trials make a false "prime" verdict astronomically unlikely. This was the practical primality test for decades before a deterministic polynomial method was found.
Why randomness helps
Random choices defeat worst-case inputs by making the algorithm's behavior independent of any fixed adversarial arrangement. Randomized quicksort has expected O(n log n) time on every input, because the pivot is chosen randomly rather than from a position an adversary could target.
The complexity class BPP
BPP (bounded-error probabilistic polynomial time) is the class of problems solvable by a Monte Carlo algorithm in polynomial time with error bounded below one half. Whether BPP equals P, meaning randomness adds no fundamental power, is widely believed true but unproven, and is distinct from the quantum class BQP.