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 ${\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 }}}}}$

Tail bound

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

${\displaystyle \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.^[1] Research leading to these inequalities were originally motivated by estimating chromatic numbers of random graphs.^[2]

References

1. Limaye, Nutan; Sreenivasaiah, Karteek; Srinivasan, Srikanth; Tripathi, Utkarsh; Venkitesh, S. (2019). "A Fixed-depth size-hierarchy theorem for AC0[] via the coin problem". Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing: 442–453. arXiv:1809.04092. doi:10.1145/3313276.3316339. S2CID 195259318.
2. Ruciński, Andrzej. "Janson inequality". Encyclopedia of Mathematics. Retrieved 5 March 2020.