# Optimal code for simple game

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.

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$$ coincides with the one given by $$(1)$$. And, indeed, in this schema we guess $$\hat Y= Z$$, so $$p$$ is also the probability of decoding error. Hence this schema attains the Fano bound, and hence it must be the optimal one.