I am working on the following exercise:
Let $\mathcal{C} = (\mathcal{X} , P, \mathcal{Y})$ be a channel with $\mathcal{X} = \mathcal{Y} = \{0,1\}$ and transition matrix
$$ P = \begin{bmatrix}
7/8 &1/8 \\
1/8 &7/8
\end{bmatrix}.$$The input probabilities are $P[X = 0] = 0.3, P[X = 1] = 0.7$. Each input bit is encoded by
transmitting it through the channel $2n + 1$ times, and the decoding function is the majority
bit (the bit $0$ or $1$ that appears more times in the sequence of $2n + 1$ output bits).
Let $f(n)$ be the probability that the decoded bit is different from the encoded bit.Express $f(n)$ as a sum of the form $f(n) = \sum_{k=\ldots}^\ldots (\ldots)$.
My attempt: From $P$ we read that the probabilites for the channel makes a wrong output, i.e.: $p(0 \mid 1)$ and $p(1 \mid 0)$, are both $1/8$. So the error probability is given by the probability that at least $n+1$ many mistakes occur. We can calculate this via
$$\sum_{k=n+1}^{2n+1} 0.7 \cdot p(0 \mid 1)^k + 0.3 \cdot p(1 \mid 0)^k = \sum_{k=n+1}^{2n+1} (1/8)^k$$
Is this correct?
Best Answer
I think decomposing the error probability in terms of number of flipped bits is the way to go, but the summand is incorrect. $0.7p(0|1)^k$ is the probability of sending the bit $1$ and observing at least $k$ bit flips. This outcome still counts events with $k, k+1,..., 2n+1$ bit errors because you are not putting any restrictions on the remaining $2n+1-k$ bits.
Let $E_k$ denote the event of $k$ bit flips. Then, $f(n) = \sum_{k=n+1}^{2n+1} P(E_k)$.
To find $E_k$, you need to count bit flips exactly; $k$ bit errors and $(2n+1-k)$ correctly received bits: \begin{align} P(E_k) = 0.7 P(E_k \vert 1 \text{ sent}) + 0.3 P(E_k \vert 0 \text{ sent}) = \left(\frac{1}{8}\right)^k\left(\frac{7}{8}\right)^{2n+1-k} \end{align}
So,
$$f(n) = \sum_{k=n+1}^{2n+1}\left(\frac{1}{8}\right)^k\left(\frac{7}{8}\right)^{2n+1-k}$$