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:
“A sentence is made up of words, a statement is made in words.... Statements are made, words or sentences are used.”
—J.L. (John Langshaw)
“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)
“Eloquence must be grounded on the plainest narrative. Afterwards, it may warm itself until it exhales symbols of every kind and color, speaks only through the most poetic forms; but first and last, it must still be at bottom a biblical statement of fact.”
—Ralph Waldo Emerson (1803–1882)