-2
$\begingroup$

From Cover & Thomas' Elements of Information Theory:

Player A chooses some object in the universe, and player B attempts to identify the object with a series of yes–no questions. Suppose that player B is clever enough to use the code achieving the minimal expected length with respect to player A’s distribution. We observe that player B requires an average of 38.5 questions to determine the object. Find a rough lower bound to the number of objects in the universe.

The solution in the solutions manuals is $37.5 = L^* - 1 < H(X) \leq log|\chi|$.

Why can we be sure that the difference between the minimum expected length and $1$ is smaller than the entropy?

$\endgroup$
3
$\begingroup$

Because an optimal prefix free code, e.g. a Huffman code, can be shown to be within one bit of source entropy. This is certainly in Cover and Thomas, I am pretty sure.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.