I am studying Cover & Thomas's Elements of Information Thoery, and I am confused about the proof of the following theorem (I'll state the theorem first, then write out their proof, then point out the part that's unclear to me):

Theorem (5.3.1): The expected Length $L$ of any instantaneous $D$-ary code for a random variable $X$ is greater than or equal to the entropy $H_D(X)$; that is, $$L(C) \geq H_D(X)$$ with equality if and only if $D^{-l_i} = p_i$.

Proof: $$ L - H_D(X) = \sum p_i l_i - \sum p_i \log_D \frac{1}{p_i} $$ Using the fact that the optimal codeword length is $l_i^* = \log_D(p_i) = \log_D(D^{-l_i})$: $$ = - \sum p_i \log_D{D^{-l_i}} + \sum p_i \log_D p_i $$ Letting $r_i = D^{-l_i}/\sum_j D^{-l_j}$ and $c = \sum D^{-l_i}$: $$ = \sum p_i \log_D \frac{p_i}{r_i} - \log_D c \\ = D(\mathbf{p}||\mathbf{r}) + \log_D \frac{1}{c} \\ \geq 0 $$ Hence, $L(C) \geq H_D(X)$ with equality if and only if $p_i = D^{-l_i}$

My question: I am confused how they move from line 2 to line 3 in the proof. That is, I am unsure how letting $r_i = D^{-l_i}/\sum_j D^{-l_j}$ and $c = \sum D^{-l_i}$ produces $L - H = \sum p_i \log_D \frac{p_i}{r_i} - \log_D c$ from the preceding line. I think this is just a susbsition and algebra step, but I'd like to be able to understand the details of this step, which I am not seeing currently.

Thank you for your help!

  • 1
    $\begingroup$ Simply replace $D^{-l_i}$ in line 2 with $r_i/c$ and use elementary properties of the logarithm $\endgroup$ – Stelios Mar 5 '17 at 9:00
  • 1
    $\begingroup$ Apologies for the typo, $r_i/c$ in the above comment should be $r_i c$ $\endgroup$ – Stelios Mar 6 '17 at 17:56

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.