TAOCP 7.1.4 Exercise 28
Let $f(x_1,\ldots,x_n)$ be a Boolean function and let G(z)=\sum_{x_1=0}^1 \cdots \sum_{x_n=0}^1 z^{x_1+\cdots+x_n} f(x_1,\ldots,x_n) be its generating function as defined in the preceding exercise.
Section 7.1.4: Binary Decision Diagrams
Exercise 28. [M16] [M16] Let F(p) be the value of the reliability polynomial F(p1, . . . , pn) when p1 = · · · = pn = p. Show that it’s easy to compute F(p) from the generating function G(z).
Verified: no
Solve time: 5m
Solution
Let $f(x_1,\ldots,x_n)$ be a Boolean function and let $$ G(z)=\sum_{x_1=0}^1 \cdots \sum_{x_n=0}^1 z^{x_1+\cdots+x_n} f(x_1,\ldots,x_n) $$ be its generating function as defined in the preceding exercise.
Let $$ F(p_1,\ldots,p_n)=\sum_{x_1=0}^1 \cdots \sum_{x_n=0}^1 \prod_{k=1}^n (1-p_k)^{1-x_k} p_k^{x_k}, f(x_1,\ldots,x_n) $$ be the reliability polynomial.
Specialize to the case $p_1=\cdots=p_n=p$. Then every term in the product becomes $(1-p)^{1-x_k}p^{x_k}$, so the weight of a vector $x=(x_1,\ldots,x_n)$ depends only on $s=x_1+\cdots+x_n$. The product simplifies to $$ \prod_{k=1}^n (1-p)^{1-x_k}p^{x_k} = (1-p)^{n-s} p^s. $$
Define $$ A_s = \sum_{x_1=0}^1 \cdots \sum_{x_n=0}^1 [x_1+\cdots+x_n=s]; f(x_1,\ldots,x_n), $$ so that $A_s$ counts (with weight $f$) all assignments having exactly $s$ ones.
Then the reliability polynomial becomes $$ F(p)=\sum_{s=0}^n A_s p^s (1-p)^{n-s}. $$
The generating function satisfies $$ G(z)=\sum_{s=0}^n A_s z^s, $$ since grouping terms by Hamming weight $s$ produces exactly the same coefficients $A_s$.
Now rewrite $F(p)$ by factoring $(1-p)^n$: $$ F(p)=(1-p)^n \sum_{s=0}^n A_s \left(\frac{p}{1-p}\right)^s. $$
The inner sum is $G!\left(\frac{p}{1-p}\right)$ by substitution into the generating function. Therefore $$ F(p)=(1-p)^n G!\left(\frac{p}{1-p}\right). $$
This expresses the reliability polynomial with equal parameters directly in terms of the generating function.
$$ \boxed{F(p)=(1-p)^n, G!\left(\frac{p}{1-p}\right)} $$
This completes the solution. ∎