A Monte Carlo algorithm for a decision problem has one-sided error: it never says 'yes' incorrectly but says 'no' incorrectly with probability at most 1/3. After running the algorithm k independent times on the same input, what is the best strategy and resulting error probability?
ATake a majority vote; error drops to (1/3)^k
BIf ANY run says 'yes,' output 'yes'; otherwise output 'no' — error drops to (1/3)^k for true-yes instances
CAverage the outputs; error drops to 1/(3k)
DRun once — repetition cannot help with one-sided error
With one-sided error on the 'no' side, a 'yes' output is always correct. For a true-yes instance, each run independently has probability at most 1/3 of incorrectly saying 'no.' If we output 'yes' whenever any run says 'yes,' the only way we err is if ALL k runs say 'no' on a true-yes instance, which happens with probability at most (1/3)^k. This is exponential amplification with k trials. Majority vote works for two-sided error (BPP), but for one-sided error (RP), the 'accept if any run accepts' strategy is optimal.
Question 2 True / False
Every Las Vegas algorithm can be converted to a Monte Carlo algorithm, but the reverse is not always true.
TTrue
FFalse
Answer: True
Las Vegas to Monte Carlo is straightforward: run for a time budget, output 'don't know' or a wrong answer if it doesn't finish. Monte Carlo to Las Vegas requires being able to VERIFY the answer efficiently. For decision problems in RP (one-sided Monte Carlo), you can verify 'yes' answers are correct but not 'no' answers, so conversion to Las Vegas is possible only if you can also verify 'no' (which puts you in ZPP = RP ∩ coRP). In general, without efficient verification, Monte Carlo algorithms cannot be made Las Vegas.
Question 3 True / False
The complexity class ZPP (Zero-error Probabilistic Polynomial time) equals RP ∩ coRP. This means ZPP algorithms are exactly Las Vegas polynomial-time algorithms.
TTrue
FFalse
Answer: True
ZPP is defined as the class of problems solvable by Las Vegas algorithms with expected polynomial running time. The equivalence ZPP = RP ∩ coRP follows from a clean construction: if a problem is in both RP and coRP, you have a Monte Carlo algorithm with one-sided error for 'yes' (RP) and another with one-sided error for 'no' (coRP). Run both alternately; at least one gives a definitive answer each round. The expected number of rounds to get a definitive answer is constant, yielding a Las Vegas algorithm. Conversely, any ZPP algorithm can be truncated to give RP and coRP algorithms.
Question 4 Short Answer
Explain the practical implications of the Las Vegas vs Monte Carlo distinction when composing randomized subroutines inside larger algorithms.
Think about your answer, then reveal below.
Model answer: Las Vegas subroutines compose trivially because each call produces a guaranteed-correct result regardless of running time variability. Monte Carlo subroutines are more delicate: if an algorithm makes m calls to a Monte Carlo subroutine with error probability epsilon each, the overall error probability can be as high as m*epsilon by a union bound. To keep overall error below delta, each subroutine call needs error at most delta/m, which requires O(log(m/delta)) repetitions per call. This amplification cost multiplies with the number of calls, making Monte Carlo composition more expensive. In practice, this means algorithms that call randomized subroutines many times (e.g., in loops) strongly prefer Las Vegas subroutines when available.
The union bound composition cost is why BPP (two-sided Monte Carlo) algorithms can still be composed polynomially — logarithmic amplification is cheap. But it explains why Las Vegas algorithms are preferred when available: zero error composes without any overhead.