Difficulty: Intermediate | Prerequisites: basic probability (expected value, independence), complexity classes P and NP, big-O notation.
Randomized algorithms sit at the intersection of algorithm design and probability theory. This section of EECS 376 asks: what happens when we let an algorithm flip coins? The payoff is often a simpler or faster solution to a hard problem, but the cost is uncertainty, either in runtime or in correctness. You should already be comfortable with basic probability, expected value, the definitions of P and NP, and polynomial-time reductions. If those feel shaky, revisit Sections 7 and 8 before diving in here.
Randomized algorithms use coin flips (randomness) to solve problems. Las Vegas algorithms are always correct but have unpredictable runtimes. Monte Carlo algorithms run in guaranteed time but may give the wrong answer. You can boost a Monte Carlo algorithm's accuracy by repeating it independently, and the complexity classes ZPP, RP and coRP capture which problems each type can solve in polynomial time.
Randomized algorithm
An algorithm that uses random bits (coin flips) as part of its logic, introducing either runtime uncertainty or correctness uncertainty.
In simple terms, the algorithm gets to roll dice while it runs, and the outcome of those rolls affects what it does.
Las Vegas algorithm
A randomized algorithm whose output is always correct, but whose running time is a random variable. The time complexity holds only in expectation.
Think of it as: you always get the right answer, but you cannot predict exactly how long it will take.
Monte Carlo algorithm
A randomized algorithm with a deterministic (guaranteed) running time, but with some probability of producing an incorrect output.
In simple terms, it finishes on schedule every time, but it might be wrong.
One-sided error randomized algorithm
A Monte Carlo algorithm that can only err in one direction: it either never gives false positives or never gives false negatives, but not both.
Think of it as: the algorithm can be wrong, but only in one specific way.
One-sided error, no false positives
If x is not in the language L, the algorithm always rejects. If x is in L, the algorithm accepts with probability at least c. It never mistakenly says "yes" to something that should be "no."
One-sided error, no false negatives
If x is in the language L, the algorithm always accepts. If x is not in L, the algorithm rejects with probability at least c. It never mistakenly says "no" to something that should be "yes."
Error amplification
The technique of repeating a randomized algorithm independently multiple times to drive the probability of error down to any desired level. For one-sided error algorithms, k > ln(1/e) / c repetitions suffice to bring the error below e.
Atlantic City algorithm (optional)
A randomized algorithm that returns a numeric value which, with high probability, is within e of the true answer. You amplify accuracy by taking the median of multiple independent runs.
ZPP (Zero-error Probabilistic Polynomial time)
The complexity class of decision problems solvable by Las Vegas algorithms running in expected polynomial time.
RP (Randomized Polynomial time)
The complexity class of decision problems solvable by one-sided error Monte Carlo algorithms with no false positives, running in polynomial time.
coRP
The complexity class of decision problems solvable by one-sided error Monte Carlo algorithms with no false negatives, running in polynomial time. It is the complement class of RP.
Always produce the correct output.
The trade-off is unpredictable runtime: the time complexity holds in expectation, not in the worst case.
Canonical example: Randomized QuickSort.
The pivot is chosen uniformly at random.
Expected runtime: O(n log n).
Worst-case runtime: O(n^2), but this is astronomically unlikely with random pivots.
Always terminate within a guaranteed time bound.
The trade-off is that the output may be incorrect with some probability.
Subcategories depend on which direction the error can go.
If the true answer is "no" (x not in L), the algorithm always says "no."
If the true answer is "yes" (x in L), the algorithm says "yes" with probability at least c.
The only possible mistake: saying "no" when the real answer is "yes" (a false negative).
If the true answer is "yes" (x in L), the algorithm always says "yes."
If the true answer is "no" (x not in L), the algorithm says "no" with probability at least c.
The only possible mistake: saying "yes" when the real answer is "no" (a false positive).
The core idea: run the algorithm k times with fresh, independent randomness each time.
For a no-false-positives algorithm: accept if any run accepts, reject only if all k runs reject.
The probability that all k runs get it wrong drops exponentially: Pr[all reject when x in L] <= (1 - c)^k <= e^(-ck).
To make the error probability less than any target e, set k > ln(1/e) / c.
If the original algorithm runs in polynomial time and c and e are constants, the amplified version still runs in polynomial time.
Return a numeric value that is, with high probability, within e of the true value.
Similar in spirit to polling or sampling.
Amplification strategy: take the median of multiple independent runs.
ZPP = problems with Las Vegas algorithms running in expected polynomial time.
RP = problems with one-sided error (no false positives) Monte Carlo algorithms in polynomial time.
coRP = problems with one-sided error (no false negatives) Monte Carlo algorithms in polynomial time.
Known inclusions:
P is a subset of ZPP, which is a subset of RP, which is a subset of NP.
P is a subset of ZPP, which is a subset of coRP, which is a subset of coNP.
ZPP = RP intersect coRP.
The big open question: are any of these inclusions strict? Most complexity theorists believe P = ZPP = RP = coRP, meaning randomness does not add fundamental power for decision problems.
Error amplification bound (no false positives)
Given a one-sided error algorithm A with Pr[A accepts x | x in L] >= c, running it k times independently:
\Pr[B \text{ rejects } x] \leq (1 - c)^k \leq e^{-ck}To guarantee error below e:
k > \frac{\ln(1/\varepsilon)}{c}Complexity class relationships
P \subseteq ZPP \subseteq RP \subseteq NPP \subseteq ZPP \subseteq coRP \subseteq coNPZPP = RP \cap coRPRandomized QuickSort is the default sorting algorithm in many standard libraries precisely because its expected O(n log n) performance is excellent in practice, even though a deterministic worst case exists. Randomised primality testing (Miller-Rabin) is a Monte Carlo algorithm used everywhere in cryptography: it is fast and its error probability can be driven below any threshold through repetition. Hash tables rely on random-like hash functions, and the birthday-paradox analysis of collisions is a direct application of the probability tools covered here.
Students often confuse Las Vegas and Monte Carlo. Remember: Las Vegas = always correct, variable time. Monte Carlo = fixed time, possibly incorrect. The names are worth drilling.
"One-sided error" does not mean the algorithm is wrong half the time. It means errors can only occur in one direction (false positives or false negatives, never both).
Error amplification does not require the original success probability c to be large. Even a tiny constant c works; you just need more repetitions (k scales as 1/c).
Students sometimes think repeating a Monte Carlo algorithm and taking the majority vote works for one-sided error. For no-false-positives algorithms, the correct strategy is to accept if any run accepts. Majority vote is the strategy for two-sided error algorithms, which are a different category.
Be able to classify a given algorithm as Las Vegas or Monte Carlo, and if Monte Carlo, identify whether it has one-sided or two-sided error.
Know the error amplification proof inside out. Exams commonly ask you to determine the number of repetitions k needed to achieve a target error bound.
Know the complexity class inclusions (P, ZPP, RP, coRP, NP, coNP) and the relationship ZPP = RP intersect coRP.
Understand why amplification preserves polynomial runtime when c and e are constants.
True or false: A Las Vegas algorithm may produce an incorrect answer. (False. Las Vegas algorithms are always correct.)
True or false: A Monte Carlo algorithm with no false positives will never accept an input that is not in the language. (True.)
Fill in the blank: To amplify a one-sided error algorithm with success probability c to error less than e, you need k > ____. (ln(1/e) / c)
True or false: ZPP is a subset of both RP and coRP. (True. In fact, ZPP = RP intersect coRP.)
True or false: It is proven that P is strictly contained in RP. (False. It is an open question; most researchers believe P = RP.)
Q: Suppose algorithm A is a one-sided error algorithm with no false positives for language L, and Pr[A accepts x | x in L] >= 1/4. How many independent runs are needed to bring the error probability below 1/1000?
A: We need k > ln(1000) / (1/4) = 4 ln(1000). Since ln(1000) is roughly 6.91, we need k > 27.6, so k = 28 runs suffice.
Q: Randomized QuickSort is which type of randomized algorithm, and why?
A: It is a Las Vegas algorithm. It always produces a correctly sorted array (the output is always correct), but its runtime is random. In expectation it runs in O(n log n), though the worst case is O(n^2).
Q: Explain why ZPP = RP intersect coRP.
A: A ZPP algorithm always gives the correct answer (like Las Vegas) in expected polynomial time. If a problem is in both RP and coRP, you have one algorithm that never gives false positives and another that never gives false negatives, both in polynomial time. Running both and combining results gives an always-correct algorithm with expected polynomial runtime, which is exactly ZPP.
Q: An algorithm A for language L has the property that if x is in L, A always accepts, and if x is not in L, A rejects with probability at least 2/3. Which complexity class does L belong to?
A: L is in coRP. The algorithm has no false negatives (it always accepts members of L) and has one-sided error on the rejection side, running in polynomial time.
This material connects directly to the P vs NP question: if P = RP, then randomness gives no extra power for decision problems, which would be a major result in complexity theory. The probability tools here (independence, expected value, amplification) reappear in the next section on Markov's inequality and later on Chebyshev's inequality, both of which are used to analyse randomized algorithms more precisely. Error amplification by repetition is also the underlying idea behind the BPP complexity class (two-sided error), which the course covers in a later section.
randomized algorithms, Las Vegas algorithm, Monte Carlo algorithm, one-sided error, two-sided error, false positive, false negative, error amplification, probability amplification, ZPP, RP, coRP, BPP, randomized QuickSort, random pivot, probabilistic polynomial time, expected polynomial time, complexity classes, EECS 376, foundations of computer science, University of Michigan