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:
“Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasn’t written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
—Robert Benchley (1889–1945)
“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)
“One is apt to be discouraged by the frequency with which Mr. Hardy has persuaded himself that a macabre subject is a poem in itself; that, if there be enough of death and the tomb in one’s theme, it needs no translation into art, the bold statement of it being sufficient.”
—Rebecca West (1892–1983)