2
$\begingroup$

I'm studying randomized algorithms and I sometimes come across results like

(1) The algorithm has an expected $O(f(n))$ cost.

and

(2) With constant probability, the cost is bounded by $O(f(n))$.

I'm perfectly fine with statements like (2), but I'm puzzled to what extent a statement like (1) is useful: For certain probability distributions of a random variable, the expected value itself occurs with less than constant probability; for other distributions, it occurs with $1-1/n$ probability. Of course, in many cases, (1) is extended via concentration bounds to show high probability, but in cases where this isn't done, it doesn't seem that a statement on the "expected cost" lets us derive any implications on the actual performance of the algorithm, right?

$\endgroup$
2
$\begingroup$

If you have a cost of $1$ with probability one half and $0$ with probability one half, you never reach the expected cost of $\frac{1}{2}$.

But what the expected cost gives you is the average of costs. If you repeat the algorithm and make the average of the cost (after an infinite number of times) you will get an average cost equal to the expected cost.

I hope it's clear ...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.