We give simple, combinatorial proofs of various concentration bounds, which says that random variables from certain classes are highly concentrated around their expected values. Examples include Chernoff bounds for the sums of independent random variables, Azuma's inequality for Martingales, and the Chernoff bound for expander walks. Unlike the standard proofs, our proof does not use the method of higher moments, but rather uses a simple reduction from the probability that subsets are entirely one to a concentration bound.

 

In addition, our proof is constructive in the following sense: if the sum of the given random variables is not concentrated around the expectation, then we can efficiently find (with high probability) a subset of the random variables that are positively correlated. This gives a reduction from Thresholded Direct Product theorems to Direct Product Theorems, applicable in almost any context. Informally, a Direct Product Theorem says that the complexity of solving all k instances of a somewhat hard problem increases exponentially with k; a Threshold Direct Product Theorem says that it is exponentially hard in k to even solve any fraction of the given k instances of a hard problem significantly larger than for a single instance. Thresholded Direct Product theorems are useful to distinguish between a legitimate user who is imperfect and an attacker that is significantly worse.  For example, a human user might be unable to solve CAPTTCHA problems all of the time, but still be significantly better than any AI bot. Thresholded direct products give a way to make the CAPTTCHA both reliably easy for humans and reliably hard for bots. We show the equivalence between optimal Direct Product Theorems and optimal Threshold Direct Product Theorems. We also get a simple constructive proof of Unger's result saying that XOR Lemmas imply Threshold Direct Product.