Janson inequality

Short description: Mathematical theory

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

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

For [math]\displaystyle{ A \in S }[/math], let [math]\displaystyle{ I_A }[/math] be the random variable that is one if [math]\displaystyle{ A \subseteq \Gamma_p }[/math] and zero otherwise. Let [math]\displaystyle{ X }[/math] be the random variables of the number of sets in [math]\displaystyle{ S }[/math] that are inside [math]\displaystyle{ \Gamma_p }[/math]: [math]\displaystyle{ X = \sum_{A \in S} I_A }[/math]. Then we define the following variables:

[math]\displaystyle{ \lambda = \operatorname E \left[\sum_{A \in S} I_A\right] = \operatorname E[X] }[/math]

[math]\displaystyle{ \Delta = \frac{1}{2}\sum_{A \neq B, A \cap B \neq \emptyset} \operatorname E[I_A I_B] }[/math]

[math]\displaystyle{ \bar{\Delta} = \lambda + 2\Delta }[/math]

Then the Janson inequality is:

[math]\displaystyle{ \Pr[X = 0] = \Pr[\forall A \in S: A \not \subset \Gamma_p] \leq e^{-\lambda + \Delta} }[/math]

and

[math]\displaystyle{ \Pr[X = 0] = \Pr[\forall A \in S: A \not \subset \Gamma_p] \leq e^{-\frac{\lambda^2}{\bar{\Delta}}} }[/math]

Tail bound

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

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

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.