A source transmits a message (a string of symbols) over a noisy communication channel. Each symbol is $0$ or $1$ with probability $p$ and $1−p$, respectively, and is received incorrectly with probability $ϵ_0$ and $ϵ_1$, respectively. Errors in different symbol transmissions are independent.
In an effort to improve reliability, each symbol is transmitted three times and the received string is decoded by majority rule. In other words, a $0$ (or $1$) is transmitted as $000$ (or $111$, respectively), and it is decoded at the receiver as a $0$ (or $1$) if and only if the received three-symbol string contains at least two $0$'s (or $1$'s, respectively).
Suppose that the scheme of part (c) is used. What is the probability that a symbol was $0$ given that the received string is $101$?
I use $S_n^k$ to denote that $n$ was sent in the $k$th transmission and $R_n^k$ to denote that $n$ was received on the $k$th transmission. Given the problem, I tried to compute the following:
$$\begin{align} \mathbb{P}(S_0^1 \cap S_0^2 \cap S_0^3 | R_1^1 \cap R_0^2 \cap R_1^3) &= \frac {\mathbb{P}((S_0^1 \cap S_0^2 \cap S_0^3) \cap (R_1^1 \cap R_0^2 \cap R_1^3))}{\mathbb{P}( R_1^1 \cap R_0^2 \cap R_1^3)} \\ &= \frac {\mathbb{P}((S_0^1 \cap R_1^1) \cap (S_0^2 \cap R_0^2) \cap (S_0^3 \cap R_1^3))}{\mathbb{P}( R_1^1 \cap R_0^2 \cap R_1^3)} \\ &= \frac {\mathbb{P}(S_0^1 \cap R_1^1)\mathbb{P}(S_0^2 \cap R_0^2)\mathbb{P}(S_0^3 \cap R_1^3)}{\mathbb{P}(R_1^1)\mathbb{P}(R_0^2)\mathbb{P}(R_1^3)} \\ &= \frac {\mathbb{P}(R_1^1|S_0^1)\mathbb{P}(S_0^1)\cdot \mathbb{P}(R_0^2|S_0^2)\mathbb{P}(S_0^2)\cdot \mathbb{P}(R_1^3|S_0^3)\mathbb{P}(S_0^3)}{\mathbb{P}(R_1^1)\mathbb{P}(R_0^2)\mathbb{P}(R_1^3)}\end{align}$$
Now, to calculate the bottom probabilities:
$$\begin{align} \mathbb{P}(R_1^k) &= \mathbb{P}(R_1^k|S_1^k) \mathbb{P}(S_1^k) + \mathbb{P}(R_1^k|S_0^k) \mathbb{P}(S_0^k) \\ &= (1-\epsilon_1)(1-p) + \epsilon_0 p \end{align}$$
$$\begin{align} \mathbb{P}(R_0^k) &= \mathbb{P}(R_0^k|S_1^k) \mathbb{P}(S_1^k) + \mathbb{P}(R_0^k|S_0^k) \mathbb{P}(S_0^k) \\ &= \epsilon_1(1-p) + (1-\epsilon_0) p \end{align} $$
Putting all of this together we should get:
$$\mathbb{P}(S_0^1 \cap S_0^2 \cap S_0^3 | R_1^1 \cap R_0^2 \cap R_1^3) = \frac{(\epsilon_0 p)(1-\epsilon_0)p(\epsilon_0 p)}{((1-\epsilon_1)(1-p) + \epsilon_0 p)^2(\epsilon_1(1-p) + (1-\epsilon_0) p)}$$
However, the book says the right answer should be:
$$\frac {p\epsilon_0^2(1-\epsilon_0)}{p\epsilon_0^2(1-\epsilon_0)+(1-p)(1-\epsilon_1)^2\epsilon_1}$$
They arrived at this result by saying that the probability of a $0$ being sent is $p$ instead of $p^3$ which confuses me because according to the improvement, three consecutive zeroes should be sent, not just one. The numerator they also condition on only one zero being sent through.
Why am I wrong?
Best Answer
I think you just misunderstood the setup.
There is one symbol $0$ or $1$ chosen first, with respective probabilities $p$ and $1-p$. Then we send this one symbol three times. So we either sent $000$ or $111$. Then, the error in each symbol occurs independently with probability $\epsilon_0$ or $\epsilon_1$.
[Context: This is the how we try to figure out the original message from the noisy output: if we send the single symbol $0$ many many times, then most of the time the output will give $0$, and sometimes there will be errors (output $1$), but the majority will be the original symbol.]
You interpreted it as choosing three symbols, each independently with probability $p$ and $1-p$, and then sending each symbol once.