Infor­ma­tion entropy defined as easy as pie!

Let $N$ messages be given, so that the proba­bi­lity of the $i$th message is equal to $p_i$ and the $i$th message occupies a message terri­tory area with the area size $q_i$ and a code of length $-\log_2 q_i$. The average number of bits sent daily with this coding is $ -p_1\cdot \log_2 q_1 -\ldots -p_N\cdot \log_2 q_N. $

For which values of $q_i$ is this sum minimal?

We remind you of the fact $$ p_1 +…+p_N = 1 $$ and a secon­dary condi­tion $$ q_1 +…+q_N = 1. $$ Let’s solve the problem with Lagrange multi­pliers. We do not forget that $p_i$ are constants and $q_i$ are varia­bles. The Lagrange function is $$ \lambda(q_1,\ldots,q_N,\lambda) =-p_1\cdot \log_2 q_1 -…-p_N\cdot \log_2 q_N + \lambda\cdot (q_1+…+q_N). $$ Let’s find the deriva­tives of $\Lambda$ to $q_i$ and set them equal to $0$: $$ -\frac{p_i}{q_i\cdot \ln 2} + \lambda = 0. $$ Reminder, $$ \frac{d}{dx}\log_2x = \frac{d}{dx} \frac{\ln x}{\ln 2} = \frac{1}{x \ln 2}. $$ From this follows $$ p_i = \lambda\cdot q_i\cdot\ln 2. $$ If you sum these equations for all $i$, you get $$ \lambda\cdot\ln 2 = 1. $$ If you insert $\lambda\cdot \ln 2 = 1$ into $p_i = \lambda\cdot q_i\cdot\ln 2$, you get $p_i = q_i$. Optimal coding is there­fore achieved when $q_i = p_i$, which means that the formula for calcu­la­ting the entropy $H$ is as defined: $$ H = -p_1\cdot \log_2 p_1 -…-p_N\cdot \log_2 p_N. $$

Cross entropy

Note that $q_i$ behave like proba­bi­lity varia­bles: they are greater than $0$ and their sum is equal to $1$. The size $$ H(p,q)=-p_1\cdot \log_2 q_1 -…-p_N\cdot \log_2 q_N $$ is called the cross entropy of the two proba­bi­lity distri­bu­tions $(p_i)$ and $(q_i)$, but $q_i$ does not actually have a proba­bi­lity role. The value $H(p,q)$ provides the average bit costs for the trans­mis­sion of messages that are coded accor­ding to ranges $q_i$ but are trans­mitted with proba­bi­li­ties $p_i$.

Kullback-Leibler diver­gence

The diffe­rence between $$ -p_1\cdot \log_2 q_1 -…-p_N\cdot \log_2 q_N $$ and $$ -p_1\cdot \log_2 p_1 -…-p_N\cdot \log_2 p_N $$ is the value of average additional bit costs for message trans­mis­sion due to subop­timal coding. This quantity is referred to as the Kullback-Leibler diver­gence between the distri­bu­tions $(p_i)$ and $(q_i)$.

One remark

For the sake of simpli­city, let us now assume that there are only $2$ weather condi­tions in summer: good weather $G$ and bad weather $S$. Let us also assume the proba­bi­li­ties $P(G)=3/4$, $P(S)=1/4$. Accor­dingly, the infor­ma­tion entropy of the weather is equal to $$ -\frac{3}{4}\cdot \log_2 \frac{3}{4} -\frac{1}{4}\cdot \log_2 \frac{1}{4} \approx 0.8113. $$ For the optimal coding of the event $S$ you need $\log_2 \frac{1}{4}=2$ bits. Every­thing is in the green here. However, for the $G$ you need about $\log_2 \frac{3}{4}\approx 0.415$ bits. This is less than $1$ bit and does not match reality, that by defini­tion only whole symbols $0$ and $1$ are written in the telegrams. There is no other way and we have to encode both events with $1$ bit: $0$ and $1$, just as in the case $P(G)=P(S)=1/2$. So if we want to send a telegram every day, we can’t save money and are forced to, Telegraph $92$ bit for $92$ days. It means the entropy value equals $1$ and seems to contra­dict the theory. However, you can actually save money by sending a single telegram with a weather report for all days, not every day but only at the end of the summer. You can see it in an example with $2$ days. With $P(G)=P(S)=1/2$ the proba­bi­li­ties for all possible 2-day variants are the same $$ P(GG)=P(GS)=P(SG)=P(SS)=1/4. $$ The infor­ma­tion entropy here is $2$ for $2$-day weather events and $1$ for $1$-day weather events. The weather entropy is there­fore $1$. In the case $P(G)=3/4$, $P(S)=1/4$ it is $P(GG)=9/16$, $P(GS)=P(SG)=3/16$, $P(SS)=1/16$. The most optimal coding for the event $GG$ requires appro­xi­m­ately $\log_2 \frac{9}{16} \approx 0.83$ Bit. Similarly for the events $GS$, $SG$, $SS$ you need about $2.415$, $2.415$ and $4$ bits accor­dingly. The most optimal coding looks like this $GG\rightarrow 0$, $GS\rightarrow 10$, $SG\rightarrow 110$, $SS\rightarrow 111$. With this coding, the average report for both days is then only $$ \frac{9}{16}\cdot 1 + \frac{3}{16}\cdot 2 + \frac{3}{16}\cdot 3 + \frac{1}{16}\cdot 3 = 1.6875 \quad (\text{Bit}) $$ and for one day: $$ \frac{1.6875}{2} = 0.84375 \quad (\text{Bit}). $$ The infor­ma­tion entropy of the weather event is equal to $0.84375$. Already cheaper. The longer the sequence of events is coded at once, the more optimal the coding is. If you go to infinity, you approach the theore­tical infor­ma­tion entropy value in praxi.