A space probe is controlled by 7 different instructions from the ground. the probabilities of sending these instructions vary -
the three most common instructions have probabilities 1/2, 1/4, and 1/8 of being sent, respectively. the remaining four instructions are equally likely to be sent. in expectation, what is the minimum number of whole number bits required to communicate with the probe?
<span>2
This problem involves entropy and Shannon information density. Let's look at the base 2 logarithm of the probability of each command. For convience, I'll call the commands a,b,c,d,e,f,g with the most frequent commands having earlier letters in the sequence. So the commands, their probability, and the base 2 logarithms are:
a: 0.5, -1
b: 0.25, -2
c: 0.125, -3
d: 0.03125, -5
e: 0.03125, -5
f: 0.03125, -5
g: 0.03125, -5
Now let's negate each of the base 2 logarithms, so we have the values 1,2,3,5,5,5,5. Those numbers represent the number of bits of information that each command represents. We expect command "a" half the time, so a single bit is all we need. Command "b" takes 2 bits, and so on for the remaining 5 commands. So the expected number of bits to be sent is simply the probability of each command multiplied by the number of bits to represent that command. Therefore:
0.5 * 1 + 0.25 * 2 + 0.125 * 3 + 0.03125 * 5 + 0.03125 * 5 + 0.03125 * 5 + 0.03125 * 5
= 0.5 + 0.5 + 0.375 + 0.15625 + 0.15625 + 0.15625 + 0.15625
= 2
Now let's demonstrate such an encoding. I'll use Huffman encoding for this example, but I'm not going to demonstrate how to derive the actual encoding since this is beyond the scope of this problem. For the command "a", I'll use the single bit "0".
a: 0
So if the probe see the single bit "0", it knows that command "a" is being sent. And if it see the value "1", it knows that more bits are being sent for another command. So for the command "b", I'll use the sequence "10". So the command table looks like:
a: 0
b: 10
And going further, the entire command table can look like:
a: 0
b: 10
c: 110
d: 11100
e: 11101
f: 11110
g: 11111
Notice that none of the shorter bit sequences is a prefix for any of the longer sequences. This allows the shorter sequences to be recognized the moment that they've been sent. Additionally, the above table isn't the only possible encoding scheme.</span>
The space probe needs to be able to differentiate 7 different type of command. The possible way that can be code by n bits would be 2^n. Then, the number of bits for coding at least 7 different commands would be:
