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:

enter image description here

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

L concatenated BSC

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

  • $\begingroup$ 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!! $\endgroup$ – Cristo Oct 6 '17 at 13:59
  • $\begingroup$ @Cristo see my update $\endgroup$ – AlexTP Oct 6 '17 at 15:41
  • $\begingroup$ @Cristo you may be interested in Dilip Sarwate's approach, which is much natural, to prove the complemented probability of $L$-cascade BSC. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.