Algorithms / Randomized Algorithms
Least You Need to Know: Randomized Algorithms, Error Types, and Probability Amplification
Randomized-algorithm questions usually test what is guaranteed and what is merely likely. You need to distinguish Monte Carlo from Las Vegas behavior, keep one-sided and two-sided error straight, and know why repeated independent trials can drive error down.
The least you need to know
- Monte Carlo algorithms run within a known time bound but may return a wrong answer with small probability.
- Las Vegas algorithms always return a correct answer, but their running time is random.
- One-sided error means one type of mistake is impossible.
- Independent repetition and majority voting can reduce the error probability of many randomized procedures.
- Expected running time is an average over the algorithm's random choices.
Key notation
Pr[event]
probability of an event
Monte Carlo
bounded time, possibly incorrect answer
Las Vegas
always correct, random running time
Tiny worked example
- Suppose a Monte Carlo primality filter says “composite” only when it has found a witness, but may occasionally say “probably prime.”
- That is one-sided error: false negatives are possible but false positives of the other type are not.
- Repeating the test independently makes the error probability multiply across trials.
Common mistakes
- Students often swap Monte Carlo and Las Vegas.
- Expected polynomial time is not the same as worst-case polynomial time.
- Amplification arguments usually need independence or at least carefully controlled repetition.
How to recognize this kind of problem
- The prompt talks about success probability, failure probability, or repeated trials.
- A bound is stated in expectation rather than in every execution.
- The algorithm uses randomness to avoid adversarial worst-case behavior or to sample evidence.