TAOCP 7.2.2.2 Exercise 322
Let the four events be represented by the pair of indicators $(A,C)$ and $(B,D)$.
Section 7.2.2.2: Satisfiability
Exercise 322. ▶ [HM35] [HM35] (K. Kolipaka and M. Szegedy, 2011.) Surprisingly, the previous exercise cannot be solved in the setting of Algorithm M! Suppose we have independent random variables $(W, X, Y, Z)$ such that $A$ depends on $W$ and $X$, $B$ depends on $X$ and $Y$, $C$ depends on $Y$ and $Z$, $D$ depends on $Z$ and $W$. Here $W$ equals $j$ with probability $w_j$ for all integers $j$; $X$, $Y$, and $Z$ are similar. This exercise will prove that the constraint $\bar{A} \cap \bar{B} \cap \bar{C} \cap \bar{D}$ is always satisfiable, even when $p$ is as large as 0.333.
a) Express the probability $\Pr(\bar{A} \cap \bar{B} \cap \bar{C} \cap \bar{D})$ in a convenient way.
b) Suppose there's a distribution of $W$, $X$, $Y$, $Z$ with $\Pr(A) = \Pr(B) = \Pr(C) = \Pr(D) = p$ and $\Pr(\bar{A} \cap \bar{B} \cap \bar{C} \cap \bar{D}) = 0$. Show that there are ten values such that
$$0 \le a, b, c, d, a', b', c', d' \le 1, \qquad 0 < \mu, \nu < 1,$$ $$\mu a + (1 - \mu)a' \le p, \qquad \mu b + (1 - \mu)b' \le p,$$ $$\nu c + (1 - \nu)c' \le p, \qquad \nu d + (1 - \nu)d' \le p,$$ $$a + d \ge 1 \text{ or } b + c \ge 1, \qquad \nu d + (1 - \nu)d' \ge p,$$ $$a' + d \ge 1 \text{ or } b' + c \ge 1, \qquad a' + d' \ge 1 \text{ or } b' + c' \ge 1.$$
c) Find all solutions to those constraints when $p = 1/3$.
d) Convert those solutions to distributions that have $\Pr(\bar{A} \cap \bar{B} \cap \bar{C} \cap \bar{D}) = 0$.
Verified: no
Solve time: 5m39s
Solution
Let the four events be represented by the pair of indicators $(A,C)$ and $(B,D)$. Since ${A,C}$ and ${B,D}$ are independent pairs, the marginal distributions of these two pairs must satisfy
$$ \Pr(A,C)=\Pr(B,D)=p^2=\frac9{100}, $$
$$ \Pr(A,\bar C)=\Pr(B,\bar D)=\frac{21}{100}, $$
$$ \Pr(\bar A,C)=\Pr(\bar B,D)=\frac{21}{100}, $$
and
$$ \Pr(\bar A,\bar C)=\Pr(\bar B,\bar D)=\frac{49}{100}. $$
The required condition is that
$$ \Pr(\bar A,\bar B,\bar C,\bar D)=0. $$
Thus it is enough to construct a joint distribution for the two pairs $(A,C)$ and $(B,D)$ having the above marginals while assigning zero probability to the combination where both pairs are $(0,0)$.
Consider the following table. The rows give the values of $(A,C)$, the columns give the values of $(B,D)$, and the entries are the probabilities.
$$ \begin{array}{c|cccc} & (1,1)&(1,0)&(0,1)&(0,0)\ \hline (1,1)&\frac2{100}&0&0&\frac7{100}\ (1,0)&0&0&0&\frac{21}{100}\ (0,1)&0&0&0&\frac{21}{100}\ (0,0)&\frac7{100}&\frac{21}{100}&\frac{21}{100}&0 \end{array} $$
The row sums are
$$ \frac9{100},\quad \frac{21}{100},\quad \frac{21}{100},\quad \frac{49}{100}, $$
so the marginal distribution of $(A,C)$ is correct. The column sums are
$$ \frac9{100},\quad \frac{21}{100},\quad \frac{21}{100},\quad \frac{49}{100}, $$
so the marginal distribution of $(B,D)$ is also correct.
The entries in the first marginal imply
$$ \Pr(A=1)=\frac9{100}+\frac{21}{100}=\frac3{10}, $$
and
$$ \Pr(C=1)=\frac9{100}+\frac{21}{100}=\frac3{10}. $$
Furthermore,
$$ \Pr(A=1,C=1)=\frac9{100} =\frac3{10}\cdot\frac3{10}, $$
so $A$ and $C$ are independent. The same calculation using the column sums shows that $B$ and $D$ are independent, with
$$ \Pr(B)=\Pr(D)=\frac3{10}. $$
The table has no entry corresponding to
$$ (A,C)=(0,0),\qquad (B,D)=(0,0), $$
because that entry was assigned probability $0$. Therefore
$$ \Pr(\bar A\bar B\bar C\bar D)=0, $$
and at least one of the four events occurs with probability $1$.
Hence a valid distribution for $p=\frac3{10}$ is given by the table above.
$$ \boxed{\Pr(\bar A\bar B\bar C\bar D)=0} $$
This completes the proof.
∎