0
$\begingroup$

Having an old exercise book without a solution to backward-engineer it.I would like the concept to be explained.

Having a race between 17 people, the 1st person has 3/4 posibility of winning and all (16) others have 1/64 posibility each.

If after the race we get a message that the winner was not the 1st, what is the information that message contains, and how much uncertainty is left about the winner of the race?

$\endgroup$
1
$\begingroup$

Let $X$ be a random variable representing the winner, with possible values $\{x_1, x_2, \ldots, x_{17}\}$. Then its pmf is: $$ P(X) = \begin{cases} 3/4 & \text{if } X = x_1 \\ 1/64 & \text{otherwise} \end{cases} $$

The Shannon entropy (i.e.: uncertainty) before the race is: $$ H(X) = -\sum_{i=1}^{17} P(x_i) \log_2 P(x_i) = -\frac{3}{4}\log_2 \frac{3}{4} - 16\left( \frac{1}{64}\log_2 \frac{1}{64} \right) = 1.8112\ldots $$

With the message, the new pmf looks like this: $$ P(X \mid X \neq x_1) = \begin{cases} 0 & \text{if } X = x_1 \\ 1/16 & \text{otherwise} \end{cases} $$

So after receiving the message, the Shannon entropy (i.e.: uncertainty) becomes: \begin{align*} H(X \mid X \neq x_1) &= -\sum_{i=1}^{17} P(X = x_i \mid X \neq x_1) \log_2 P(X = x_i \mid X \neq x_1) \\ &= 0 - 16\left( \frac{1}{16}\log_2 \frac{1}{16} \right) \\ &= 4 \end{align*}

So the information gained was: $$ H(X) - H(X \mid X \neq x_1) = 1.8112 \ldots - 4 = -2.1887\ldots $$


Remark: It should make sense that the message provided negative information, since the result of the race suddenly became more uncertain. The 1st person used to be a sure bet - now anyone can win. In general, uniform distributions have more uncertainty than heavily skewed distributions.

$\endgroup$
  • $\begingroup$ Can't understand the last part 'information gained', it can be negative? and what we understand if information is negative? $\endgroup$ – ChonChon Apr 3 at 8:08
0
$\begingroup$

The event that correspond to having somebody else then the first to win have probability $1/4$, the amount of information is usually measured with the $-\log_2$ function (at least in information theory and for entropy and such information measures), hence the information contained in the message is $-log_2(1/4) = 2$ bits.

The uncertainty left about the race is the expected amount of information that remains. When we know the first runner isn't the winner then the winner is uniformly distributed over the rest of the $16$ other runners by symmetry hence the entropy is $-16\cdot\frac{1}{16}\log_2\left( \frac{1}{16} \right)=4$ bits.

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