Fix your favorite programming language and let K(x) be the length of the smallest program generating string x. Define μ(x)=2-K(x), known as the universal distribution for reasons I won't get into here. Notice how strings of smaller complexity get more weight.
Theorem (Li-Vitányi) Any algorithm using time T(n) on average over the universal distribution uses time O(T(n)) in the worst case.
Li and Vitányi prove their theorem by showing that if the set of worst-case inputs is small they will have a short description and thus more heavily weighted under μ. Read all the details in their paper.