Statement
Let us state the principle for Las Vegas randomized algorithms, i.e., distributions over deterministic algorithms that are correct on every input but have varying costs. It is straightforward to adapt the principle to Monte Carlo algorithms, i.e., distributions over deterministic algorithms that have bounded costs but can be incorrect on some inputs.
Consider a problem over the inputs, and let be the set of all possible deterministic algorithms that correctly solve the problem. For any algorithm and input, let be the cost of algorithm run on input .
Let be a probability distributions over the algorithms, and let denote a random algorithm chosen according to . Let be a probability distribution over the inputs, and let denote a random input chosen according to . Then,
- ,
i.e., the worst-case expected cost of the randomized algorithm is at least the cost of the best deterministic algorithm against input distribution .
Read more about this topic: Yao's Principle
Famous quotes containing the word statement:
“Eroticism has its own moral justification because it says that pleasure is enough for me; it is a statement of the individual’s sovereignty.”
—Mario Vargas Llosa (b. 1936)
“The new statement is always hated by the old, and, to those dwelling in the old, comes like an abyss of skepticism.”
—Ralph Waldo Emerson (1803–1882)
“After the first powerful plain manifesto
The black statement of pistons, without more fuss
But gliding like a queen, she leaves the station.”
—Stephen Spender (1909–1995)