Averaging argument

In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems. It usually allows us to convert probabilistic polynomial-time algorithms into non-uniform polynomial-size circuits.
Example.
Example: If every person likes at least 1/3 of the books in a library, then the library has a book, which at least 1/3 of people like.
Proof: Suppose there are formula_1 people and B books. Each person likes at least formula_2 of the books. Let people leave a mark on the book they like. Then, there will be at least formula_3 marks. The averaging argument claims that there exists a book with at least formula_4 marks on it. Assume, to the contradiction, that no such book exists. Then, every book has fewer than formula_4 marks. However, since there are formula_6 books, the total number of marks will be fewer than formula_7, contradicting the fact that there are at least formula_8 marks. formula_9
Formalized definition of averaging argument.
Let "X" and "Y" be sets, let "p" be a predicate on "X" × "Y" and let "f" be a real number in the interval [0, 1]. If for each "x" in "X" and at least "f |Y|" of the elements "y" in "Y" satisfy "p"("x", "y"), then there exists a "y" in "Y" such that there exist at least "f |X|" elements "x" in "X" that satisfy "p"("x", "y").
There is another definition, defined using the terminology of probability theory.
Let formula_10 be some function. The averaging argument is the following claim: if we have a circuit formula_11 such that formula_12 with probability at least formula_13, where formula_14 is chosen at random and formula_15 is chosen independently from some distribution formula_16 over formula_17 (which might not even be efficiently sampleable) then there exists a single string formula_18 such that formula_19.
Indeed, for every formula_15 define formula_21 to be formula_22 then
and then this reduces to the claim that for every random variable formula_24, if formula_25 then formula_26 (this holds since formula_27 is the weighted average of formula_24 and clearly if the average of some values is at least formula_13 then one of the values must be at least formula_13).
Application.
This argument has wide use in complexity theory (e.g. proving formula_31) and cryptography (e.g. proving that indistinguishable encryption results in semantic security). A plethora of such applications can be found in Goldreich's books.