Janson inequality

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

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

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

$\lambda =\mathrm{E}\left[\sum _{A\in S}{I}_A\right]=\mathrm{E}[X]$

$\mathrm{\Delta }=\frac{1}{2}\sum _{A\ne B,A\cap B\ne \mathrm{\varnothing }}\mathrm{E}[I_A{I}_B]$

$\overline{\mathrm{\Delta }}=\lambda +2\mathrm{\Delta }$

Then the Janson inequality is:

$\mathrm{Pr}[X=0]=\mathrm{Pr}[\mathrm{\forall }A\in S:A\subset ̸{\mathrm{\Gamma }}_p]\le e^{-\lambda +\mathrm{\Delta }}$

and

$\mathrm{Pr}[X=0]=\mathrm{Pr}[\mathrm{\forall }A\in S:A\subset ̸{\mathrm{\Gamma }}_p]\le e^{-\frac{{\lambda }^2}{\overline{\mathrm{\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\le t\le \lambda$ give the distance from the expected number of subsets. Let $\phi (x)=(1+x)\ln (1+x)-x$. Then we have

$\mathrm{Pr}(X\le \lambda -t)\le e^{-\phi (-t/\lambda ){\lambda }^2/\overline{\mathrm{\Delta }}}\le e^{-t^2/\left(2\overline{\mathrm{\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.