TAOCP 7.2.2.2 Exercise 321

Let the four events be represented by the pair of indicators $(A,C)$ and $(B,D)$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.2: Satisfiability

Exercise 321. [M24] Suppose each of four random events $A$, $B$, $C$, $D$ occurs with probability $p$, where ${A, C}$ and ${B, D}$ are independent. According to exercise 320(b) with $m = 4$, there's a joint distribution of $(A, B, C, D)$ such that at least one of the events always occurs, whenever $p \ge (2 - \sqrt{2})/2 \approx 0.293$. Exhibit a distribution when $p = 3/10$.

Verified: no
Solve time: 4m47s

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.

∎