= Solution
A <independence digraph of events>[dependency digraph] has <vertices> $1,\ldots,n$ and no loops. For each $i$, the <event> $A_i$ must be <independent> of the <sigma-algebra> generated jointly by all $A_j$ with $j\neq i$ for which there is no <edge> $i\to j$. Joint <independence> from that collection is required; <pairwise independence> alone does not suffice.
Write $\Gamma^+(i)$ for the outneighbours of $i$, and $B_S=\bigcap_{j\in S}A_j^c$. We prove by <induction> on $|S|$ that $B_S$ has positive <probability> and, when $i\notin S$,
$$
\mathbb P(A_i\mid B_S)\leq x_i.
$$
For $S=\varnothing$, the asserted conditional bound follows from the hypothesis, since its product factors are at most one. For the <induction> step, positivity for a <set> of size $r$ follows by writing its avoidance <probability> as a chain product: all preceding conditioning <sets> have size below $r$, so each factor is at least $1-x_j>0$.
Now take $|S|=r$, split $S_1=S\cap\Gamma^+(i)$ and $S_2=S\setminus\Gamma^+(i)$, and condition first on $B_{S_2}$. <Independence> gives $\mathbb P(A_i\mid B_{S_2})=\mathbb P(A_i)$. Moreover, order the elements of $S_1$ and use the inductive conditional bounds on the successive avoidance factors. Their conditioning <sets> have size at most $r-1$, so
$$
\mathbb P(B_{S_1}\mid B_{S_2})\geq\prod_{j\in S_1}(1-x_j).
$$
This remains true when $S_1$ is empty, with both sides one. Therefore
$$
\begin{aligned}
\mathbb P(A_i\mid B_S)
&=\frac{\mathbb P(A_i\cap B_{S_1}\mid B_{S_2})}{\mathbb P(B_{S_1}\mid B_{S_2})}\\
&\leq\frac{\mathbb P(A_i)}{\prod_{j\in S_1}(1-x_j)}\\
&\leq x_i\prod_{j\in\Gamma^+(i)\setminus S_1}(1-x_j)\leq x_i.
\end{aligned}
$$
The <induction> is complete. Finally expand the <probability> of avoiding all <events> in the order $1,\ldots,n$:
$$
\boxed{\mathbb P\left(\bigcap_{i=1}^nA_i^c\right)
=\prod_{i=1}^n\left(1-\mathbb P\left(A_i\,\middle|\,\bigcap_{j<i}A_j^c\right)\right)
\geq\prod_{i=1}^n(1-x_i)>0.}
$$
This proves the asymmetric <Lovász local lemma>, including the positivity needed to make every conditioning step legitimate.
Back to article page
