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:
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (1709–1784)
“If some books are deemed most baneful and their sale forbid, how, then, with deadlier facts, not dreams of doting men? Those whom books will hurt will not be proof against events. Events, not books, should be forbid.”
—Herman Melville (1819–1891)
“a meek humble Man of modest sense,
Who preaching peace does practice continence;
Whose pious life’s a proof he does believe,
Mysterious truths, which no Man can conceive.”
—John Wilmot, 2d Earl Of Rochester (1647–1680)