1.2 Entropy

aicc

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 \frac1{p(s)|\mathcal A|}$$$$\le\sum_s p(s) \left[ \frac1{p(s)|\mathcal A|} - 1 \right] \log e = \left\{ \sum_s \frac1{|\mathcal A|} - \sum_s p(s) \right\} \log e \le 0