In the mathematical theory of probability, Janson's inequality is a collection of related inequalities giving an exponential bound on the probability of many related events happening simultaneously by their pairwise dependence. Informally Janson's inequality involves taking a sample of many independent random binary variables, and a set of subsets of those variables and bounding the probability that the sample will contain any of those subsets by their pairwise correlation.

Statement

Let  be our set of variables. We intend to sample these variables according to probabilities . Let  be the random variable of the subset of  that includes  with probability . That is, independently, for every .

Let  be a family of subsets of . We want to bound the probability that any  is a subset of . We will bound it using the expectation of the number of  such that , which we call , and a term from the pairwise probability of being in , which we call .

For , let  be the random variable that is one if  and zero otherwise. Let  be the random variables of the number of sets in  that are inside : . Then we define the following variables:

 

 

 

Then the Janson inequality is:

 

and

Tail bound

Janson later extended this result to give a tail bound on the probability of only a few sets being subsets. Let  give the distance from the expected number of subsets. Let . Then we have

Uses 

Janson's Inequality has been used in pseudorandomness for bounds on constant-depth circuits. Research leading to these inequalities were originally motivated by estimating chromatic numbers of random graphs.

References 

Probabilistic inequalities