Here's the problem as it has been posed to me:
Suppose a message sent through a binary symmetric channel with probability $p_1$ that a symbol is transmitted incorrectly. The received symbol is then sent through a second binary symmetric channel where the symbol error probability is $p_1'$. Show that this process is equivalent to a single channel with some symbol error probability $p_2$. Find $p_2$ in terms of $p_1$ and $p_1'$. Hence express $1-2p_2$ in terms of $1-2p_1$ and $1-2p_1'$. Conclude that $p_2 < \frac{1}{2}$ if $p_1, p_1' < \frac{1}{2}$. Explain what happens when a message is sent through $n$ binary symmetric channels each with symbol error probability $p<\frac{1}{2}$, and $n$ becomes larger and larger.
Here's my attempt:
$p_2=(1-p_1)p_1'+p_1(1-p_1')+(1-p_1)p_1'+p_1(1-p_1') = 2p_1+2p_1'-4p_1p_1'$
$1-2p_2=1-2(2p_1+2p_1'-4p_1p_1')=1-4p_1-4p_1'+8p_1p_1'=2(1-2p_1)(1-2p_1')-1$
I hope this is not too silly of a question, but I'm unable to see how to conclude that $p_2<\frac{1}{2}$. I'd love a bit of help getting started on the next part of the problem if that's also not too much to ask!
Thanks! :-)
From my understanding of the question, you should have $p_2=(1-p_1)p_1'+p_1(1-p_1') = p_1 + p_1'-2p_1p_1'$. Because the probability of a fail is either succeed/fail or fail/succeed. WLOG, let's assume $p_1' \leq p_1$. So we can write $p_1' = \alpha p_1$ for some $\alpha \leq 1$. Now we have to show $p_1 + \alpha p_1 -2\alpha p_1^2 < \frac12$ assuming $p_1 < \frac12$. Differentiating $p_1 + \alpha p_1 -2\alpha p_1^2$ we get $1 + \alpha -4\alpha p_1$. This slope is always positive whenever $p_1 \leq \frac{1 + \alpha}{4 \alpha}$. But $\alpha \leq 1$ implies $\frac12 \leq \frac{1 + \alpha}{4 \alpha}$. And we already have $p_1 \leq \frac12$. So the slope is always positive, and so the maximum is at the boundary of $p_1 = \frac12$, giving $\frac12 + \frac12 \alpha -\frac12 \alpha = \frac12$. So with $p_1 < \frac12$ this function is always less than $\frac12$, which answers the first part of the question.