Nominull: By adding randomness to your algorithm, you spread its behaviors out over a particular distribution, and there must be at least one point in that distribution whose expected value is at least as high as the average expected value of the distribution.

Well said! This is an obvious point, but I've never heard it put quite so sharply before.