question archive Recall that a Monte Carlo algorithm is p-correct if it returns a correct answer with probability at least p, whatever the instance considered
Recall that a Monte Carlo algorithm is p-correct if it returns a correct answer with probability at least p, whatever the instance considered
Subject:Computer SciencePrice: Bought3
Recall that a Monte Carlo algorithm is p-correct if it returns a correct answer with probability at least p, whatever the instance considered. The potential difficulty is that even though a p-correct algorithm returns a correct answer with high probability when p is large, it could happen that one systematic wrong answer is returned more often than any given correct answer. In this case, amplification of the stochastic advantage by majority voting would decrease the probability of being correct! Show that if algorithm MC is 75%-correct, it may happen that MC3 is not even 71%-correct, where MC3 returns the most frequent answer of three calls on MC, as in Section 10.6.4. (Ties are broken arbitrarily.) For what value of k could RepeatMC(., k) be less than 50%-correct even though MC is 75%-correct?
