# Randomized Algorithms: High-Probability vs. Expectation

Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation. My question is motivated by the definition of a randomized $$\alpha$$-approximation algorithm given here, namely that it is a polynomial-time algorithm that produces a solution within $$\alpha$$ of OPT in expectation or with high probability. I also found that the first few pages of this source provides some good insight into the high-probability vs. expectation approaches, but I still have questions.

• Can you always transform an algorithm that achieves an $$\alpha$$-approximation in expectation to one that achieves this with high probability, and vice versa? (Ostensibly by rerunning the algorithm multiple [a polynomial number] of times.)
• If not, is one harder than the other to obtain? (I would think that if you fix $$\alpha$$, a high-probability algorithm would always be harder to find/less likely to exist. Or maybe you can always find one, but the approximation ratio will become worse.)

Thanks for the help!

If you have an algorithm that is an $$\alpha$$-approximation in expectation, then you can construct an algorithm that is a $$(1+\epsilon)\alpha$$-approximation with high probability, for any $$\epsilon>0$$. In particular, by Markov's inequality, if you run the algorithm, then with probability at least $$1-1/(1+\epsilon)$$ it will output a $$(1+\epsilon)\alpha$$-approximation. So, if you run the algorithm about $$(c \log n)/\epsilon$$ times and keep the best output among all of those trials, with probability about $$1-1/n^c$$ you will find a $$(1+\epsilon)\alpha$$-approximation.
If you have an algorithm that is an $$\alpha$$-approximation with high probability, there are no guarantees about the expectation. It's possible that with very small probability (probability $$1/n^c$$), it outputs an extremely bad solution (one with exponentially large approximation factor), and in all other cases it outputs an $$\alpha$$-approximation. In this case, the expected value of the approximation factor will be very large, even though it has a very small probability to output such a bad solution.
• Thank you for this fantastic answer! I'm probably missing something obvious, but I am stuck at checking the $(c \log n) / \epsilon$. The probability of failure in one trial is at most $\frac{1}{1 + \epsilon}$, so we want to show that $$\left( \frac{1}{1 + \epsilon} \right)^{(c \log n) / \epsilon}$$ is small, i.e., about $1/n^c$. Clearly we are allowed to upper bound the expression. At first I was thinking you could apply $1 + \epsilon \le e^\epsilon$ in the denominator, but this would make the entire expression smaller, so it is a no go. What am I missing? – kanso37 Jul 13 at 5:03
• @kanso37, When $\epsilon$ is small, $1/(1+\epsilon)\approx 1-\epsilon$, and $(1-\epsilon)^{1/\epsilon} \approx 1/e$. You should be able to take it from there. I haven't thought about maximization algorithms. The answer might be different, if solutions have non-negative value. – D.W. Jul 13 at 6:02