Shannon entropy

Idea: Bits per message

A feed sends updates, trades, cancels and halts with chances $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$.

• A fixed code needs $2$ bits for each
• Code words $0$, $10$, $110$, $111$: short for common
• No word starts another, so no separators are needed

Example: The average code length

With code words $0$, $10$, $110$, $111$ for chances $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$, what is the average length in bits?

1. Lengths $1$, $2$, $3$, $3$
2. $\frac{1}{2}+\frac{2}{4}+\frac{3}{8}+\frac{3}{8}=\frac{7}{4}$ bits

Formula: Entropy

$H(X)=-\sum p(x){\log }_{2}p(x)$

The average surprise −log₂ p, in bits: the floor for any lossless code.

Idea: Surprise

Each code length above is $-{\log }_{2}p$: chance $\frac{1}{8}$ took $3$ bits.

• Rare outcomes surprise more
• A certain outcome carries no surprise
• $H$ counts good yes or no questions on average

Formula: Independent sources add

$H(X,Y)=H(X)+H(Y)\text{for}\text{independent}X,Y$

Chances of independent events multiply, and logs turn products into sums.

Idea: Both ends of the scale

On $n$ values, $0\le H\le {\log }_{2}n$ for every distribution.

• $H=0$ when one value is certain
• $H={\log }_{2}n$ when all are equally likely
• $8$ equal sectors: ${\log }_{2}8=3$ bits

Quick check: Kind and venue

Each message also comes from venue A, B or C with chances $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{4}$, independent of its kind. What is the entropy of the pair?

Common mistake: Entropy is not variance

Payoffs $1$, $2$, $3$ and $1$, $100$, $10000$ with the same chances have the same entropy.

Instead $H$ asks which outcome comes; variance asks how far apart the outcomes lie.

Idea: Say it in an interview

Entropy is the average bits an optimal code needs: uncertainty about the outcome.

• Show it on chances that are powers of $\frac{1}{2}$
• Then every logarithm is a whole number