Black Boxes in a Chain


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}$


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.


|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny