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