How do the conditional probabilities work in the main proof of the general Lovasz Local Lemma without a non-zero probability condition?

40 Views Asked by At

In the proof of the Lovasz Local Lemma (general case), we want to prove that $Pr \left[ \bigwedge_{i = 1}^{n} \bar{A_i} \right] \ge \prod_{i=1}^{n}(1 - x_i) > 0$.

The proof uses a helper lemma proved by induction which states that for any $S \subset \{ 1, ..., n \}$, $|S| = s < n$, and for any $i \notin S$, $Pr \left[ A_i | \bigwedge_{j \in S} \bar{A_j} \right] \le x_i$. This helper lemma is proved inductively.

The helper lemma can then be applied to prove the main lemma, by expanding out the typical multiplication rule for conditional probabilities:

$Pr \left[ \bigwedge_{i = 1}^{n} \bar{A_i} \right] = Pr[\bar{A_1}]Pr[\bar{A_2}|\bar{A_1}] \dots = (1 - Pr[A_1])(1 - Pr[A_2|\bar{A_1}]) \dots (1 - Pr\left[A_n | \bigwedge_{i = 1}^{n -1} \bar{A_i} \right])$

My main question is around the application of the rule $Pr[A|B] = 1 - Pr[\bar{A}|B]$ which obviously only holds when conditional probability is defined (i.e. $Pr[B] > 0$). But in the above expansion, we don't have any such constraints on terms such as $Pr\left[\bigwedge_{i = 1}^{n -1} \bar{A_i} \right]$. In fact, this is what we are trying to prove for the n case. So how can the complement rule be applied? I've found a proof that does a second lot of induction on the main lemma statement that removes this question, but in most textbooks/lecture notes, this is not done. So is this a case of proofs skipping over some intuition, or am I missing another reason we can apply the rule directly?