Janson's 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$, 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 \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_ I_A$. Then we define the following variables:

: \lambda = \operatorname E \left sum_ I_A\right= \operatorname E /math>

: \Delta = \frac\sum_ \operatorname E _A I_B/math>

: $\bar = \lambda + 2\Delta$

Then the Janson inequality is:

: \Pr = 0= \Pr forall A \in S: A \not \subset \Gamma_p\leq e^

and

: \Pr = 0= \Pr forall A \in S: A \not \subset \Gamma_p\leq e^

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^ \leq e^$

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

{{reflist

Probabilistic inequalities