# Amplification for Randomized Algorithms

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!