Let be a randomized algorithm computing a function with Pr(() = ()) ≥ 1/3 for every argument of . Assume that one is aware of the fact that Pr(() = ) ≤ 1/4 for any wrong result (i.e., that the probability of computing any specific wrong result is at most 1/4). Can this knowledge be used to design a useful randomized algorithm for ? If so, describe your randomized algorithm and give the analysis of correctness. If not, explain why.
Yes, this knowledge can be used to design a useful randomized algorithm for . One way to utilize this information is to repeat the randomized algorithm multiple times and take a majority vote of the results.
Algorithm:
1. Run the randomized algorithm times on input .
2. Let be the set of results obtained from the executions.
3. Output the most common result in .
Analysis:
Let be the true output of on input . Let be the set of wrong results obtained from the executions. Then, the probability of obtaining a wrong result in a single execution is at most 1/4. Therefore, the probability of obtaining a wrong majority vote is at most 1/4 as well.
On the other hand, the probability of obtaining a correct result in a single execution is at least 1/3. Therefore, the probability of obtaining a correct majority vote is at least 1/3.
By repeating the algorithm multiple times (e.g., times), we can further increase the probability of obtaining the correct majority vote. The analysis above holds for any arbitrary wrong result, so the majority vote algorithm guarantees a high probability of correctness.