Jump to content

Janson inequality

From Wikipedia, the free encyclopedia

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

[edit]

Let be our set of variables. We intend to sample these variables according to probabilities . Let be the random variable of the subset of that includes with probability . That is, independently, for every .

Let be a family of subsets of . We want to bound the probability that any is a subset of . We will bound it using the expectation of the number of such that , which we call , and a term from the pairwise probability of being in , which we call .

For , let be the random variable that is one if and zero otherwise. Let be the random variables of the number of sets in that are inside : . Then we define the following variables:

Then the Janson inequality is:

and

Tail bound

[edit]

Janson later extended this result to give a tail bound on the probability of only a few sets being subsets. Let give the distance from the expected number of subsets. Let . Then we have

Uses

[edit]

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

[edit]
  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.