Lesson 4

Proof. We will prove a more general property: for any \(A \in \mathcal{A}\) and any \(A \not \in \mathcal{S} \subseteq \mathcal{A}\), the inequalities hold \[\begin{align*}\Pr\left[\bigcap_{B \in \mathcal{S}}\overline B \right]&> 0 \\ \Pr\left[A \mid \bigcap_{B \in \mathcal{S}}\overline B \right]&\le p(A) \ .\end{align*}\] (The first inequality guarantees that the conditional probability in the second inequality is used correctly.)

We will show how these two inequalities imply the statement of the theorem. From the second, we conclude that \[\Pr\left[\overline A \mid \bigcap_{B \in \mathcal{S}}\overline B \right] \ge 1-p(A) \ .\] Then, by the chain rule, we get \[\Pr[\overline A_{1} \cap \dotsb \cap \overline A_{n}]=\prod_{i \in [n]}\Pr\left[\overline A_{i} \mid \bigcap_{j \in [i-1]}\overline A_{j}\right] \ge \prod_{i \in [n]}(1-p(A_{i})) \ .\]

The two inequalities we need will be proven by induction on \(s=|\mathcal{S}|\). The base case \(s=0\) is satisfied: \(\Pr[\cap_{B \in \varnothing}\overline{B}]=1>0\) and \(\Pr[A] \le p(A)\). For the transition \(s-1 \to s\), we first show that the first inequality holds. To do this, fix the event \(A' \in \mathcal{S}\) and let \(\mathcal{S}'=\mathcal{S}\setminus \{A'\}\). Then, from the first and third inequalities, we conclude that \[\Pr\left[\bigcap_{B \in \mathcal{S}}\overline B \right]= \Pr\left[\bigcap_{B \in \mathcal{S'}}\overline B\right] \cdot \Pr\left[\overline{A'}\mid \bigcap_{B \in \mathcal{S'}}\overline B \right] >0\] (the first factor is positive by the induction hypothesis, the second is at least \(1-p(A')\) by the third inequality and therefore positive).

To prove the second inequality, consider the sets \(\mathcal{S}_{1}=\mathcal{S} \cap \Gamma(A)\) and \(\mathcal{S}_{2} = \mathcal{S} \setminus \mathcal{S}_{1}\). Write: \[\Pr\left[A \mid \bigcap_{B \in \mathcal{S}}\overline B\right] = \frac{\Pr\left[A \cap \bigcap_{B \in \mathcal{S_1}}\overline B \mid \bigcap_{B \in \mathcal{S_2}}\overline B \right]}{\Pr\left[\bigcap_{B \in \mathcal{S_1}}\overline B \mid \bigcap_{B \in \mathcal{S_2}}\overline B \right]}\ .\] The numerator of the resulting fraction is at most \[\Pr\left[A \mid \bigcap_{B \in \mathcal{S_2}}\overline B \right] = \Pr[A] \le p(A)\prod_{B \in \Gamma(A)}(1-p(B)) \ ,\] where the equality follows from the independence condition. To estimate the denominator, we write the conjunction of the events \(\mathcal{S}_{1}=\{B_{1}, \dotsc, B_{m}\}\) and estimate the factors by the induction hypothesis (in the conditional part, there will be strict subsets of \(\mathcal{S}\), so their size will be smaller than \(s\)): \[\Pr\left[\bigcap_{B \in \mathcal{S_1}}\overline B \mid \bigcap_{B \in \mathcal{S_2}}\overline B \right]=\prod_{i \in [m]}\Pr\left[\overline B_{i} \mid \bigcap_{j \in [i-1]}\overline B_{j} \cap \bigcap_{B \in \mathcal{S_2}}\overline B \right] \ge \prod_{B \in \mathcal{S_1}}(1-p(B)) \ .\] It remains to estimate the ratio of the obtained estimates: \[\Pr\left[A \mid \bigcap_{B \in \mathcal{S}}\overline B \right] \le p(A) \prod_{B \in \Gamma(A) \setminus \mathcal{S_1}}(1-p(B)) \le p(A) \ .\]◼