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.