3
$\begingroup$

Setup: Alice and Bob are playing a cooperative game. Alice chooses a number $y \in \{1, 2, 3, 4\}$ uniformly at random. Bob doesn't observe $y$; his goal is to guess $y$. Alice can send Bob a message $z$ that contains at most 1 bit of information about $y$ (i.e., $I(z;y) = 1$).

Problem: How should Alice encode information about $y$ into her message $z$?


Potential Solutions: I have three ideas for what Alice should do, but they all give contradictory answers.

  1. If $y \in \{1, 2\}$, Alice sends $z = 0$; otherwise, Alice sends $z = 1$. The code $z$ contains 1 bit of information. Bob will guess $y$ correctly with probability 0.5.
  2. With probability 1/2, Alice sends $z = y$ (2 bits); otherwise, Alice sends some null message (0 bits). Thus, Alice sends 1 bit in expectation. Bob will guess $y$ correctly in the first case; in the second case, he will guess randomly and be correct with probability 0.25. In total, Bob will guess $y$ correctly with probability $0.5 \cdot 1.0 + 0.5 \cdot 0.25 = 0.625$.
  3. Alice samples $z$ from the following 4-dimensional Categorical distribution that places probability 0.811 on $z = y$ and probability 0.063 on the other 3 atoms. The marginal $p(z)$ is uniform, so $H(z) = \log_2(4) = 2$; the conditional $p(z \mid y)$ has entropy $$H(z \mid y) = 0.811 \cdot \log_2(\frac{1}{0.811}) + 3 \cdot 0.063 \cdot \log_2(\frac{1}{0.063}) \approx 1 $$ The information content of Alice's message is $I(z;y) = H(z) - H(z \mid y) = 1$. Bob's guess will be whatever message Alice sends, so he'll guess $y$ correctly with probability 0.811.
$\endgroup$
2
$\begingroup$

The problem statement is a little neater for me if put in the following way:

Let $Y$ be uniform on $ \{1, 2, 3, 4\}$. We will guess $Y$ from a variable $Z$, i.e. $\hat Y =g(Z)$, with $I(Y;Z)=1$ bit. The goal is minimizing the probability of error $p_e=P(\hat Y \ne Y)$. We want to find the optimal joint distribution for $Y,Z$ (in terms of channels: find the optimal channel with $Y$ as input and $Z$ as output), and the corresponding guess function $\hat Y=g(Z)$.

Your three answers are not "contradictory", they are just different (valid) proposals that give different results. It would be contradictory to assume that they are all optimal - at most the third one can be.

To assert this, we recall Fano's inequality.

In our scenario, we have $H(Z)=2 \implies H(Z | Y)= H(Z)-I(Z;Y)=1$, so we get the bound $$ 1 \le h(p_e) + p_e \log(3) \tag{1}$$ where $h()$ is the binary entropy function. The critical value (which gives an equality) is $p^*_e = 0.18929\cdots $. Then the probability of correct decoding cannot be greater than $ 1-p^*_e=0.81071\cdots$.

Your solution $3$ would correspond to a $4-$ary channel which has "crossover" probability $p$, so that, say $P(Z | Y= 1)= ( 1-p, \frac{p}{3}, \frac{p}{3}, \frac{p}{3})$. Then, given that $Y$ is uniform, the conditional entropy would be

$$\begin{align} H(Z|Y) &= \sum_i p(Y=i) H(Z|Y=i)\\ &= H(Z|Y=1)\\ &=-(1-p)\log(1-p) - 3\frac{p}{3}\log(\frac{p}{3}) \\ &=-(1-p)\log(1-p) - p \log(p) + p \log(3) \\ &=h(p) + p \log(3) \\ \end{align}$$

The value of $p$ that verifies $H(Z|Y)=1$ concides with that $(1)$. And, indeed, in this schema with guess $\hat Y= Z$, so $p$ is also the probability of decoding error. Hence this schema attains the Fano bound, and it must be the optimal one.

$\endgroup$

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.