Shannon Entropy

Shannon’s entropy is a measure of the uncertainty of a system, or equivalently the amount of information present in it. It is often measured in bits, and, for a system with $n$ possible states, and probabilities described by the Vector $p=[p_1,p_2,...,p_n]$, the entropy is given by $H(p)={\sum }_{i=0}^n-{\log }_2{p}_i$

Desired properties

The entropy $H$ is derived as the only solution that satisfies three properties:

• Continuity: $H$ must be continuous: small changes in the probabilities $p_i$ cause small changes in Entropy.
• Monotonicity: For a Uniform Distribution, $H$ must be increasing with the number of outcomes, i.e. $H(\frac{1}{n+1},\dots ,\frac{1}{n+1})\ge H(\frac{1}{n},\dots ,\frac{1}{n})$.
• Additivity: $H(p_1,\dots ,p_n,q_1,\dots ,q_m)=H(\sum p_i,\sum q_i)+\left(\frac{{\sum }_i{p}_i}{{\sum }_i{p}_i+{\sum }_i{q}_i}\right)H(p_1,...p_n)+\left(\frac{{\sum }_i{q}_i}{{\sum }_i{p}_i+{\sum }_i{q}_i}\right)H(q_1,\dots q_m)$. This property can be visualized as making a composed choice: I can make a choice in two ways both of which should have the same entropy. These ways are:
  • Picking one of the $p_i$ or $q_i$ outcomes, with entropy $H(p_1,\dots ,p_n,q_1,\dots ,q_m)$.
  • Picking either a $p$ or $q$ outcome, with entropy $H(\sum p_i,\sum q_i)$, and then, with probability $\frac{{\sum }_i{p}_i}{{\sum }_i{p}_i+{\sum }_i{q}_i}$, if I picked $p$, I pick one of the $p_i$, with entropy $H(p_1,\dots ,p_n)$, and similarly for $q_i$, which has a total entropy of $H(\sum p_i,\sum q_i)+\left(\frac{{\sum }_i{p}_i}{{\sum }_i{p}_i+{\sum }_i{q}_i}\right)H(p_1,...p_n)+\left(\frac{{\sum }_i{q}_i}{{\sum }_i{p}_i+{\sum }_i{q}_i}\right)H(q_1,\dots q_m)$.

Formula derivation

We define $H_n:=H(\frac{1}{n},\dots ,\frac{1}{n})$. By additivity, we have

$$\begin{array}{rl}{H}_{n^k}& =H(\frac{1}{n^k},\dots ,\frac{1}{n^k})\\ & =H(\frac{1}{n},\dots ,\frac{1}{n})+n(\frac{1}{n})H(\frac{1}{n^{k-1}},\dots ,\frac{1}{n^{k-1}})\\ & =H_n+H_{n^{k-1}}\\ & =\dots \text{ ( Induction )}\\ & =k{H}_n\end{array}$$

Now we fix an $m$, and describe $H_m$ as a function of $H_2$. For any given $l\in {\mathbb{Z}}^{+}$, we can find a $k\in {\mathbb{Z}}^{+}$ such that

$$\begin{array}{cccccl}{2}^k& \le & m^l& \le & 2^{k+1}& \text{By monotonicity}\\ H_{2^k}& \le & H_{m^l}& \le & H_{2^{k+1}}& \text{Since }{H}_{n^k}=k{H}_n\\ k{H}_2& \le & l{H}_m& \le & (k+1)H_2& \\ \frac{k}{l}{H}_2& \le & H_m& \le & \frac{k+1}{l}{H}_2& l\in [k{\log }_{m}2,(k+1){\log }_m(2)]\\ \frac{k}{(k+1){\log }_m(2)}{H}_2& \le & H_m& \le & \frac{k+1}{k{\log }_m(2)}{H}_2& \frac{1}{{\log }_m(2)}={\log }_2(m)\\ \frac{k}{(k+1)}{\log }_2(m)H_2& \le & H_m& \le & \frac{k+1}{k}{\log }_2(m)H_2& k\to \infty \\ {\log }_2(m)H_2& \le & H_m& \le & {\log }_2(m)H_2& \end{array}$$

Hence $H_m={\log }_2(m)H_2$ holds $\forall m\in {\mathbb{Z}}^{+}$. Letting $p_1,p_2,\dots ,p_n\in {\mathbb{Q}}^{+}$, we can take their lowest common denominator $n\in {\mathbb{Z}}^{+}$ and write $p_i=\frac{n_i}{n},n_i\in {\mathbb{Z}}^{+}$. By additivity, $H_n=H(p_1,p_2,\dots ,p_n)+{\sum }_i{p}_i{H}_{p_i}$, which can be rearranged to get

$$\begin{array}{rlc}H(p_1,\dots ,p_n)& =H_n-{\sum }_i{p}_i{H}_{n_i}& \\ & =H_n-{\sum }_i\frac{n_i}{n}{H}_{n_i}& {\sum }_i\frac{n_i}{n}=1\\ & ={\sum }_i\frac{n_i}{n}{H}_n-{\sum }_i\frac{n_i}{n}{H}_{n_i}& H_m={\log }_2(m)H_2\\ & ={\sum }_i\frac{n_i}{n}{\log }_2(n)H_2-{\sum }_i\frac{n_i}{n}{\log }_2(n_i)H_2& \\ & ={\sum }_i\frac{n_i}{n}({\log }_2(n)-{\log }_2(n_i))H_2& \\ & ={\sum }_i\frac{n_i}{n}{\log }_2(\frac{n}{n_i})H_2& \\ & ={\sum }_i{p}_i{\log }_2(p_i^{-1})H_2& \\ & =-{\sum }_i{p}_i{\log }_2(p_i)H_2& \text{Absorbing }{H}_2>0\text{ into }b>1\\ & =-{\sum }_i{p}_i{\log }_b(p_i)& \end{array}$$

By continuity, we have that $H(p_1,p_2,\dots p_n)=-{\sum }_i{p}_i{\log }_b(p_i)$ holds $\forall p_i\in {\mathbb{R}}^{+}$ such that ${\sum }_i{p}_i=1$. The constant $b>1$ defines the information units we work in:

• $b=2$ is bits
• $b=3$ is trits
• $b=e$ is nats
• $b=10$ is harleys
• $\dots$