Suppose that you have a randomized algorithm that estimates some quantity. It can err by providing...

 

Transcribed Image Text:

Suppose that you have a randomized algorithm that estimates some quantity. It can err by providing an estimate that is too high or too low, which we will refer to as a bad estimate. However, with probability at least 2/3 (taken over the algorithm's internal randomness), it provides a good estimate, i.e., one that is in the desired range. Given any & (0, 1/3), how can you improve the algorithm so that it errs with probability at most d? Hint: How about taking the median of a number of independent estimators? How can you bound the probability that half or more of the estimates are outside of the desired range? Consider an experiment in which an event & occurs with probability p. Why does it suffice to run the experiment independently (1/p) times to see & occur at least once with probability 1/2? Hint: What is the probability that you repeat the experiment k times and it does not occur? You may find the following inequality useful: 1 - x e- for all x R. Suppose that you have a randomized algorithm that estimates some quantity. It can err by providing an estimate that is too high or too low, which we will refer to as a bad estimate. However, with probability at least 2/3 (taken over the algorithm's internal randomness), it provides a good estimate, i.e., one that is in the desired range. Given any & (0, 1/3), how can you improve the algorithm so that it errs with probability at most d? Hint: How about taking the median of a number of independent estimators? How can you bound the probability that half or more of the estimates are outside of the desired range? Consider an experiment in which an event & occurs with probability p. Why does it suffice to run the experiment independently (1/p) times to see & occur at least once with probability 1/2? Hint: What is the probability that you repeat the experiment k times and it does not occur? You may find the following inequality useful: 1 - x e- for all x R.