Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 1 / a / Solution

In an independent Bernoulli product space, an event is increasing if changing any coordinate from $0$ to $1$ cannot destroy it. Harris' inequality says that two increasing events $A,B$ satisfyEquivalently, two decreasing events are positively correlated.

For Janson inequalities, let $R$ be a random subset of a finite ground set whose elements are selected independently, let $(S_i{)}_{i\in I}$ be fixed subsets, and putWrite $i\sim j$ when $i\ne j$ and $S_i\cap S_j\ne \varnothing$, and define the ordered dependency sumThe first Janson inequality isThe usual extended form isThere is also the complementary lower boundand if $\mathbb{E}{I}_i\le \epsilon <1$ for all $i$, the product is at least $\exp (-\mu /(1-\epsilon ))$.

For the proof, order $I$ arbitrarily and expose the avoidance events one at a time. The standard Janson sequential product lemma, obtained by conditioning and using Harris' inequality on the coordinates outside $S_i$, givesUsing $1-x\le e^{-x}$ and summing the pair terms yields $e^{-\mu +\Delta /2}$. If $\Delta \le \mu$, this is at most $e^{-\mu /2}$. If $\Delta >\mu$, adjoin an independent Bernoulli coordinate of mean $q=\mu /\Delta$ to each index and intersect $A_i$ with the event that its new coordinate is $1$. The event $X=0$ implies that none of these thinned events occurs, while the thinned family has mean $q\mu$ and dependency sum $q^2\Delta$. Applying the first inequality in the enlarged product space givesFinally, the events $I_i=0$ are decreasing, so repeated Harris' inequality proves the product lower bound; $log(1-x)\ge -x/(1-\epsilon )$ gives its exponential version.