Janson inequality

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

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

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

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

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

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

Then the Janson inequality is:

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

and

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

Tail bound

Janson later extended this result to give a tail bound on the probability of only a few sets being subsets. Let $0\leq t\leq \lambda$ give the distance from the expected number of subsets. Let $\varphi (x)=(1+x)\ln(1+x)-x$. Then we have

$\Pr(X\leq \lambda -t)\leq e^{-\varphi (-t/\lambda )\lambda ^{2}/{\bar {\Delta }}}\leq e^{-t^{2}/\left(2{\bar {\Delta }}\right)}$

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.