Amplification for Randomized Algorithms

Question

I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms.

---

Amplification for randomized algorithms:
Given a randomized algorithm with time complexity $f(n)$ and error probability $\frac{1}{4}$, show there is an algorithm that solves the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\varepsilon}\right)\right)$ run time, and error probability of $\varepsilon$, for a given $\varepsilon>0$.

I managed to show this running the original algorithm $k$ times, and choosing by majority vote the answer. Using Multiplicative Chernoff Bound (Which I've proven as well), I've shown $k\geq O\left(ln\left(\frac{1}{\varepsilon}\right)\right)$ gives us the required results.

---

Now I'm trying to do the same for approximation algorithms.

Amplification for randomized approximation algorithms:
Given a randomized approximation algorithm that returns an $\varepsilon$-additive-approximation with a probability of $\frac{3}{4}$, with run time complexity of $f\left(n\right)$, show there is an algorithm that returns an $\varepsilon$-additive-approximation with a probability of 1ドル-\delta$, for the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\delta}\right)\right)$ run time, for a given $\delta>0$.

The first thing that comes to my mind, is use a similar approach as before - run the original algorithm $k$ times, but this time instead of using majority vote, return the average.

I have to somewhow find a $k\geq O\left(ln\left(\frac{1}{\delta}\right)\right)$ such that $\mathbb{P}\left[\left|OPT-\frac{1}{k}\underset{i=1}{\overset{k}{\sum}}X_{i}\right|>\varepsilon\right]<\delta$.

I tried using the triangle inequality, then using union bound, but this doesn't lead me to being able to use Chernoff. In order to use Chernoff, I thought of defining an indicator random variable for each run of the original algorithm, stating if the result - $X_{i}$ is bad (that is, if $\left|X_{i}-OPT\right|>\varepsilon$), but this is where I get stuck.

Would appreciate any help. Thanks!

Answer 1

Use the median instead of the mean. The median can only be bad if more than half the samples are bad.

The problem with the mean is that the mean could be bad from a lot of the samples being a little bit bad, or from a few of the samples being really bad. However, in general, you don't know the probabilities of different degrees of sample badness; just the probability of bad-versus-good.

• Idra: That is indeed what I was missing. Managed to prove it using the Median. Thanks a lot!
• Idra: I do wonder though why using the average didn't work out as average is usually used for these kind of things and has lots of nice qualities. Is it possible to show this using average?
• David Richerby: I'm not sure it's possible with the mean, in general. Usually, all you know is that a single sample is bad with at most the given probability. Now, the mean of a set of samples could be bad because lots of the samples were a bit bad, or because one sample was really really bad, but, in general, you don't know the probabilities of different degrees of badness so you can't begin to bound the probability that the mean is bad.
• Idra: That makes perfect sense and helped sort out everything in my head :P Appreciate the help!
• David Richerby: You're welcome! Glad it was useful for you. (I added the explanation of why the mean doesn't work to the answer.)