01.2 Entropy

How do we communicate ? We reveal the value of a sequence of variables that we call symbols

Hartley

Information is measured in $\log x$ → because the sum of information is the amount of possibilities

Example

If there are $5$ weather states, then the sum of the information for weather in two places is $\log 5+\log 5=\log 25$ → because there are $25$ possibilities of weather configurations

But something is not quite right about this way to measure this information

Example

Something really unlikely is just “as informative” as a really likely event

Entropy

Quantifies “randomness”

Definition

$H_b(S):=-{\sum }_{S\in \text{supp}(p_S)}{p}_S(s){\log }_b{p}_S(s),\text{supp}(p_S)=\left\{s:p_S(s)>0\right\}$

Which can also be written as $H(S)=\mathbb{E}\left[-\log p_S(S)\right]$ We also have the definition $|\mathcal{A}|=\frac{1}{p_S(s)}⟹H(S)=\mathbb{E}\left[\log |\mathcal{A}|\right]$

Binary Entropy

When $|\mathcal{A}|=2$, we have two possible values $p$ and $(1-p)$ The entropy is given by the binary entropy function : $h(p):=-p{\log }_{2}p-(1-p){\log }_2(1-p)$

Lemma

For a positive real $r$, we have ${\log }_{b}r\le (r-1){\log }_b(e)$ with equality $⟺r=1$

Proof

Since all logarithms are “equal”, we can prove this using the natural log $\ln r\le (r-1),\text{with equality }⟺r=1$

Theorem

The entropy of a discrete random variable $S\in \mathcal{A}$ satisfies $0\le H_b(S)\le {\log }_b|\mathcal{A}|$ with equality on the left$⟺p_S(s)=1$ for a singular $s$, and equality on the right $⟺p_S(s)=\frac{1}{|\mathcal{A}|},\forall s$

Proof

Inequality on the left → $p_S(s)\in \left\{0,1\right\}$ → really rare and weird

Proof

Inequality on the right → We prove that $H_b(S)-\log |\mathcal{A}|\le 0$ $=-{\sum }_{s}p(s)\log p(s)-\log |\mathcal{A}|={\sum }_{s}p(s)\left\{-\log p(s)-\log |\mathcal{A}|\right\}$ $={\sum }_{s}p(s)\left(-\log (p(s)|\mathcal{A}|)\right)={\sum }_{s}p(s)\log \frac{1}{p(s)|\mathcal{A}|}$ $\le {\sum }_{s}p(s)\left[\frac{1}{p(s)|\mathcal{A}|}-1\right]\log e=\left\{{\sum }_s\frac{1}{|\mathcal{A}|}-{\sum }_{s}p(s)\right\}\log e\le 0$

01.3 The fundamental compression theorem