Questions on Information

Problem : Measuring information

A.   Someone picks a name out of a hat known to contain the names of 5 women and 3 men, and tells you a man has been selected. How much information have they given you about the selection?

Answer: -

There are 8 names to start with and knowing the selection is a man narrows the choices down to 3 names. Using the formula from lecture with N = 8 and M = 3, we've been given log₂(8/3) bits of information.

Alternatively, the probability of drawing a man's name is p_man = 3/8, so the amount of information received is log₂(1/p_man) = log₂(1/(3/8)) = log₂(8/3).

B.    You're given a standard deck of 52 playing cards that you start to turn face up, card by card. So far as you know, they're in completely random order. How many new bits of information do you get when the first card is flipped over? The fifth card? The last card?

Answer: -

Before the first card was flipped over there are 52 choices for what we'll see on the first flip. Turning the first card over narrows the choice down to a single card, so we've received log₂(52/1) bits of information.

After flipping over 4 cards, there are 48 choices for the next card, so flipping over the fifth card gives us log₂(48/1) bits of information.

Finally if all but one card has been flipped over, we know ahead of time what the final card has to be so we don't receive any information from the last flip. Using the formula, there is only 1 "choice" for the card before the card is flipped and we have the same "choice" afterwards, so, we receive log₂(1/1) = 0 bits of information.

C.    X is an unknown N-bit binary number (N > 3). You are told that the first three bits of X of 011. How many bits of information about X have you been given?

Answer: -

Since we were told about 3 bits of X it would make sense intuitively that we've been given 3 bits of information! Turning to the formulas: there are 2^N N-bit binary numbers and 2^N-3 N-bit binary numbers that begin with 011. So we've been given log₂(2^N/2^N-3) = log₂(2³) = 3 bits of information (whew!).

D.  X is an unknown 8-bit binary number. You are given another 8-bit binary number, Y, and told that the Hamming distance between X and Y is one. How many bits of information about X have you been given?

Answer: -

Before we learn about Y, there are 2⁸ = 256 choices for X. If the Hamming distance between X and Y is one that means that X and Y differ in only one of their 8 bits, i.e., for a given Y there are only eight possible choices for X. So we've been given log₂(256/8) = 5 bits of information.