In his Probability Theory (Dover edition, pages 541 and 542; luckily the pages are available on [Google Books]), Renyi derives Hartley's formula the following way:

Given an alphabet of $N$ elements, we can choose a sequence of $k$ elements. There are $N^k$ such sequences, and if we want to uniquely identify each, we need $n_k$ bits. $n_k$ is characterized by:

$$ 2^{n_k-1} < N^k \leq 2^{n_k} $$

From here we can easily get to the inequality

$$ k \log_2 N \leq n_k < k \log_2 (N+1) $$

Now comes a statement that I don't understand. He writes that “it follows”:

$$ \lim_{k\to\infty} \frac{n_k}{k} = \log_2 N $$

This statement is not obvious to me. Can somebody help me think about why the inequality turns into an equality?

Is this statement in any way connected to what follows immediately after?

Thus for every $\epsilon > 0$ we can find a number $k$ such that if we take the elements of $E$ by ordered groups of $k$, then the identification of one element requires on the average less than $\log_2 N + \epsilon$ binary digits.

  • 1
    $\begingroup$ There is something wrong in your statement. The correct version is: $$ k \log_2 N \leq n_k < k \log_2 (N)+1. $$ Can you now see how it works? $\endgroup$ – Arash Aug 25 '17 at 22:17
  • $\begingroup$ Yes, I actually realize/understand this now. I have had the chance to read “A Diary on Information Theory”, where this is also covered, and it became much more obvious. So I obviously made a big mistake in reading that equation. :-) $\endgroup$ – mSSM Sep 2 '17 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.