Janson inequality
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
![]() |
![]() |
Then
![]() | (a1) |
and, which is better for ,
![]() | (a2) |
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):
![]() | (a3) |
where . This version puts emphasis on comparison with the independent case.
Under modest symmetry conditions, inequality (a2) appeared in [a3], while the general version was proved in [a4]. See also [a6] for another proof of (a2), but with an extra factor in the exponent.
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
.
Example.
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
,
![]() | (a4) |
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].
References
[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. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Janson_inequality&oldid=49932