TAOCP 7.1.1 Exercise 133
Let the outcomes of the $n$ independent coins be $x=(x_1,\ldots,x_n)\in{0,1}^n$, with $\Pr(x_k=1)=p_k,\qquad \Pr(x_k=0)=1-p_k.$ Write the index of a bit string $x$ as $i(x)=x_1+2x_2+4x_3+\cdots+2^{n-1...
Exercise 133. [20] [20] (Mark A. Smith, 1990.) Suppose we flip $n$ independent coins to get $n$ random bits, where the $k$th coin produces bit 1 with probability $p_k$. Find a way to choose $(p_1, \ldots, p_n)$ so that $f(x_1, \ldots, x_n) = 1$ with probability $(l_0 l_1 \cdots l_{2^n - 1})/(2^{2^n} - 1)$, where $l_0 l_1 \ldots l_{2^n-1}$ is the truth table of the Boolean function $f$. (Thus, $n$ suitable random coins can generate a probability with any $2^n$-bit precision.)
By and large the minimization of switching components outweighs all other engineering considerations in designing economical logic circuits., H. A. CURTIS, A New Approach to the Design of Switching Circuits (1962)
He must be a great calculator indeed who succeeds. Simplify, simplify., HENRY D. THOREAU, Walden; or, Life in the Woods (1854)
Verified: yes
Solve time: 1m47s
Solution
Let the outcomes of the $n$ independent coins be $x=(x_1,\ldots,x_n)\in{0,1}^n$, with
$\Pr(x_k=1)=p_k,\qquad \Pr(x_k=0)=1-p_k.$
Write the index of a bit string $x$ as
$i(x)=x_1+2x_2+4x_3+\cdots+2^{n-1}x_n.$
The truth table of $f$ is the sequence $l_0l_1\ldots l_{2^n-1}$, so the desired probability is
$\frac{\sum_{i=0}^{2^n-1} l_i 2^i}{2^{2^n}-1},$
since the binary number $l_0l_1\ldots l_{2^n-1}$ equals $\sum l_i 2^i$.
Define
$q_k = 2^{2^{k-1}}.$
Then
$\prod_{k=1}^n q_k^{x_k} = 2^{\sum_{k=1}^n x_k 2^{k-1}} = 2^{i(x)}.$
Also set
$p_k = \frac{q_k}{1+q_k} = \frac{2^{2^{k-1}}}{1+2^{2^{k-1}}}, \qquad 1-p_k = \frac{1}{1+q_k}.$
For each $x\in{0,1}^n$, independence gives
$\Pr(x)=\prod_{k=1}^n p_k^{x_k}(1-p_k)^{1-x_k}.$
Substituting the expressions for $p_k$ and $1-p_k$ yields
$\Pr(x)=\prod_{k=1}^n \frac{q_k^{x_k}}{1+q_k} = \frac{\prod_{k=1}^n q_k^{x_k}}{\prod_{k=1}^n (1+q_k)} = \frac{2^{i(x)}}{\prod_{k=1}^n (1+2^{2^{k-1}})}.$
The denominator simplifies using
$\prod_{k=1}^n (1+2^{2^{k-1}})=\prod_{k=1}^n (1+q_k)=\sum_{x\in{0,1}^n} \prod_{k=1}^n q_k^{x_k}=\sum_{i=0}^{2^n-1} 2^i=2^{2^n}-1.$
Thus
$\Pr(x)=\frac{2^{i(x)}}{2^{2^n}-1}.$
The probability that $f(x)=1$ equals
$\sum_{x:,f(x)=1} \Pr(x)=\frac{\sum_{x:,f(x)=1} 2^{i(x)}}{2^{2^n}-1}=\frac{\sum_{i=0}^{2^n-1} l_i 2^i}{2^{2^n}-1}.$
This matches the required value.
This completes the proof. ∎