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:
“Talk shows are proof that conversation is dead.”
—Mason Cooley (b. 1927)
“The moment a man begins to talk about technique that’s proof that he is fresh out of ideas.”
—Raymond Chandler (1888–1959)
“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)