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 [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.[1] Research leading to these inequalities were originally motivated by estimating chromatic numbers of random graphs.[2]
References
- ↑ 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. doi:10.1145/3313276.3316339.
- ↑ Ruciński, Andrzej. "Janson inequality". http://www.encyclopediaofmath.org/index.php?title=Janson_inequality&oldid=16002. Retrieved 5 March 2020.
![]() | Original source: https://en.wikipedia.org/wiki/Janson inequality.
Read more |