TAOCP 7.1.1 Exercise 13
Let $X_j$ be independent random variables with $\Pr(X_j = 1) = p_j, \qquad \Pr(X_j = 0) = 1 - p_j,$ and interpret $x_j$ in the Boolean function $f(x_1,\ldots,x_n)$ as $X_j$.
Exercise 13. [20] [20] Consider a system that consists of $n$ units, each of which may be "working" or "failing." If $x_j$ represents the condition "unit $j$ is working," then a Boolean function like $x_1 \wedge (x_2 \vee x_3)$ represents the statement "unit 1 is working, but either unit 2 or unit 3 is failing"; and $S_k(x_1, \ldots, x_n)$ means "exactly three units are working."
Suppose each unit $j$ is in working order with probability $p_j$, independent of the other units. Show that the Boolean function $f(x_1, \ldots, x_n)$ is true with probability $F(p_1, \ldots, p_n)$, where $F$ is the multilinear representation of $f$.
Verified: yes
Solve time: 1m20s
Solution
Let $X_j$ be independent random variables with
$\Pr(X_j = 1) = p_j, \qquad \Pr(X_j = 0) = 1 - p_j,$
and interpret $x_j$ in the Boolean function $f(x_1,\ldots,x_n)$ as $X_j$.
Let the integer multilinear representation of $f$ be written in the form
$F(x_1,\ldots,x_n) = \sum_{S \subseteq {1,\ldots,n}} a_S \prod_{j \in S} x_j,$
where $a_S \in \mathbb{Z}$ and $F(x_1,\ldots,x_n) = f(x_1,\ldots,x_n)$ for all $(x_1,\ldots,x_n) \in {0,1}^n$.
Define the random variable
$Y = f(X_1,\ldots,X_n).$
Since $Y \in {0,1}$, the probability that $f$ is true equals its expectation,
$\Pr(Y=1) = \mathbb{E}[Y].$
Because $F(X_1,\ldots,X_n) = Y$ for all outcomes of $(X_1,\ldots,X_n)$, it follows that
$\Pr(f(X_1,\ldots,X_n)=1) = \mathbb{E}[F(X_1,\ldots,X_n)].$
Substituting the multilinear expansion,
$\mathbb{E}[F(X_1,\ldots,X_n)] = \mathbb{E}\left[\sum_{S \subseteq {1,\ldots,n}} a_S \prod_{j \in S} X_j \right].$
Linearity of expectation yields
$\mathbb{E}[F(X_1,\ldots,X_n)] = \sum_{S \subseteq {1,\ldots,n}} a_S , \mathbb{E}\left[\prod_{j \in S} X_j\right].$
For each fixed subset $S$, independence of the $X_j$ implies
$\mathbb{E}\left[\prod_{j \in S} X_j\right] = \prod_{j \in S} \mathbb{E}[X_j] = \prod_{j \in S} p_j.$
Substituting this identity into the previous sum gives
$\mathbb{E}[F(X_1,\ldots,X_n)] = \sum_{S \subseteq {1,\ldots,n}} a_S \prod_{j \in S} p_j.$
The right-hand side is exactly the evaluation of the multilinear polynomial $F$ at $(p_1,\ldots,p_n)$, since multilinearity preserves the same coefficient structure under substitution:
$F(p_1,\ldots,p_n) = \sum_{S \subseteq {1,\ldots,n}} a_S \prod_{j \in S} p_j.$
Therefore,
$\Pr(f(X_1,\ldots,X_n)=1) = F(p_1,\ldots,p_n).$
This completes the proof. ∎