Averaging argument
Introduction 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  people and  books. Each person likes at least  of the books. Let people leave a mark on the book they like. Then, there will be at least  marks. The averaging argument claims that there exists a book with at least  marks on it. Assume, to the contradiction, that no such book exists. Then, every book has fewer than  marks. However, since there are  books, the total number of marks will be fewer than , contradicting the fact that there are at least  marks.
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  be some function. The averaging argument is the following claim: if we have a circuit  such that  with probability at least , where  is chosen at random and  is chosen independently from some distribution  over  (which might not even be efficiently sampleable) then there exists a '''single''' string  such that .Indeed, for every  define  to be  then: and then this reduces to the claim that for every random variable , if  then  (this holds since  is the weighted average of  and clearly if the average of some values is at least  then one of the values must be at least ).
Application This argument has wide use in complexity theory (e.g. proving ) and cryptography (e.g. proving that indistinguishable encryption results in semantic security). A plethora of such applications can be found in Goldreich's books.
References