# Black Boxes in a Chain

### Problem ### Solution 1

The original input and the final output will coincide if the number of input/output reversals is even; they'll differ if the number of reversals is odd.

Imagine that the boxes before making a transmission toss a coin that comes up a heads with probability $p.$ And this is what decides the behavior of the box. We know that after $N$ transmissions the probability of having an even number of heads is $\displaystyle P(N)=\frac{1}{2}+\frac{1}{2}(1-2p)^N.$

If $N$ is even, then the probability of having an even number of tails, i.e., an even number input/output reversals is $\displaystyle Q(N)=P(N)=\frac{1}{2}+\frac{1}{2}(1-2p)^N.$ But, if $N$ is odd then getting an even number of tails is the same as getting an odd number of heads, i.e.,

$\displaystyle Q(N)=1-P(N)=1-\left(\frac{1}{2}+\frac{1}{2}(1-2p)^N\right)=\frac{1}{2}-\frac{1}{2}(1-2p)^N.$

The two expressions for $Q(N)$ can be combined into a single formula:

$\displaystyle Q(N)=\frac{1}{2}+\frac{(-1)^N}{2}(1-2p)^N=\frac{1}{2}+\frac{1}{2}(2p-1)^N.$

### Solution 2

With the same reasoning as above, if $q=1-p$ then the probability of getting an even number of tails is

\displaystyle\begin{align}Q(N)&=\frac{1}{2}+\frac{1}{2}(1-2q)^N\\ &=\frac{1}{2}+\frac{1}{2}(1-2(1-p))^N\\ &=\frac{1}{2}+\frac{1}{2}(2p-1)^N. \end{align}

### Solution 3

Any number of flips will do. Let $x=p$ and $y=1-p.$ Then the required probability is

\displaystyle\begin{align}\sum_{k\text{ is even}}^N&=\frac{1}{2}\left[(y+x)^N+(y-x)^N\right]\\ &=\frac{1}{2}\left[1+(2p-1)^N\right].\end{align}

### Acknowledgment

This is a modification of a problem from P. J. Nahin's Will You Be Alive 10 Years from Now? (Princeton University Press, 2014).

Solution 3 is by Amit Itagi. 