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:
“O, popular applause! what heart of man
Is proof against thy sweet, seducing charms?”
—William Cowper (1731–1800)
“Talk shows are proof that conversation is dead.”
—Mason Cooley (b. 1927)
“To cease to admire is a proof of deterioration.”
—Charles Horton Cooley (1864–1929)