Conditional Probability · Local Lemma (Optional)

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Theorem (Erd\H{o}s — Lov\'asz, 1975; asymmetric version). Let \(\mathcal{A}=\{A_{1}, \dotsc, A_{n}\}\) be a set of events. Suppose there exist functions \(\Gamma \colon \mathcal{A} \to 2^{\mathcal{A}}\) and \(p \colon \mathcal{A} \to [0,1)\) with the following two properties, holding for all \(A \in \mathcal{A}\):

\(A\) is mutually independent of events from \(\mathcal{A} \setminus \Gamma(A)\) (that is, \(A\) and all events from \(\mathcal{A} \setminus \Gamma(A)\) are mutually independent);

\(\Pr[A] \le p(A) \prod_{B \in \Gamma(A)}(1-p(B))\).

Then \[\Pr\left[ \bigcap_{i \in [n]}\overline{A}_{i}\right] \ge \prod_{i \in [n]}(1-p(A_{i}))>0 \ .\]