The conditional-probability induction underlying the Lovász Local Lemma

For $S=\mathrm{\varnothing }$, the conditional probability is $\mathbb{P}(A_i)\le x_i{\prod }_{j\in N_D^{+}(i)}(1-x_j)\le x_i$.

Assume the assertion holds whenever the conditioning set has fewer than $m$ elements, and let $\mathrm{\mid }S\mathrm{\mid }=m>0$. Put $S_1=S\cap N_D^{+}(i)$ and $S_2=S\setminus S_1$.

If $S_1=\mathrm{\varnothing }$, [L3] gives $\mathbb{P}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)=\mathbb{P}(A_i)\le x_i$.

Suppose $S_1\mathrm{\ne }\mathrm{\varnothing }$, order it as $j_1,\dots ,j_r$, and write $C_t={\bigcap }_{j\in S_t}{A}_j^c$. Since $\mathbb{P}(C_1\cap C_2)>0$, also $\mathbb{P}(C_2)>0$. Conditional multiplication gives $\mathbb{P}(A_i\mid C_1\cap C_2)=\mathbb{P}(A_i\cap C_1\mid C_2)\mathrm{/}\mathbb{P}(C_1\mid C_2)\le \mathbb{P}(A_i\mid C_2)\mathrm{/}\mathbb{P}(C_1\mid C_2)=\mathbb{P}(A_i)\mathrm{/}\mathbb{P}(C_1\mid C_2)$, where the equality uses [L3] because $S_2$ consists of non-out-neighbours of $i$.

The chain rule writes $\mathbb{P}(C_1\mid C_2)={\prod }_{q=1}^r(1-\mathbb{P}(A_{j_q}\mid {\bigcap }_{h\in S_2\cup \{j_1,\dots ,j_{q-1}\}}{A}_h^c))$. Every displayed conditioning set has fewer than $m$ elements and positive probability, because its complement intersection contains the positive event $C_1\cap C_2$. The induction hypothesis therefore bounds the conditional probability by $x_{j_q}$, so this denominator is at least ${\prod }_{j\in S_1}(1-x_j)$.

Consequently $\mathbb{P}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)\le \mathbb{P}(A_i)\mathrm{/}{\prod }_{j\in S_1}(1-x_j)\le x_i{\prod }_{j\in N_D^{+}(i)\setminus S_1}(1-x_j)\le x_i$.

Steps 2.1 and 4.1 cover the two possibilities for $S_1$, completing the induction. No conditional probability with zero denominator was formed.