TAOCP 7.1.1 Exercise 14
We restart from the definitions used in Exercise 13 and the notion of self-duality.
Exercise 14. [20] [20] The probability function $F(p_1, \ldots, p_n)$ in exercise 13 is often called the availability of the system. Find the self-dual function (19) of maximum availability when the probabilities $(p_1, p_2, p_3)$ are (a) $(.9, .8, .7)$; (b) $(.8, .6, .4)$; (c) $(.8, .6, .1)$.
Verified: yes
Solve time: 8m23s
We restart from the definitions used in Exercise 13 and the notion of self-duality.
A Boolean function $f(x_1,x_2,x_3)$ is self-dual if
$$ f(x_1,x_2,x_3) = 1 - f(1-x_1,1-x_2,1-x_3). $$
The availability of a system with structure function $f$ is
$$ F(p_1,p_2,p_3) = \mathbb{E}[f(X_1,X_2,X_3)], $$
where $X_i$ are independent Bernoulli variables with $\Pr(X_i=1)=p_i$.
We restrict attention to the class of self-dual monotone Boolean functions on three variables, as in (19). For $n=3$, these are exactly the self-dual structure functions corresponding to coherent systems. A direct classification (via the symmetry condition on the Hasse diagram of ${0,1}^3$) shows that there is, up to permutation of variables, a single essential self-dual coherent structure:
$$ f(x_1,x_2,x_3) = 1 \quad \text{iff at least two of } x_1,x_2,x_3 \text{ equal } 1. $$
This is the majority system (2-out-of-3).
No other monotone structure function satisfies self-duality for three variables while remaining coherent: any function depending asymmetrically on one variable forces a violation of the complement symmetry condition.
Hence, the maximization over self-dual functions reduces to evaluating this function.
Step 1: Availability of the majority (2-out-of-3) system
The system works if at least two components work:
$$ F(p_1,p_2,p_3) = p_1p_2(1-p_3) + p_1p_3(1-p_2) + p_2p_3(1-p_1) + p_1p_2p_3. $$
Simplifying,
$$ F(p_1,p_2,p_3) = p_1p_2 + p_1p_3 + p_2p_3 - 2p_1p_2p_3. $$
Step 2: Evaluate each case
(a) $(p_1,p_2,p_3) = (0.9,0.8,0.7)$
Pair products:
$$ p_1p_2 = 0.72,\quad p_1p_3 = 0.63,\quad p_2p_3 = 0.56, $$
so
$$ \sum p_ip_j = 1.91. $$
Triple product:
$$ p_1p_2p_3 = 0.504. $$
Thus
$$ F = 1.91 - 2(0.504) = 1.91 - 1.008 = 0.902. $$
(b) $(p_1,p_2,p_3) = (0.8,0.6,0.4)$
Pair products:
$$ 0.48 + 0.32 + 0.24 = 1.04, $$
triple product:
$$ 0.8 \cdot 0.6 \cdot 0.4 = 0.192. $$
Thus
$$ F = 1.04 - 2(0.192) = 1.04 - 0.384 = 0.656. $$
(c) $(p_1,p_2,p_3) = (0.8,0.6,0.1)$
Pair products:
$$ 0.48 + 0.08 + 0.06 = 0.62, $$
triple product:
$$ 0.8 \cdot 0.6 \cdot 0.1 = 0.048. $$
Thus
$$ F = 0.62 - 2(0.048) = 0.62 - 0.096 = 0.524. $$
Step 3: Optimality among self-dual functions
For three variables, any self-dual coherent structure function must be symmetric with respect to complementarity of minimal path sets. This constraint forces the structure to be equivalent to the majority system. Therefore, no alternative self-dual function can yield a higher availability for any given $(p_1,p_2,p_3)$.
Hence the majority function is the unique maximizer in each case.
Final answers
- (a) optimal self-dual function: majority (2-out-of-3), availability $0.902$
- (b) optimal self-dual function: majority (2-out-of-3), availability $0.656$
- (c) optimal self-dual function: majority (2-out-of-3), availability $0.524$