Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2009 / B / 5 / a

Let $I_i=1_{A_i}$ and $X={\sum }_i{I}_i$. DefineThe dependency sum is over ordered pairs, so each unordered overlapping pair is counted twice. Disjoint prescribed edge sets give independence.

Order the events. For each $i$, let $B_i$ be the event that all earlier events fail. Split it as $B_i=C_i\cap D_i$, where $C_i$ excludes earlier events with edge sets disjoint from $E_i$, and $D_i$ excludes the overlapping earlier events. These are down-sets. The event $A_i$ is a principal up-set, and it is independent of $C_i$ since their determining edge sets are disjoint.

If some $B_i$ has probability zero the desired zero-event bound is immediate. Otherwise the allowed conditional correlation inequality givesSince $\mathbb{P}(B_i)\le \mathbb{P}(C_i)$, it follows thatThe last step is the union bound under conditioning on $A_i$. Zero-probability events may simply be omitted, and a certain event makes the target probability zero. Finally the sequential product and $1-u\le e^{-u}$ giveThis proves the first Janson inequality with the dependency-sum convention explicit.

Independently retain each event with probability $t$, using a fresh Bernoulli mark for every index. Its retained occurrence is the original principal up-set together with its mark being one, so the first proof applies in the enlarged independent product space. The new parameters are ${\mu }_t=t\mu$ and ${\Delta }_t=t^2\Delta$: distinct retained events have independent marks, and pairs of disjoint original supports remain independent.

If no original event occurs, no retained event occurs. ThusWhen $\Delta \ge \mu >0$, choose $t=\mu /\Delta$ to minimize this quadratic exponent. It givesIf $\mu =0$, the appropriate trivial bound is one, rather than an undefined zero-over-zero exponent. The argument is the Janson lower-tail bound by independent thinning.