Suppose that the signal $X$ is drawn as…
$$
X =
\begin{cases}
1 & \style{font-family:inherit}{\text{with probability 1/2}} \\
0 & \style{font-family:inherit}{\text{with probability 1/2}}
\end{cases}
$$
& the conditional pmf $P\left[Y = y\;|\;X = x\right]$ of $Y$ given $X$ is specified by…
$$
\begin{array}{l}
P\left[Y = 1\;|\;X = 1\right] = 1 \\
P\left[Y = 1\;|\;X = 0\right] = 1/2
\end{array}
$$
-
Find the optimal decoder $d\left(y\right)$ that minimizes the
probability of error $P\left[X \ne d\left(Y\right)\right]$. -
Find the associated probability of error.
Based on the information given, I constructed the following probability table…
$$
\begin{array}{c|c|c|c}
& X = 0 & X = 1 & \style{font-family:inherit}{\text{Total}} \\\hline
Y = 1 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4} \\\hline
Y = 0 & \frac{1}{4} & 0 & \frac{1}{4} \\\hline
\style{font-family:inherit}{\text{Total}} & \frac{1}{2} & \frac{1}{2} & 1
\end{array}
$$
Using the table, I have the answers to every conditional probability…
- $P\left[X = 0 | Y = 0\right] = 1$.
- $P\left[X = 0 | Y = 1\right] = 1/3$.
- $P\left[X = 1 | Y = 0\right] = 0$.
- $P\left[X = 1 | Y = 1\right] = 2/3$.
- $P\left[Y = 0 | X = 0\right] = 1/2$.
- $P\left[Y = 0 | X = 1\right] = 0$.
- $P\left[Y = 1 | X = 0\right] = 1/2$.
- $P\left[Y = 1 | X = 1\right] = 1$.
From here, could you explain how to find $d\left(y\right)$ for this problem &, if you're feeling generous, any problem like it?
FYI: This is not hw; I am practicing for a qualification exam.
Best Answer
In this context, a decoder maps observed $Y$'s to guessed $X$'s, i.e. $d: \{0,1\} \rightarrow \{0, 1\}$. Or in other words, you are choosing $d(0)$ (what $X$ to guess when seeing $Y=0$) and $d(1)$ (what $X$ to guess when seeing $Y=1$). And you want to minimize the prob of guessing wrong, i.e. when $d(Y)$ (i.e. the guess) $\neq X$ (i.e. the actual signal).
At this point, if you stare at the $2 \times 2$ probability table, it should be "really obvious" that you should guess $d(0) = 0$, because if you see $Y=0$ then it is certain that $X=0$. The question is what to guess when seeing $Y=1$, but it should also be "somewhat obvious" :) that in that case you should guess $d(1) = 1$. We will prove these rigorously now.
$$ \begin{align} P(d(Y) \neq X) &= P(d(Y) \neq X | Y = 1) P(Y=1) + P(d(Y) \neq X | Y=0) P (Y=0)\\ &=P(d(1) \neq X | Y=1)P(Y=1) + P(d(0) \neq X | Y=0) P(Y=0) \end{align}$$
Note that, as far as the minimization is concerned, $P(Y=1), P(Y=0)$ are constants. Since we can choose $d(0), d(1)$ independently, we can minimize each term separately. Formally we're doing this:
$$d(i) = \arg\min_{j \in \{0,1\}} P(j \neq X | Y = i) = \arg \max_{j \in \{0,1\}} P(j = X | Y = i)$$
I.e. for each case of $Y=i$, simply find the most probable $X$ (conditioned on $Y=i$). I would say this is a general feature of all kinds of decoding.
First, $P(d(0) \neq X | Y = 0)$: Conditioned on $Y=0$, we have $X=0$ with certainty. Nothing is more probable than certainty. So we choose $d(0) = 0$.
Next, $P(d(1) \neq X | Y = 1)$: You can easily calculate that $P(X=1 | Y = 1) = {2 \over 3}$, and $P(X=0 | Y = 1) = {1 \over 3}$. Since $X=1$ is more probable (conditioned on $Y=1$), we choose $d(1) = 1$.
With these optimal choices of $d(0) = 0, d(1) = 1$, the overall error prob is:
$$ \begin{align} P(d(Y) \neq X) &= P(d(1) \neq X | Y=1)P(Y=1) + P(d(0) \neq X | Y=0) P(Y=0) \\ &= P(1 \neq X | Y=1)P(Y=1) + P(0 \neq X | Y=0) P(Y=0) \\ &= {1 \over 3} \cdot {3 \over 4} + 0 \cdot {1 \over 4} = {1 \over 4} \end{align}$$
Another way to find the overall error prob is to augment your table with your choices (remember that $d()$ is a deterministic function, depending on $Y$ only), and then realize the red entries are the cases when you guess wrong:
\begin{array}{c|c|c|c} & X = 0 & X = 1 & \style{font-family:inherit}{\text{Total}} \\\hline Y = 1 \iff d(Y) = 1 & \color{red}{\frac{1}{4}} & \frac{1}{2} & \frac{3}{4} \\\hline Y = 0 \iff d(Y) = 0 & \frac{1}{4} & \color{red}{0} & \frac{1}{4} \\\hline \style{font-family:inherit}{\text{Total}} & \frac{1}{2} & \frac{1}{2} & 1 \end{array}