Janson inequality

For increasing containment events $A_i$ in a Bernoulli product space, let $X={\sum }_i{1}_{A_i}$, $\mu =\mathbb{E}X$, andwhere the sum is ordered and dependency means overlapping coordinate supports. ThenIn particular it is at most $e^{-\mu /2}$ when $\Delta \le \mu$, and at most $e^{-{\mu }^2/(2\Delta )}$ when $\Delta \ge \mu$.

For increasing containment indicators, attach independent Bernoulli selectors of parameter $t$. Janson inequality applied to the selected events gives $\mathbb{E}(1-t{)}^X\le \exp (-t\mu +t^2\Delta /2)$. Set $t=1-e^{-s}$ and apply the exponential Markov bound. The estimates $s-s^2/2\le 1-e^{-s}\le s$ give exponent at most $-sa+s^2(\mu +\Delta )/2$. Optimizing at $s=a/(\mu +\Delta )$ proves the displayed lower-tail bound, with the dependency sum ordered and excluding the diagonal.

The Janson dependency sum adds $\mathbb{P}(A_i\cap A_j)$ over ordered pairs of distinct containment events whose coordinate supports overlap.

For containment-event indicators $I_1,\dots ,I_m$ in a Bernoulli product space,It follows by exposing the avoidance events in sequence, separating disjoint coordinate supports, and applying Harris' inequality to the remaining decreasing events.