4
$\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$
0

1 Answer 1

3
$\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$ 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .