Janson inequality

Remarks

If moreover $\Delta \ge \mu$, a further argument gives the bound $e^{-\mu^2/(2\Delta)}$. In the other direction, the Harris inequality gives $\Pr\big(\bigcap_i \overline{B_i}\big) \ge \prod_i (1 - \Pr(B_i))$. So when $\Delta$ is small and each $\Pr(B_i)$ is small, the probability that no $B_i$ occurs is close to $e^{-\mu}$, as for independent events. For example, in the random graph $G(n, p)$, take $\Gamma$ to be the set of edges of $K_n$ and the $A_i$ to be the edge sets of triangles. Then $\mu = \binom{n}{3} p^3$. When $p = c/n$ for a constant $c > 0$, one has $\mu \to c^3/6$ and $\Delta \to 0$ as $n \to \infty$. With the lower bound, the probability that $G(n, p)$ has no triangle tends to $e^{-c^3/6}$. The proof writes the probability as a product of the factors $\Pr\big(\overline{B_i} \mid \bigcap_{j < i} \overline{B_j}\big)$. It bounds each conditional probability of $B_i$ from below, using the Harris inequality for increasing events.

Going deeper

For a student

The Janson inequality is a standard tool in the theory of random graphs and the probabilistic method. It gives exponentially small upper bounds on the probability that a random graph contains no copy of a given subgraph. Compared with the second moment method, it gives a much sharper bound on the probability of the lower tail.