Janson's inequality
/ YAN-son /
Janson's inequality is a sharp exponential bound on the lower tail of a sum of dependent indicator variables — specifically the probability that none of a family of 'increasing' bad events occurs. It is the tool that fills a gap left by the second moment method. Suppose X = sum of indicators 1_{A_i}, where each A_i is the event that a particular small substructure (say a fixed subgraph) is present in a random object. The first moment gives E[X]; the second moment can show X > 0 with high probability; but to bound P(X = 0) — the probability that NOT A SINGLE one of the substructures appears — one wants an exponentially small estimate, and Chebyshev only gives a polynomial one. Janson's inequality supplies the exponential bound.
The setting is a random subset R of a ground set where each element is included independently, and each A_i is the event that R contains a fixed subset S_i (a monotone increasing event). Write mu = E[X] = sum P(A_i), and let Delta = sum over ordered pairs (i,j) with i not equal j and S_i, S_j overlapping of P(A_i and A_j) — the total pairwise dependence between overlapping events. Janson's inequality states P(X = 0) = P(no A_i occurs) <= exp(-mu + Delta/2). When the events are nearly independent, Delta is small, and this reduces to roughly e^(-mu), matching the answer for independent events product of (1 - P(A_i)). The companion 'extended' Janson inequality handles the regime Delta >= mu, giving P(X = 0) <= exp(-mu^2/(2 Delta)), which is the form needed in dense regimes. The proof rests on the FKG correlation inequality: increasing events are positively correlated, so P(none occurs) is controlled by an FKG-style product expansion.
Its power is that for monotone subgraph-appearance events it gives the truly exponentially small probability of total absence, which Chebyshev cannot, and it does so with explicit constants. This is exactly what is needed to prove that a property holds with very high probability (probability 1 - e^(-c)) rather than merely high probability, and it is central to sharp threshold results in random graphs and to lower-tail large deviations for subgraph counts. The honest caveat is that Janson's inequality is one-sided and structurally restricted: it bounds only the lower tail (P(X = 0) or P(X small)), it requires the A_i to be increasing events on independent coordinates, and the bound exp(-mu + Delta/2) is useless once Delta exceeds 2 mu — that is precisely the regime where the extended inequality, or a different tool, must take over.
Probability G(n,p) is triangle-free. Let A_i range over the C(n,3) potential triangles; mu = E[X] = C(n,3)p^3 and Delta ~ n^4 p^5 from triangles sharing an edge. Janson gives P(triangle-free) = P(X=0) <= exp(-mu + Delta/2). For p just above 1/n, mu -> infinity while Delta/mu stays controlled, so the probability of being triangle-free is exponentially small in mu — an exact rate that the second moment's polynomial bound P(X=0) <= Var/E^2 cannot deliver.
P(X = 0) <= exp(-mu + Delta/2): an FKG-based exponential bound on the lower tail of monotone counts.
Janson is one-sided and needs increasing events on independent coordinates; the bound exp(-mu + Delta/2) is useless once Delta > 2 mu, where the extended inequality exp(-mu^2/(2 Delta)) must take over.