TAOCP 3.4.1 Exercise 25
Let E_t=X_1\mid\bigl(X_2\mathbin{\&}(X_3\mid(X_4\mathbin{\&}X_5)\cdots)\bigr) denote the nested expression.
Section 3.4.1: Numerical Distributions
Exercise 25. [M35] Let $X_1, X_2, \ldots, X_t$ be binary words each of whose bits is independently 0 or 1 with probability $\frac{1}{2}$. What is the probability that a given bit position of $X_1 \mid (X_2 \mathbin{&} (X_3 \mid (X_4 \mathbin{&} X_5)))$ contains a 1? Generalize.
Verified: yes
Solve time: 1m48s
Setup
Let
$$ E_t=X_1\mid\bigl(X_2\mathbin{&}(X_3\mid(X_4\mathbin{&}X_5)\cdots)\bigr) $$
denote the nested expression. Since corresponding bit positions of the words are independent and identically distributed, the probability sought is the probability that a fixed bit position of $E_t$ equals $1$.
Let $p_t$ be the probability that a given bit position of the expression
$$ X_1\mid\bigl(X_2\mathbin{&}(X_3\mid(X_4\mathbin{&}\cdots X_t)\cdots)\bigr) $$
is $1$. Each bit of each $X_j$ is independently $1$ with probability $\frac12$.
We must determine $p_5$ and then obtain a general formula.
Solution
For a fixed bit position, replace each word by a Bernoulli random variable
$$ B_j\in{0,1},\qquad \Pr{B_j=1}=\Pr{B_j=0}=\frac12, $$
with the $B_j$ independent.
Let
$$ q_t=1-p_t $$
be the probability that the corresponding bit of the nested expression equals $0$.
For a single variable,
$$ p_1=\frac12,\qquad q_1=\frac12. $$
Suppose the outermost operation is OR. Then
$$ E=B_1\mid F, $$
where $F$ is independent of $B_1$ and has probability $p$ of being $1$.
The bit of $E$ is $0$ only when both $B_1=0$ and $F=0$; hence
$$ q=\frac12(1-p)=\frac12 q_F. $$
Therefore an OR operation transforms $q$ into $\frac12 q$.
Similarly, suppose the outermost operation is AND:
$$ E=B_1\mathbin{&}F. $$
The bit of $E$ is $1$ only when both operands are $1$; hence
$$ p=\frac12 p_F. $$
Equivalently,
$$ q=1-\frac12(1-q_F) =\frac12+\frac12 q_F. $$
Therefore an AND operation transforms $q$ into
$$ q\mapsto \frac12+\frac12 q. $$
Now compute from the inside outward. Define
$$ q_1=\frac12, $$
and for $n\ge2$,
$$ q_n= \begin{cases} \dfrac12,q_{n-1}, & n \text{ odd},\[2ex] \dfrac12+\dfrac12,q_{n-1}, & n \text{ even}. \end{cases} $$
The first values are
$$ q_1=\frac12, $$
$$ q_2=\frac12+\frac14=\frac34, $$
$$ q_3=\frac12 q_2=\frac38, $$
$$ q_4=\frac12+\frac12\cdot\frac38=\frac{11}{16}, $$
$$ q_5=\frac12\cdot\frac{11}{16}=\frac{11}{32}. $$
Hence
$$ p_5=1-q_5 =1-\frac{11}{32} =\frac{21}{32}. $$
Therefore the required probability is
$$ \boxed{\frac{21}{32}}. $$
To obtain the general form, separate odd and even indices:
$$ a_m=q_{2m-1},\qquad b_m=q_{2m}. $$
The recurrence gives
$$ b_m=\frac12+\frac12 a_m, $$
and
$$ a_{m+1}=\frac12 b_m =\frac14+\frac14 a_m. $$
Thus
$$ a_{m+1}-\frac13 =\frac14\left(a_m-\frac13\right). $$
Since
$$ a_1=\frac12, $$
we obtain
$$ a_m=\frac13+\frac16,4^{-(m-1)}. $$
Therefore
$$ q_{2m-1} =\frac13+\frac16,4^{-(m-1)}, $$
and
$$ q_{2m} =\frac12+\frac12 q_{2m-1} =\frac23+\frac1{12},4^{-(m-1)}. $$
Hence
$$ p_{2m-1} =1-q_{2m-1} =\frac23-\frac16,4^{-(m-1)}, $$
and
$$ p_{2m} =1-q_{2m} =\frac13-\frac1{12},4^{-(m-1)}. $$
These formulas give the probability that a fixed bit position is $1$ in the alternating expression of length $t$.
Verification
For $t=3$,
$$ p_3 =\frac23-\frac1{24} =\frac58. $$
Directly,
$$ p_3 =1-\Pr{B_1=0,;B_2\mathbin{&}B_3=0} =1-\frac12\left(1-\frac14\right) =\frac58. $$
The values agree.
For $t=5$,
$$ p_5 =\frac23-\frac1{96} =\frac{63}{96} =\frac{21}{32}, $$
which matches the recurrence computation.
Notes
As $t\to\infty$,
$$ p_{2m-1}\to\frac23, \qquad p_{2m}\to\frac13. $$
Thus the probability oscillates between limits $\frac23$ and $\frac13$ according to the parity of the number of operands. ∎