# Capacity of cascade binary symmetric channels

Let's imagine that we have interconnected in cascade $L$ binary symmetric channels each with the same transition probability $p(y|x) \in \{p, q=1-p\}$, where the output of each BSC is connected to the input of the next.

The overall channel is also a BSC channel, but what happens as $L \to \infty$?

A binary symmetric channel (BSC) can be characterized by its complemented probability $p$. Its well-known capacity is

$$C = 1 - H(p) = 1 - (-p\log(p) - (1-p)\log(1-p))$$

where $H(p)$ is binary entropy function:

A $L-$concatenated BSC, which is also a BSC characterized by $p_L$, can be visualized as in the figure below

The complemented probability $p_L$ is derived

\begin{align} p_L &= p_{L-1} (1-p) + (1-p_{L-1}) p \\ &= p + (1-2p)p_{L-1}\\ \implies 1 - 2 p_L &= (1-2p)(1-2p_{L-1}) \\ \implies 1 - 2 p_L &= (1-2p)^L \\ \end{align}

Thus $$p_L = \frac{1}{2}(1 - (1-2p)^L)$$

If $p=0$ then $p_L = 0$, $H(p_L) = 0$ and $C = 1$.

If $p=1$ then $p_L = 0$ or $p_L = 1$ depending on $L$ is pair or impair; $H(p_L) = 0$ and $C = 1$.

If $0 < p < 1$ then $\lim_{L \to \infty} p_L = 0.5$; $H(p_L) = 1$ and $C = 0$.

Conclusion: if the unit BSC is not certain $(p \neq 0, 1)$, the capacity of infinitely-concatenated BSC tends to $0$.

• Wow @AlexTP . Incredible answer but how did you get from: p_L =p+(1-2p)p_{L-1} To: p_L = \frac{1}{2}(1 - (1-2p)^L) ? Thank you!! – Cristo Oct 6 '17 at 13:59
• @Cristo see my update – AlexTP Oct 6 '17 at 15:41
• @Cristo you may be interested in Dilip Sarwate's approach, which is much natural, to prove the complemented probability of $L$-cascade BSC. – AlexTP Oct 10 '17 at 9:31

A cascade of $L$ binary symmetric channels (BSCs) with cross-over probability $p$ is the same as a single BSC with cross-over probability $$p_L = \left.\left.\frac 12 \right(1 - (1-2p)^L\right).\tag{1}$$ To get to $(1)$, note that the cascaded BSC output is incorrect if and only if the transmitted bit was flipped an odd number of times as it traversed the cascade; even numbers of flips result in error-free transmission in accordance with the age-old principle that two wrongs make a right. The number of flips is a Binomial$(L,p)$ random variable $X$ for which \begin{align} P(X ~\text{odd}) &= \sum_{i=1,3,5,\ldots}\binom{L}{i}p^i (1-p)^{L-i}\\ &= ~~~\frac 12\left(\sum_{i=1,3,5,\ldots}\binom{L}{i}p^i (1-p)^{L-i} + \sum_{i=0,2,4,\ldots}\binom{L}{i}p^i (1-p)^{L-i}\right)\\ & ~~~~+ \frac 12\left(\sum_{i=1,3,5,\ldots}\binom{L}{i}p^i (1-p)^{L-i} - \sum_{i=0,2,4,\ldots}\binom{L}{i}p^i (1-p)^{L-i}\right)\\ &= \frac 12\left(\sum_{i=0}^L\binom{L}{i}p^i (1-p)^{L-i} - \sum_{i=0}^L \binom{L}{i}(-p)^i (1-p)^{L-i} \right)\\ &= \left.\left.\frac 12 \right(1 - (1-2p)^L\right). \end{align} As AlexTP points out, $p_L \to \frac 12$ for all $p \in (0,1)$, and so the non-trivial cascaded BSC has capacity approaching $0$ as $L \to \infty$.