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 ${\displaystyle \Gamma }$ be our set of variables. We intend to sample these variables according to probabilities ${\displaystyle p=(p_{i}\in [0,1]:i\in \Gamma )}$. Let ${\displaystyle \Gamma _{p}\subseteq \Gamma }$ be the random variable of the subset of ${\displaystyle \Gamma }$ that includes ${\displaystyle i\in \Gamma }$ with probability ${\displaystyle p_{i}}$. That is, independently, for every ${\displaystyle i\in \Gamma$ :\Pr[i\in \Gamma _{p}]=p_{i}} .

Let ${\displaystyle S}$ be a family of subsets of ${\displaystyle \Gamma }$. We want to bound the probability that any ${\displaystyle A\in S}$ is a subset of ${\displaystyle \Gamma _{p}}$. We will bound it using the expectation of the number of ${\displaystyle A\in S}$ such that ${\displaystyle A\subseteq \Gamma _{p}}$, which we call ${\displaystyle \lambda }$, and a term from the pairwise probability of being in ${\displaystyle \Gamma _{p}}$, which we call ${\displaystyle \Delta }$.

For ${\displaystyle A\in S}$, let ${\displaystyle I_{A}}$ be the random variable that is one if ${\displaystyle A\subseteq \Gamma _{p}}$ and zero otherwise. Let ${\displaystyle X}$ be the random variables of the number of sets in ${\displaystyle S}$ that are inside ${\displaystyle \Gamma _{p}}$: ${\displaystyle X=\sum _{A\in S}I_{A}}$. Then we define the following variables:

${\displaystyle \lambda =\operatorname {E} \left[\sum _{A\in S}I_{A}\right]=\operatorname {E} [X]}$

${\displaystyle \Delta ={\frac {1}{2}}\sum _{A\neq B,A\cap B\neq \emptyset }\operatorname {E} [I_{A}I_{B}]}$

${\displaystyle {\bar {\Delta }}=\lambda +2\Delta }$

Then the Janson inequality is:

${\displaystyle \Pr[X=0]=\Pr[\forall A\in S:A\not \subset \Gamma _{p}]\leq e^{-\lambda +\Delta }}$

and

${\displaystyle \Pr[X=0]=\Pr[\forall A\in S:A\not \subset \Gamma _{p}]\leq e^{-{\frac {\lambda ^{2}}{\bar {\Delta }}}}}$

Uses

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

References