Proof
Let . For every input, we have . Therefore, . Using Fubini's theorem, since all terms are non-negative we can switch the order of summation, giving . By the Pigeonhole principle, there must exist an algorithm so that, concluding the proof.
As mentioned above, this theorem can also be seen as a very special case of the Minimax theorem.
Read more about this topic: Yao's Principle
Famous quotes containing the word proof:
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other twoa proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (16941773)
“There is no better proof of a mans being truly good than his desiring to be constantly under the observation of good men.”
—François, Duc De La Rochefoucauld (16131680)
“a meek humble Man of modest sense,
Who preaching peace does practice continence;
Whose pious lifes a proof he does believe,
Mysterious truths, which no Man can conceive.”
—John Wilmot, 2d Earl Of Rochester (16471680)