<p>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.</p>

CC BY-SA 3.0
2016-10-16T21:54:49.673Z
2016-10-16T21:54:49.673Z
kodlu
<p>From Cover &amp; Thomas' <em>Elements of Information Theory</em>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

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

<it.information-theory><shannon-entropy><prefix-free-code>
Lower bound on the number of objects in the universe
user42880
# Lower bound on the number of objects in the universe

(Asked by: username_0 on 2016-10-16)

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?

**Tags:** it.information-theory, shannon-entropy, prefix-free-code

---

## 1 answers

### Answer by username_1 on 2016-10-16. Score: 3

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.


---

