There are a couple of inequalities referred to as "Janson inequality" . They provide exponential upper bounds for the probability that a sum of dependent zero-one random variables (cf. also Random variable) equals zero. The underlying probability space corresponds to selecting a random subset of a finite set , where , in such a way that the elements are chosen independently with for each .
Let be a family of subsets of and, for every , let be equal to one if and be zero otherwise. Then counts those elements of which are entirely contained in . Set
and, which is better for ,
Research leading to these inequalities was motivated by a ground-breaking proof of B. Bollobás [a2], who, in order to estimate the chromatic number of a random graph, used martingales (cf. also Graph colouring; Graph, random; Martingale) to show that the probability of not containing a large clique is very small. Bollobás presented his proof at the opening day of the "Third Conference on Random Graphs (Poznań, July 1987)" . By the end of the meeting S. Janson found a proof of inequality (a1) based on Laplace transforms (cf. also Laplace transform), while T. Łuczak proved a related, less explicit estimate using martingales. The latter result was restricted to a special, though pivotal, context of small subgraphs of random graphs. Soon after, R. Boppana and J. Spencer [a1] gave another proof, resembling the proof of the Lovász local lemma, of the following version of (a1):
where . This version puts emphasis on comparison with the independent case.
The quantity is a measure of the pairwise dependence between the s. If , then the exponents in (a1) and (a2) are both equal to , matching asymptotically a lower bound obtained via the FKG inequality, provided further .
Let be an integer, , and let be the set of all two-element subsets of . With all , , the random subset is a random graph . Let be the family of all triples of pairs of the form , . Then is the number of triangles in , and . Thus, if , then , while for , inequality (a2) yields . As long as , , and the above exponential bounds strengthen the polynomial bound
obtained by the method of second moments, i.e. by a corollary of the Chebyshev inequality. To illustrate the strength of (a1), fix and assume that is divisible by . Then (a1) easily implies that with probability tending to one, more than of the vertices of are covered by vertex-disjoint triangles. Indeed, otherwise there would be a subset of vertices spanning no triangle. By (a1), the probability that this may happen is smaller than
In 1990, Janson [a4] generalized inequality (a2), obtaining an estimate of the lower tail of the distribution of . With , for ,
When consists of mutually disjoint sets, is a sum of independent zero-one random variables and (a4) coincides with the (one-sided) Chernoff bound. No corresponding upper tail estimate is true in general.
Also in 1990, W.C.S. Suen [a7] proved a related inequality, which remains valid for a general probability space (and not only for random subsets). In his setting, is a sum of arbitrary indicators , and the bound hinges on the dependency graph induced by them. Suen's inequality has been revived and extended in [a5].
Fore more details on this subject see [a8].
|[a1]||R. Boppana, J. Spencer, "A useful elementary correlation inequality" J. Combin. Th. A , 50 (1989) pp. 305–307|
|[a2]||B. Bollobás, "The chromatic number of random graphs" Combinatorica , 8 (1988) pp. 49–56|
|[a3]||S. Janson, T. Łuczak, A. Ruciński, "An exponential bound for the probability of nonexistence of a specified subgraph in a random graph" M. Karoński (ed.) J. Jaworski (ed.) A. Ruciński (ed.) , Random Graphs '87 , Wiley (1990) pp. 73–87|
|[a4]||S. Janson, "Poisson approximation for large deviations" Random Struct. Algor. , 1 (1990) pp. 221–230|
|[a5]||S. Janson, "New versions of Suen's correlation inequality" Random Struct. Algor. , 13 (1998) pp. 467–483|
|[a6]||J. Spencer, "Threshold functions for extension statements" J. Combin. Th. A , 53 (1990) pp. 286–305|
|[a7]||W.C.S. Suen, "A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph" Random Struct. Algor. , 1 (1990) pp. 231–242|
|[a8]||S. Janson, T. Łuczak, A. Ruciński, "Random graphs" , Wiley (2000)|
Janson inequality. A. RuciÅ„ski (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Janson_inequality&oldid=16002