Information Theory · Study tools

InteractiveApplebaum, Ch. 6: Information and entropy

Information and entropy

A rare event is more informative than a common one. Entropy is the average information in the outcome of a random variable: how many yes/no questions, on average, it takes to pin down the outcome. Drag the bars below and find the shapes with the most and the least entropy.

The idea

Information. The information in an event of probability

p

is

I=-\log p

bits. Two independent events carry the sum of their informations, because probabilities multiply and logarithms turn products into sums.

Entropy. For

X

with law

p_1,\dots,p_n

,

H(X)=E\big(I(X)\big)=-\sum_{j=1}^n p_j\log p_j, \qquad\text{with } 0\log 0=0.

It depends only on the probabilities, not on the values $X$ takes. For a Bernoulli variable, $H_b(p)=-p\log p-(1-p)\log(1-p)$ , which is 1 bit at $p=\frac12$ .

Bounds.

0\le H(X)\le\log n

. The lower bound holds exactly when one outcome is certain, the upper exactly when

X

is uniform.

Maximum entropy principle. Among all laws on values

x_1,\dots,x_n

with a given mean, the one of largest entropy is the Gibbs law

p_j=\frac{e^{-\beta x_j}}{Z(\beta)}, \qquad Z(\beta)=\sum_j e^{-\beta x_j},

with $\beta$ chosen to give the right mean. It is the "least committal" law consistent with what you know. In statistical mechanics the $x_j$ are energies and this is the Boltzmann distribution.

Explore

Drag the bars (outcomes

j=1,\dots,6

) up and down; the heights are rescaled to sum to 1. Above each bar is the information

-\log p_j

of that outcome, in bits. The dashed outline is the maximum-entropy law with the same mean as yours.

Worked example

Three fair coins are tossed. Let $X$ be the number of heads.

Write down the law of $X$ .

$P(X=0)=P(X=3)=\frac18$ and $P(X=1)=P(X=2)=\frac38$ .
How much information is there in learning $X=0$ ? In learning $X=1$ ?

$-\log\frac18=3$ bits, and $-\log\frac38=\log\frac83\approx1.415$ bits.
Compute $H(X)$ .

$H(X)=2\cdot\tfrac18\cdot3+2\cdot\tfrac38\cdot1.415\approx0.75+1.061=1.811\ \text{bits}.$
The full outcome (e.g. HTH) has 3 bits of entropy. Where did the other 1.19 bits go?

The full outcome is uniform on 8 sequences, so it has $\log8=3$ bits. $X$ is a function of it and forgets the order of the heads, which is why $H(X)<3$ . In general $H(f(Y))\le H(Y)$ : processing can only lose information. The missing $3-1.811=1.189$ bits is the average information in "which order", given the count.

Check your understanding

Which law on four outcomes has more entropy: $(0.5,0.5,0,0)$ or $(0.4,0.2,0.2,0.2)$ ?

The first, because it is uniform.It is uniform only on two of the four outcomes, which gives $\log2=1$ bit.
The second
They are equal.Compute both: one is exactly 1 bit.

H(0.5,0.5,0,0)=1

bit, while

H(0.4,0.2,0.2,0.2)=0.4\log2.5+0.6\log5\approx1.922

bits. Spreading probability over more outcomes matters more than being exactly uniform.

$X$ takes values $1,\dots,6$ . Let $Y=10X+7$ . How does $H(Y)$ compare with $H(X)$ ?

$H(Y)=H(X)$
$H(Y)=10\,H(X)$ That is how the variance would scale (by $10^2$ , in fact). Entropy only sees the probabilities.
$H(Y)>H(X)$ , since $Y$ is more spread out.Entropy does not measure spread of values; relabelling the outcomes changes nothing.

x\mapsto10x+7

is one-to-one, so

Y

has the same list of probabilities as

X

and the same entropy. Entropy measures uncertainty about which outcome occurs, not how far apart the outcomes are.

Among all laws on $\{1,\dots,6\}$ with mean 3.5, which has the largest entropy?

The uniform law
$p_3=p_4=\frac12$ It has mean 3.5 but only 1 bit of entropy. Try it in the explorer.
A Gibbs law with $\beta>0$ With $\beta>0$ the weights $e^{-\beta j}$ favour small values, so the mean is below 3.5.

The uniform law has the largest entropy of all,

\log6\approx2.585

bits, and its mean is 3.5. It is the Gibbs law with

\beta=0

. Press "Uniform", then "Replace with the max-entropy law": nothing changes.

Practice

The Bernoulli entropyA calculus check

Show that $H_b(p)$ has its maximum at $p=\frac12$ and is symmetric about it. Compute $H_b(0.1)$ .

Solution

$H_b(p)=H_b(1-p)$ by its formula. In natural logs, $\frac{d}{dp}\big(-p\ln p-(1-p)\ln(1-p)\big)=\ln\frac{1-p}{p}$ , which is positive for $p<\frac12$ , zero at $\frac12$ and negative after. So the maximum is $H_b(\frac12)=1$ bit. $H_b(0.1)=0.1\log10+0.9\log\frac{10}9\approx0.332+0.137=0.469$ bits.

Why uniform is the maximumThe Gibbs inequality

Using $\ln x\le x-1$ (equality only at $x=1$ ), show that $H(X)\le\log n$ , with equality only for the uniform law.

Hint

Look at $H(X)-\log n=\sum_j p_j\log\frac{1}{np_j}$ , summing over the $j$ with $p_j>0$ .

Solution

In natural logs, $\sum_j p_j\ln\frac1{np_j}\le\sum_j p_j\big(\frac1{np_j}-1\big)=\sum_{p_j>0}\frac1n-1\le0$ . Equality needs $np_j=1$ for every $j$ with $p_j>0$ , and needs every $j$ to have $p_j>0$ ; that is the uniform law. Dividing by $\ln2$ converts to bits.

From Applebaum, Probability and Information: An Integrated Approach (2nd ed., Cambridge, 2008)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 6.5Two entropies

Find the entropy of (a) the number of heads in two tosses of a fair coin; (b) a Poisson variable with mean $0.5$ .

Hint

(b) has infinitely many terms, but they shrink fast; sum the first several.

Solution

(a) The distribution is $(\tfrac14,\tfrac12,\tfrac14)$ , so $H=\tfrac14\cdot2+\tfrac12\cdot1+\tfrac14\cdot2=1.5$ bits.

(b) $p_k=e^{-0.5}0.5^k/k!$ : $0.607,0.303,0.076,0.013,0.0016,\dots$ . Summing $-p_k\log_2p_k$ gives $H\approx1.34$ bits (the terms beyond $k=5$ contribute less than $0.001$ ).

Exercise 6.6The binary entropy function

For $H_b(p)=-p\log p-(1-p)\log(1-p)$ : (a) show $H_b(0)=H_b(1)=0$ ; (b) show $H_b(\tfrac12-q)=H_b(\tfrac12+q)$ ; (c) show the maximum is at $p=\tfrac12$ and sketch the graph.

Hint

Use the convention $0\log0=0$ (the limit of $x\log x$ ). For (c), differentiate.

Solution

(a) Both terms vanish at $p=0$ and $p=1$ , using $x\log x\to0$ .

(b) Replacing $p$ by $1-p$ swaps the two terms, and $1-(\tfrac12-q)=\tfrac12+q$ .

(c) $H_b'(p)=\log\frac{1-p}p$ , which is positive for $p<\tfrac12$ , zero at $\tfrac12$ , negative after. So $H_b$ rises from $0$ to its maximum $H_b(\tfrac12)=1$ bit and falls back symmetrically; it is concave ( $H_b''<0$ ) with vertical tangents at the ends.

Exercise 6.13Maximum entropy with a mean constraint

Three states have energies 1, 2 and 3 J and the mean energy is 2.4 J. (a) Find the maximum-entropy distribution. (b) Find the corresponding temperature and comment.

Hint

The maximiser is a Gibbs distribution $p_i\propto e^{-\beta E_i}$ ; choose $\beta$ to match the mean. Temperature is $T=1/(k\beta)$ .

Solution

(a) $p_i=e^{-\beta E_i}/Z$ . With $u=e^{-\beta}$ , the mean condition $\frac{u+2u^2+3u^3}{u+u^2+u^3}=2.4$ becomes $1+2u+3u^2=2.4(1+u+u^2)$ , i.e. $3u^2-2u-7=0$ , so $u=\tfrac{1+\sqrt{22}}3\approx1.897$ and $\beta=-\ln u\approx-0.640\ \mathrm{J^{-1}}$ . Then $p\approx(0.154,\ 0.292,\ 0.554)$ .

(b) $T=1/(k_B\beta)\approx-1.1\times10^{23}$ K. The temperature is negative: the mean energy is above the uniform-distribution value $2$ , so higher energies must be more likely, which a Gibbs distribution can only do with $\beta<0$ . Negative temperatures do occur in systems with bounded energy (population inversion in lasers); the huge magnitude is because the energies are joules rather than atomic scales.

Exercise 6.16Evening out a distribution raises entropy

Replace two probabilities $p_1<p_2$ by $p_1+\varepsilon$ and $p_2-\varepsilon$ , where $0<2\varepsilon<p_2-p_1$ . Prove the entropy increases.

Hint

Only two terms change. Differentiate in $\varepsilon$ .

Solution

Let $f(t)=-(p_1+t)\log(p_1+t)-(p_2-t)\log(p_2-t)$ . Then $f'(t)=\log\frac{p_2-t}{p_1+t}$ , which is positive as long as $p_1+t<p_2-t$ , i.e. $2t<p_2-p_1$ . So $f$ is strictly increasing on $[0,\varepsilon]$ and $f(\varepsilon)>f(0)$ . The other terms of the entropy are unchanged.

InteractiveApplebaum, Ch. 6: Information and entropy (§6.3)

Joint entropy and mutual information

How much does knowing $X$ tell you about $Y$ ? Mutual information answers in bits: it is the drop in uncertainty about $Y$ once $X$ is known. Reshape a joint law by dragging the dividers of the mosaic below and watch the entropies add up.

The idea

Joint and conditional entropy. For a pair

(X,Y)

with joint law

p_{jk}=P(X=x_j,Y=y_k)

,

H(X,Y)=-\sum_{j,k}p_{jk}\log p_{jk}, \qquad H(Y\mid X)=\sum_j P(X=x_j)\,H(Y\mid X=x_j).

$H(Y\mid X=x_j)$ is the entropy of the conditional law of $Y$ given $X=x_j$ , and $H(Y\mid X)$ is its average over $x_j$ . (The book writes $H_X(Y)$ .)

Chain rule.

H(X,Y)=H(X)+H(Y\mid X)

: learning the pair is learning

X

, then learning

Y

given

X

.

Mutual information.

I(X;Y)=H(Y)-H(Y\mid X)=H(X)+H(Y)-H(X,Y)=\sum_{j,k}p_{jk}\log\frac{p_{jk}}{P(X=x_j)P(Y=y_k)}.

Properties.

I(X;Y)=I(Y;X)\ge0

, with equality exactly when

X

and

Y

are independent. Equivalently

H(Y\mid X)\le H(Y)

: on average, conditioning cannot increase uncertainty.

Explore

Start from:

Each rectangle's area is

p_{jk}

. Drag the vertical divider to set

P(X=0)

, and each horizontal divider to set

P(Y=0\mid X=x)

.

H(X\mid Y)

I(X;Y)

H(Y\mid X)

, in bits

Worked example

$X$ and $Y$ take values 0 and 1 with joint law $p_{00}=\frac12$ , $p_{01}=\frac14$ , $p_{10}=0$ , $p_{11}=\frac14$ .

Find the marginal laws and their entropies.

$P(X=0)=\frac34$ , $P(X=1)=\frac14$ , so $H(X)=H_b(\frac14)\approx0.811$ . $P(Y=0)=P(Y=1)=\frac12$ , so $H(Y)=1$ .
Find $H(X,Y)$ .

$H(X,Y)=\frac12\log2+\frac14\log4+\frac14\log4=0.5+0.5+0.5=1.5$ bits.
Compute $H(Y\mid X)$ from its definition, and check the chain rule.

Given $X=0$ , $Y$ is 0 or 1 with probabilities $\frac23,\frac13$ , so $H(Y\mid X=0)=H_b(\frac13)\approx0.918$ . Given $X=1$ , $Y=1$ for certain, so $H(Y\mid X=1)=0$ . Then $H(Y\mid X)=\frac34\cdot0.918\approx0.689$ , and indeed $H(X)+H(Y\mid X)\approx0.811+0.689=1.5$ .
Find $I(X;Y)$ two ways.

$H(Y)-H(Y\mid X)\approx1-0.689=0.311$ , and $H(X)+H(Y)-H(X,Y)\approx0.811+1-1.5=0.311$ bits. Set the mosaic to these numbers ( $P(X=0)=0.75$ , $P(Y=0\mid X=0)=\frac23$ , $P(Y=0\mid X=1)=0$ ) to check.

Check your understanding

$I(X;Y)=0$ . What can you conclude?

$X$ and $Y$ are independent.
$Y$ is a function of $X$ .Then $H(Y\mid X)=0$ and $I(X;Y)=H(Y)$ , the largest it can be.
One of them is constant.That is enough for $I=0$ but not necessary. In the mosaic, line the two horizontal dividers up.

I(X;Y)=\sum p_{jk}\log\frac{p_{jk}}{p_jq_k}

is zero exactly when

p_{jk}=p_jq_k

for every

j,k

. In the mosaic, that means the two horizontal dividers are at the same height: the conditional law of

Y

doesn't depend on

X

.

$X$ is a fair bit and $Y=X$ . What is $I(X;Y)$ ?

0 $Y$ tells you $X$ exactly. That is the opposite of independence.
1 bit
2 bitsThat is $H(X)+H(Y)$ . But $H(X,Y)=1$ , not 0, so subtract it.

H(Y\mid X)=0

, so

I=H(Y)=1

bit. A variable shares all of its information with itself:

I(X;X)=H(X)

.

Which of these always holds?

$H(Y\mid X)\le H(Y)$
$H(Y\mid X=x)\le H(Y)$ for every value $x$ Try "Y depends on X only sometimes": a rare value of $X$ after which $Y$ is a fair coin.
$H(X,Y)\ge H(X)+H(Y)$ The inequality goes the other way: $H(X,Y)=H(X)+H(Y)-I(X;Y)$ .

Only the average over

x

is guaranteed to drop. If

X=0

with probability 0.9 and then

Y=0

, but

X=1

makes

Y

a fair coin, then

H(Y)=H_b(0.05)\approx0.286

while

H(Y\mid X=1)=1

. Learning a particular, surprising value can make you less sure.

Practice

Two formulas for IExpanding the logarithm

Show that $\displaystyle\sum_{j,k}p_{jk}\log\frac{p_{jk}}{p_jq_k}=H(X)+H(Y)-H(X,Y)$ , where $p_j$ , $q_k$ are the marginals.

Solution

Split the logarithm: $\sum p_{jk}\log p_{jk}-\sum p_{jk}\log p_j-\sum p_{jk}\log q_k$ . The first sum is $-H(X,Y)$ . In the second, summing over $k$ first gives $\sum_j p_j\log p_j=-H(X)$ ; similarly the third is $-H(Y)$ . So the total is $-H(X,Y)+H(X)+H(Y)$ .

The last bitA function of a random variable

$X$ is uniform on $\{0,1,2,3\}$ and $Y=X\bmod2$ . Find $H(X)$ , $H(Y)$ , $H(Y\mid X)$ , $H(X\mid Y)$ and $I(X;Y)$ .

Solution

$H(X)=2$ , $H(Y)=1$ . $Y$ is determined by $X$ , so $H(Y\mid X)=0$ . Given $Y$ , $X$ is uniform on two values, so $H(X\mid Y)=1$ . Then $I(X;Y)=H(Y)-H(Y\mid X)=1$ bit, and the chain rule checks: $H(X,Y)=H(X)=2=H(Y)+H(X\mid Y)$ .

From Applebaum, Probability and Information: An Integrated Approach (2nd ed., Cambridge, 2008)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 6.8Entropies of a pair of bits

$X$ is Bernoulli with $P(X=1)=\tfrac13$ , and $P(Y=0\mid X=0)=\tfrac14$ , $P(Y=1\mid X=1)=\tfrac35$ . Compute $H(X,Y)$ , $H_X(Y)$ , $H(Y)$ , $H_Y(X)$ and $I(X,Y)$ .

Hint

Build the joint table first, then everything follows from $H(X,Y)=H(X)+H_X(Y)=H(Y)+H_Y(X)$ .

Solution

Joint probabilities: $P(0,0)=\tfrac23\cdot\tfrac14=\tfrac16$ , $P(0,1)=\tfrac12$ , $P(1,0)=\tfrac13\cdot\tfrac25=\tfrac2{15}$ , $P(1,1)=\tfrac15$ . So $P(Y=0)=0.3$ , $P(Y=1)=0.7$ . In bits:

(a) $H(X,Y)\approx1.783$ . With $H(X)=H_b(\tfrac13)\approx0.918$ : (b) $H_X(Y)=H(X,Y)-H(X)\approx0.865$ . (c) $H(Y)=H_b(0.3)\approx0.881$ . (d) $H_Y(X)=H(X,Y)-H(Y)\approx0.902$ . (e) $I(X,Y)=H(Y)-H_X(Y)\approx0.017$ .

Exercise 6.10Conditioning can only reduce entropy

Using Gibbs' inequality, show $H_X(Y)\le H(Y)$ , with equality iff $X,Y$ are independent. Deduce $I(X,Y)\ge0$ .

Hint

Write $H(Y)-H_X(Y)$ as one sum over the joint distribution.

Solution

H(Y)-H_X(Y)=\sum_{x,y}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}.

Gibbs' inequality $-\sum p_i\log p_i\le-\sum p_i\log q_i$ for probability vectors $p,q$ , applied with $p=p(x,y)$ and $q=p(x)p(y)$ , shows this is $\ge0$ , with equality iff $p(x,y)=p(x)p(y)$ for all $x,y$ : independence. Since $I(X,Y)=H(Y)-H_X(Y)$ , $I\ge0$ with the same equality case.

InteractiveApplebaum, Ch. 6: Information and entropy (§§6.4–6.5)

The maximum entropy principle

With no information about a die, you assume every face is equally likely. Now suppose you are told only that its average roll is 4.5. Which probabilities should you assume? Pick the ones with the most entropy: the least committal law that still agrees with what you know.

The idea

The uniform law has the largest entropy among all laws on $n$ outcomes, $H=\log n$ . So the old principle of symmetry (“with no reason to prefer an outcome, treat them equally”) can be restated as: choose the law of maximum entropy. The restatement is more powerful, because it still makes sense when you do have partial information.

Principle of maximum entropy (Applebaum §6.4.1). Given a random variable

X

with unknown law

p_1,\dots,p_n

, choose the

p_j

to maximize the entropy

H(X)

subject to any known constraints.

Knowing only the mean. Let $X$ take values $x_1,\dots,x_n$ with $\mathbb E(X)=E$ known. Maximize $H=-\sum_jp_j\log p_j$ subject to $\sum_jp_j=1$ and $\sum_jx_jp_j=E$ . With Lagrange multipliers $\lambda,\mu$ ,

L=-\sum_jp_j\log p_j+\lambda\Big(\sum_jp_j-1\Big)+\mu\Big(\sum_jx_jp_j-E\Big),\qquad \frac{\partial L}{\partial p_j}=0\ \Rightarrow\ p_j=e^{\lambda'+\mu'x_j}.

Gibbs distribution. Normalizing removes

\lambda'

:

p_j=\frac{e^{\mu'x_j}}{Z(\mu')},\qquad Z(\mu')=\sum_{k=1}^ne^{\mu'x_k}\quad\text{(the partition function)},

and

\mu'

is the one number that makes the mean come out to

E

. For

\mu'=0

it is the uniform law;

\mu'>0

tilts the weight toward large values,

\mu'<0

toward small ones, each probability a constant ratio

e^{\mu'}

times the one before.

Physics. If the $x_j$ are the energies of the particles in a gas and the average energy is fixed, the same calculation gives Boltzmann's law, with $\mu'=-\beta=-1/kT$ (Applebaum §6.5): the maximum-entropy law at a given temperature.

Explore

Known mean E

The maximum-entropy law with mean

E

: a Gibbs distribution

p_j\propto e^{\mu'j}

.

Your guess: drag the bars (they are rescaled to add to 1). Try to match the mean and beat the entropy on the left.

Worked example

Jaynes's dice problem (the “Brandeis dice”): a die has average roll 4.5. Find the maximum-entropy law.

Write down the form of the answer.

$p_j=r^j/Z$ for $j=1,\dots,6$ , with $r=e^{\mu'}$ and $Z=r+r^2+\dots+r^6$ : a geometric progression.
Which equation determines $r$ ? Is $r$ above or below 1?

$\sum_jj\,r^j=4.5\sum_jr^j$ . The mean 4.5 is above the fair value 3.5, so the weights must increase: $r>1$ . Solving numerically gives $r\approx1.449$ ( $\mu'\approx0.371$ ).
Give the law and its entropy, and compare with another law of mean 4.5.

$p\approx(0.054,\,0.079,\,0.114,\,0.165,\,0.240,\,0.348)$ , with $H\approx2.33$ bits (the fair die has $\log6\approx2.58$ ). The law “4 or 5, each with probability $\tfrac12$ ” also has mean 4.5, but only 1 bit of entropy: it claims to know much more than we were told.

Check your understanding

You know only that a die's mean is 3.5. The maximum-entropy law is:

Uniform: 3.5 is the fair die's mean, so the constraint adds nothing, and $\mu'=0$ .
Half the mass on 3 and half on 4.Mean 3.5, but only 1 bit of entropy: it assumes far more than you know.

When the constraint is already satisfied by the uniform law, maximum entropy gives back the symmetry principle.

In a Gibbs law on $1,\dots,6$ , the ratio $p_{j+1}/p_j$ is:

The same for every $j$ , namely $e^{\mu'}$ .
Proportional to $j$ . $p_j\propto e^{\mu'x_j}$ with equally spaced $x_j$ gives a geometric progression.

p_{j+1}/p_j=e^{\mu'(x_{j+1}-x_j)}

, constant when the values are equally spaced, as on a die.

Why is the maximum-entropy law a sensible default, rather than any other law with the right mean?

Any other law with the same mean has less entropy, so it encodes information you were not given.
It is the law the die actually has.Nothing guarantees that. It is the best guess given what you know, not the truth.

Maximum entropy is a rule for honest guessing. New information (say, the variance too) adds a constraint and changes the answer.

Practice

Two outcomesThe smallest case

$X$ takes values 0 and 1, and $\mathbb E(X)=E$ . What does the maximum-entropy principle give, and why is there nothing to maximize?

Solution

$p_1=E$ , $p_0=1-E$ : the two constraints already determine the law. The Gibbs form agrees: $p_1/p_0=e^{\mu'}$ with $e^{\mu'}=E/(1-E)$ .

The constraint at workLagrange in full

Using natural logarithms, solve $\partial L/\partial p_j=0$ for $L=-\sum p_j\ln p_j+\lambda(\sum p_j-1)+\mu(\sum x_jp_j-E)$ , and show that $\lambda$ is fixed by normalization.

Solution

$-\ln p_j-1+\lambda+\mu x_j=0$ , so $p_j=e^{\lambda-1}e^{\mu x_j}$ . Summing to 1 gives $e^{\lambda-1}=1/Z(\mu)$ . (Base-2 logarithms only rescale $\lambda$ and $\mu$ , as in Applebaum's $\lambda',\mu'$ .) The second-derivative matrix is $-\mathrm{diag}(1/p_j)$ , negative definite, so this critical point is the maximum.

InteractiveBuilds on Applebaum §6.4; Goodfellow–Bengio–Courville §6.2.2.3

Why e to the score: softmax

Classifiers, attention in language models, Boltzmann exploration in reinforcement learning and the Exp3 algorithm for adversarial bandits all turn real-valued scores into probabilities the same way: exponentiate, then normalize. Scores can be negative, so some positive transformation is needed, but why the exponential? Because the result is the maximum-entropy distribution of the previous module. The base $e$ itself turns out to be a choice of units.

The idea

Softmax. Scores

s_1,\dots,s_n\in\R

and a temperature

\tau>0

give the probabilities

p_i=\frac{e^{s_i/\tau}}{Z},\qquad Z=\sum_{j=1}^ne^{s_j/\tau}.

This is the Gibbs distribution of the maximum entropy module with the score playing the role of

x_j

and

\mu'=1/\tau

.

Softmax is the best trade-off between score and uncertainty (the Gibbs variational principle). Among all probability vectors

p

, softmax maximizes

F(p)=\underbrace{\sum_ip_is_i}_{\text{expected score}}+\tau\,\underbrace{\Big(-\sum_ip_i\ln p_i\Big)}_{\text{entropy }H(p)\text{, in nats}},

and the maximum value is

\tau\ln Z=\tau\ln\sum_je^{s_j/\tau}

, the “log-sum-exp”, a smooth version of

\max_js_j

.

Proof in one line. Write $q$ for softmax, so $s_i=\tau\ln q_i+\tau\ln Z$ . Substitute:

F(p)=\tau\ln Z+\tau\sum_ip_i\ln q_i-\tau\sum_ip_i\ln p_i=\tau\ln Z-\tau\,D(p\,\|\,q),

where

D(p\|q)=\sum_ip_i\ln\frac{p_i}{q_i}\ge0

is the Kullback–Leibler divergence, zero only for

p=q

(Gibbs' inequality). So every other distribution falls short of softmax by exactly

\tau

times its divergence from it.

What that means. Putting all the probability on the highest score maximizes the expected score but commits completely. The uniform law hedges completely but ignores the scores. Softmax is the law that is as uncertain as possible for the expected score it achieves; the temperature sets the exchange rate. As $\tau\to0$ it becomes the argmax; as $\tau\to\infty$ , the uniform law.

Why $e$ , and not 2 or 10?

b^{s}=e^{s\ln b}

, so “base-

b

softmax” is ordinary softmax at temperature

1/\ln b

: for base 2,

\tau\approx1.44

. Every base gives the same family of distributions. Choosing

e

means measuring entropy in nats, and then the temperature is literally the weight on entropy and the derivatives come out clean:

\partial\ln p_i/\partial s_j=(\delta_{ij}-p_j)/\tau

, so the gradient of the cross-entropy loss

-\ln p_y

with respect to the scores is

p-e_y

, predicted minus true. Base 2 would only put a factor

\ln2

everywhere.

Why an exponential at all: only it ignores a common shift. Scores usually mean something only relative to each other, so adding the same constant

c

to every score should not change the distribution. If

f

is continuous and positive and

f(s_i+c)/\sum_jf(s_j+c)=f(s_i)/\sum_jf(s_j)

for all scores and all

c

, then

f(x)=Ab^x

for constants

A>0

,

b>0

: an exponential. Squaring the scores, or clipping the negative ones to zero (a ReLU) and dividing by the total, fails this test (try it in the figure). Note what the theorem does not say: it allows any base

b

.

Where it shows up. The final layer of a classifier (multinomial logistic regression). Attention, $\mathrm{softmax}(QK^\top/\sqrt d)$ , where dividing by $\sqrt d$ is a temperature: the dot product of two $d$ -dimensional vectors with independent unit-variance entries has variance $d$ , and the scaling keeps the scores at variance about 1 so the softmax is neither nearly one-hot nor nearly uniform. Boltzmann (softmax) exploration in reinforcement learning. And Hedge/Exp3 for adversarial bandits, which put weight $e^{\eta S_a}$ on arm $a$ with $S_a$ its total reward so far: by the theorem above, that is the law maximizing $\eta\langle p,S\rangle+H(p)$ , an entropy-regularized “follow the leader” that never commits completely.

The same formula in economics. In discrete-choice models, a person picks option $m$ with value $V_m$ , and the multinomial logit $p_m=e^{V_m}/\sum_{m'}e^{V_{m'}}$ is the standard model of their choice probabilities. It is the theorem above with $\tau=1$ : logit maximizes $\sum_mV_mp_m+H(p)$ over the simplex, a concave objective, so a convex program with a unique solution. The entropy term has two readings: a value placed on variety (not committing to one option), or, in rational-inattention models, the cost of the information needed to tell the options apart (see M. Fosgerau, E. Melo, A. de Palma and M. Shum, “Discrete choice and rational inattention: a general equivalence result”, International Economic Review, 2020). A third route reaches the same formula without entropy: McFadden's random utility model, in the last practice problem below.

Explore

Temperature τ Add c to every score

Turn scores into probabilities by

Four scores; drag the bars (they can be negative). The shift

c

moves all of them together.

the probabilities from the chosen map; dashed: softmax at the same

\tau

.

Worked example

Scores $s=(2,1,0)$ , temperature $\tau=1$ .

Compute the softmax probabilities.

$e^2\approx7.389$ , $e^1\approx2.718$ , $e^0=1$ , so $Z\approx11.107$ and $p\approx(0.665,\,0.245,\,0.090)$ . Each step down in score divides the probability by $e$ .
Check that $F(p)=\ln Z$ .

Expected score $2(0.665)+1(0.245)\approx1.575$ ; entropy $-\sum p_i\ln p_i\approx0.832$ nats; total $\approx2.408$ , and $\ln11.107\approx2.408$ .
Compare two other laws: all mass on the top score, and uniform.

One-hot: $F=2+0=2$ . Uniform: $F=1+\ln3\approx2.099$ . Both are below $2.408$ ; the shortfalls are $D(p\|q)$ , the divergences from softmax.
Change the temperature to $\tau=0.5$ and $\tau=2$ .

$\tau=0.5$ : $p\approx(0.867,0.117,0.016)$ , sharper. $\tau=2$ : $p\approx(0.506,0.307,0.186)$ , flatter. Doubling all the scores has the same effect as halving $\tau$ : only $s/\tau$ matters.

Check your understanding

You add 5 to every score before a softmax. The probabilities:

Don't change: every $e^{s_i+5}$ gets the same factor $e^5$ , which cancels in $Z$ .
Move toward the highest score.That is what dividing by a smaller $\tau$ does, not adding a constant.

This shift invariance is why implementations subtract

\max_js_j

before exponentiating (to avoid overflow) without changing the answer, and it characterizes the exponential among all positive maps.

A softmax with base 2 instead of $e$ is:

The same as an $e$ -softmax at temperature $1/\ln2\approx1.44$ times larger.
A genuinely different family of distributions. $2^s=e^{s\ln2}$ : only the scale of the scores changes.

The base is a unit, like measuring entropy in bits or nats. Since scores are usually learned, a different base would just be absorbed into the learned scale.

Why does attention divide $QK^\top$ by $\sqrt d$ ?

It keeps the scores' spread about constant as the dimension $d$ grows, so the softmax's effective temperature doesn't shrink with $d$ .
To make every score positive.Positivity isn't needed: the exponential takes care of that.

A dot product of

d

independent unit-variance products has standard deviation

\sqrt d

. Without the scaling, large

d

would make the softmax nearly one-hot, with tiny gradients everywhere else.

Practice

Only the exponentialA functional equation

Let $f:\R\to(0,\infty)$ be continuous and suppose that normalizing $f(s_1),\dots,f(s_n)$ gives the same probabilities after adding any constant $c$ to all the scores. Show $f(x)=Ab^x$ .

Hint

With two scores $x$ and $0$ , invariance says $f(x+c)/f(c)=f(x)/f(0)$ .

Solution

Put $g(x)=f(x)/f(0)$ . The hint gives $g(x+c)=g(x)g(c)$ for all $x,c$ : Cauchy's multiplicative equation. Then $h=\ln g$ is continuous and additive, $h(x+c)=h(x)+h(c)$ , so $h(x)=kx$ , and $f(x)=f(0)e^{kx}=Ab^x$ with $b=e^k$ . Every base is allowed; $k$ plays the role of $1/\tau$ .

The gradient of cross-entropyWhy training is easy

For $p=\mathrm{softmax}(s)$ ( $\tau=1$ ) and a true class $y$ , show that the gradient of $L=-\ln p_y$ with respect to $s$ is $p-e_y$ .

Solution

$L=-s_y+\ln\sum_je^{s_j}$ , so $\partial L/\partial s_k=-\mathbf 1\{k=y\}+e^{s_k}/Z=p_k-\mathbf 1\{k=y\}$ . The update pushes up the true score and pushes down each other score in proportion to its probability. With base 2 the same calculation gives an extra factor $\ln2$ .

Gumbel noise gives softmaxMcFadden's random utility

Each option's utility is $V_m+G_m$ , with $G_1,\dots,G_n$ independent standard Gumbel variables (distribution function $F(x)=\exp(-e^{-x})$ ). The person picks the option with the largest utility. Show that option $m$ is picked with probability $e^{V_m}/\sum_je^{V_j}$ .

Hint

Condition on the value $x$ of $V_m+G_m$ : every other option must come out below $x$ . Then substitute $u=e^{-x}$ .

Solution

With density $F'(y)=e^{-y}F(y)$ , $P(m\text{ wins})=\int F'(x-V_m)\prod_{j\ne m}F(x-V_j)\,dx=\int e^{-(x-V_m)}\prod_jF(x-V_j)\,dx$ . Since $\prod_jF(x-V_j)=\exp(-e^{-x}Z)$ with $Z=\sum_je^{V_j}$ , substituting $u=e^{-x}$ gives $e^{V_m}\int_0^\infty e^{-uZ}\,du=e^{V_m}/Z$ . The expected best utility is $\ln Z+\gamma$ (Euler's constant): the log-sum-exp once more. In machine learning the same fact is the “Gumbel-max trick” for sampling from a softmax.

Hedge is entropy-regularizedAdversarial bandits and experts

In the experts problem, after $t$ rounds expert $a$ has total reward $S_a$ . Hedge plays $p_a\propto e^{\eta S_a}$ . Show this is the $p$ maximizing $\langle p,S\rangle+\frac1\eta H(p)$ , and explain why plain “follow the leader” (put all weight on $\arg\max S$ ) is the $\eta\to\infty$ limit.

Solution

It is the theorem with scores $S_a$ and $\tau=1/\eta$ . As $\eta\to\infty$ the entropy term vanishes and the maximizer becomes the argmax. Follow-the-leader can be forced to switch every round by an adversary; the entropy term keeps Hedge's weights changing smoothly, which is what gives it $O(\sqrt{T\log K})$ regret against any adversary.

InteractiveApplebaum, Ch. 7: Communication (§§7.1–7.2, 7.5)

Channels and capacity

A noisy channel garbles some of what is sent. The mutual information between input and output measures how much gets through, and the sender can tune it by choosing how often to send each symbol. The best achievable value is the channel's capacity, and Shannon's theorem says it is a hard speed limit for reliable communication.

The idea

Channel. A source sends a symbol

X

; the receiver gets

Y

. The channel is described by the conditional probabilities

P(Y=y\mid X=x)

, which are fixed. The sender chooses the input law

P(X=x)

.

Capacity.

C=\max I(X;Y)

, the maximum over all input laws.

In the binary symmetric channel each bit is flipped with probability $\varepsilon$ , independently. If $P(X=1)=p$ , then $P(Y=1)=p(1-\varepsilon)+(1-p)\varepsilon$ , and $H(Y\mid X)=H_b(\varepsilon)$ whatever was sent, so

I(X;Y)=H_b\big(p(1-\varepsilon)+(1-p)\varepsilon\big)-H_b(\varepsilon), \qquad C=1-H_b(\varepsilon),

with the maximum at $p=\frac12$ , which makes $Y$ uniform.

Shannon's coding theorem. Send blocks of

n

bits through the channel, using

2^{nR}

of the possible blocks as codewords (a rate of

R

message bits per channel use). If

R<C

, then for large

n

there are codes whose probability of a decoding error is as small as you like. Above capacity this is impossible.

Explore

Flip probability ε Input law p = P(X = 1)

Right-hand plot

The channel. Line widths show the joint probabilities

P(X=x,Y=y)

.

Worked example

In a "Z-channel", a 0 is always received correctly, but a 1 arrives as 0 with probability $\frac12$ . Find its capacity and the input law that achieves it.

With $P(X=1)=p$ , find the law of $Y$ .

$Y=1$ only if a 1 was sent and survived: $P(Y=1)=\frac p2$ .
Find $H(Y\mid X)$ .

Given $X=0$ , $Y$ is certain: entropy 0. Given $X=1$ , $Y$ is a fair coin: entropy 1. So $H(Y\mid X)=(1-p)\cdot0+p\cdot1=p$ .
Write $I(X;Y)$ as a function of $p$ and maximise it.

$I(p)=H_b(\frac p2)-p$ . Using $\frac{d}{dq}H_b(q)=\log\frac{1-q}{q}$ ,

$I'(p)=\tfrac12\log\frac{1-p/2}{p/2}-1=0 \iff \frac{2-p}{p}=4 \iff p=\tfrac25.$
What is the capacity? What is surprising about the optimal input?

$C=H_b(0.2)-0.4\approx0.722-0.4=0.322$ bits, which equals $\log\frac54$ . The best input sends 1 only 40% of the time: since 1s are the unreliable symbol, it pays to use them less. For the symmetric channel the optimum is always $\frac12$ , but in general the capacity-achieving input need not be uniform.

Check your understanding

A binary symmetric channel has $\varepsilon=\frac12$ . What is its capacity?

0
$\frac12$ bit, since half the bits arrive correctlyThey do, but the receiver can't tell which half. Set ε to 0.5 and look at the output law.
1 bitThat is the capacity of a perfect channel.

With

\varepsilon=\frac12

,

Y

is a fair coin whatever was sent, so

Y

is independent of

X

and

I(X;Y)=0

for every input law. Indeed

1-H_b(\frac12)=0

.

A binary symmetric channel flips each bit with probability 0.9. How does its capacity compare with a channel that flips with probability 0.1?

It is the same.
It is nearly zero.The receiver can flip every bit back. That turns it into a channel with ε = 0.1.
It is lower than at ε = 0.5.The capacity is smallest at 0.5. Look at the capacity curve.

H_b(0.9)=H_b(0.1)

, so both have capacity

1-0.469=0.531

bits. A channel that is almost always wrong is almost as useful as one that is almost always right; only one that is unpredictable is useless.

Why is the capacity defined as a maximum over input laws?

The channel's noise is fixed, but the sender can choose how often to use each input symbol.
Because $I(X;Y)$ is the same for every input law, so the maximum is just that value.Move the p slider: $I(X;Y)$ changes with the input law.
To make the capacity independent of the noise.The capacity depends on the noise; for the symmetric channel it is $1-H_b(\varepsilon)$ .

I(X;Y)

depends on the channel and on the input law. Maximising over the part the sender controls leaves a number that describes the channel alone.

Practice

A ternary channelCapacity by symmetry

Inputs and outputs are $\{0,1,2\}$ . Each input $j$ arrives as $j$ or as $j+1\pmod3$ , with probability $\frac12$ each. Find the capacity.

Hint

$H(Y\mid X)$ does not depend on the input law. Which input law makes $H(Y)$ as large as possible?

Solution

$H(Y\mid X=j)=1$ for each $j$ , so $H(Y\mid X)=1$ . $H(Y)\le\log3$ , with equality when $Y$ is uniform, which happens when $X$ is uniform. So $C=\log3-1\approx0.585$ bits.

The repetition codeReliable, but slow

Over a binary symmetric channel with $\varepsilon=0.1$ , each message bit is sent three times and decoded by majority vote. Find the probability of a decoding error and the rate. How does this compare with what Shannon's theorem allows?

Solution

Decoding fails if at least two of the three copies are flipped: $3\varepsilon^2(1-\varepsilon)+\varepsilon^3=0.027+0.001=0.028$ . The rate is $\frac13$ bit per use. The capacity is $1-H_b(0.1)\approx0.531$ , so Shannon's theorem promises codes with rate up to about 0.53 and error probability as small as we like. Repetition buys reliability by giving up rate, and longer repetition makes the rate tend to 0; good codes avoid this.

From Applebaum, Probability and Information: An Integrated Approach (2nd ed., Cambridge, 2008)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 7.1The binary erasure channel

In the binary erasure channel each input bit is received correctly with probability $1-\varepsilon$ and erased (output E) with probability $\varepsilon$ ; let $p=P(S=1)$ . Find $I(0,0)$ , $I(0,E)$ , $I(1,1)$ , the mutual information $I(R,S)$ , and the capacity.

Hint

Output $0$ or $1$ reveals the input; output E reveals nothing, so $P(S=0\mid E)=1-p$ .

Solution

$Q(0)=(1-p)(1-\varepsilon)$ , $Q(E)=\varepsilon$ , $Q(1)=p(1-\varepsilon)$ , and $P(S=0\mid R=0)=1$ , $P(S=0\mid R=E)=1-p$ , $P(S=1\mid R=1)=1$ .

With $I(a,b)=\log\frac{P(a\mid b)}{P(a)}$ : $I(0,0)=-\log(1-p)$ , $I(0,E)=\log\frac{1-p}{1-p}=0$ , $I(1,1)=-\log p$ .

$I(R,S)=H(S)-H_R(S)$ . Given $R\in\{0,1\}$ there's no uncertainty; given $R=E$ the uncertainty is $H_b(p)$ . So $H_R(S)=\varepsilon H_b(p)$ and $I(R,S)=(1-\varepsilon)H_b(p)$ . This is maximal at $p=\tfrac12$ : $C=1-\varepsilon$ bits. The fraction $\varepsilon$ of erased bits is simply lost.

Exercise 7.2Output entropy of the binary symmetric channel

For the binary symmetric channel with error probability $\varepsilon$ and $p=P(S=1)$ , confirm $H(R)=H_b(x)$ with $x=\varepsilon+p-2\varepsilon p$ . Show $x=\tfrac12$ iff $p=\tfrac12$ when $\varepsilon\ne\tfrac12$ . Why doesn't the case $\varepsilon=\tfrac12$ matter for the capacity?

Hint

$x=P(R=1)$ .

Solution

$P(R=1)=p(1-\varepsilon)+(1-p)\varepsilon=\varepsilon+p-2\varepsilon p=x$ , so $H(R)=H_b(x)$ .

$x=\tfrac12\iff p(1-2\varepsilon)=\tfrac12(1-2\varepsilon)\iff p=\tfrac12$ , dividing by $1-2\varepsilon\ne0$ .

If $\varepsilon=\tfrac12$ , the output is independent of the input: $x=\tfrac12$ for every $p$ , $H(R)=1=H_S(R)$ , so $I(R,S)=0$ whatever $p$ is, and the capacity $1-H_b(\varepsilon)=0$ . The maximisation over $p$ is trivial, so nothing in the capacity calculation depends on solving $x=\tfrac12$ .

Exercise 7.5A cascade of two channels

Two binary symmetric channels $A\to B\to C$ with error probabilities $\varepsilon_1=0.14$ , $\varepsilon_2=0.21$ are connected in series, with $P(A=1)=0.4$ . Compute $I(A,B)$ and $I(A,C)$ and check $I(A,B)>I(A,C)$ .

Hint

The cascade is itself a binary symmetric channel with error $\varepsilon=\varepsilon_1+\varepsilon_2-2\varepsilon_1\varepsilon_2$ . For a BSC, $I=H_b(P(\text{output}=1))-H_b(\text{error})$ .

Solution

$P(B=1)=0.14+0.4-2(0.14)(0.4)=0.428$ , so $I(A,B)=H_b(0.428)-H_b(0.14)\approx0.985-0.584=0.401$ bits.

The cascade error is $\varepsilon=0.14+0.21-2(0.14)(0.21)=0.2912$ , and $P(C=1)=0.2912+0.4-2(0.2912)(0.4)\approx0.458$ . So $I(A,C)=H_b(0.458)-H_b(0.2912)\approx0.995-0.870=0.125$ bits.

$I(A,B)-I(A,C)\approx0.276>0$ : passing through a second noisy channel loses information (the data processing inequality).

Animated lessonApplebaum, Ch. 7: Communication (§§7.3–7.4)

Prefix codes and Huffman coding

To compress a source, give common symbols short codewords and rare ones long codewords. Entropy is the floor: no code can beat $H$ bits per symbol on average. Huffman's algorithm builds the best possible prefix code by repeatedly merging the two least likely symbols. Watch it work.

The idea

Prefix-free code. A binary code in which no codeword is the beginning of another. Such a code can be decoded as the bits arrive, with no separators. Codewords correspond to leaves of a binary tree: 0 for left, 1 for right.

Kraft–McMillan inequality. A binary prefix-free code with codeword lengths

l_1,\dots,l_n

exists if and only if

\sum_j 2^{-l_j}\le1

. (McMillan: the inequality also holds for every uniquely decodable code.)

Noiseless coding theorem. For a source with law

p_1,\dots,p_n

, every uniquely decodable code has average length

E(L)=\sum_j p_jl_j\ge H

. There is a prefix-free code with

E(L)<H+1

: take

l_j=\lceil-\log p_j\rceil

(Shannon–Fano lengths).

Huffman's algorithm. Start with each symbol as a one-node tree with its probability. Repeatedly join the two trees of smallest probability under a new root, whose probability is their sum, until one tree remains. The resulting code has the smallest

E(L)

of all prefix-free codes.

$E(L)=H$ exactly when every $p_j$ is a power of $\frac12$ . Otherwise the gap can be shrunk by coding blocks of $m$ symbols at a time, which gives $H\le E(L)/m<H+\frac1m$ bits per symbol.

Watch

Source (six symbols)

the two trees being merged trees still waiting codeword lengths at the end

Six symbols, sorted by probability. Each one starts as a tree on its own.
Merge the two least likely trees. The new node's probability is their sum.
Repeat with the trees that remain: again take the two smallest.
And again. A merged node is treated exactly like a symbol.
After this merge only two trees are left.
The last merge makes the root.
Label left branches 0 and right branches 1. Each codeword is the path from the root to its symbol. Compare the average length with the entropy.

Worked example

A source emits five symbols with probabilities $0.4,\ 0.2,\ 0.15,\ 0.15,\ 0.1$ . Build a Huffman code and compare it with the entropy and with the Shannon–Fano lengths.

Carry out the merges.

$0.1+0.15=0.25$ . Now the smallest are $0.15$ and $0.2$ : $0.35$ . Then $0.25+0.35=0.6$ . Finally $0.4+0.6=1$ .
Read off the codeword lengths and the average length.

The symbol of probability 0.4 joins only at the last merge: length 1. The other four sit two merges below the 0.6 node: length 3 each. So $E(L)=0.4\cdot1+0.6\cdot3=2.2$ bits. One valid code is $0,\ 100,\ 101,\ 110,\ 111$ . Kraft: $\frac12+4\cdot\frac18=1$ .
Compute the entropy.

$H=0.4\log2.5+0.2\log5+2\cdot0.15\log\frac1{0.15}+0.1\log10\approx0.529+0.464+0.821+0.332=2.146$ bits. So $H\le E(L)<H+1$ , with a gap of only about 0.05 bits.
What do the Shannon–Fano lengths $\lceil-\log p_j\rceil$ give?

Lengths $2,3,3,3,4$ , so $E(L)=0.8+0.6+0.45+0.45+0.4=2.7$ bits. It also lies within 1 bit of $H$ , as the theorem promises, but Huffman does half a bit better.

Check your understanding

Is there a binary prefix-free code for four symbols with codeword lengths 1, 2, 2, 3?

Yes, for example 0, 10, 11, 110110 begins with 11, which is another codeword.
No
Yes, as long as the shortest word goes to the most likely symbolWhether the lengths are possible doesn't depend on the probabilities at all.

\frac12+\frac14+\frac14+\frac18=\frac98>1

, so Kraft–McMillan rules it out. Lengths 1, 2, 3, 3 would work: 0, 10, 110, 111.

A source has two symbols with probabilities 0.9 and 0.1, so $H\approx0.469$ bits. What is the average length of its Huffman code?

0.469 bitsCodeword lengths are whole numbers, and each symbol needs at least one bit.
1 bit
Somewhere between 0.469 and 1, depending on the codeWith two symbols the only sensible code is 0 and 1.

The code is

\{0,1\}

, with

E(L)=1

, more than twice the entropy. Coding pairs of symbols brings it down to 0.645 bits per symbol (see the first practice problem); longer blocks get closer still.

For which sources does the Huffman code achieve $E(L)=H$ exactly?

When every probability is a power of $\frac12$
When the source is uniformTry three equally likely symbols: $H=\log3\approx1.585$ , but the best code has lengths 1, 2, 2 and $E(L)=\frac53$ .
Always, since Huffman codes are optimalOptimal among codes, but codes have whole-number lengths, and $H$ usually isn't of that form.

E(L)-H=\sum p_j(l_j+\log p_j)

vanishes only if

l_j=-\log p_j

for each

j

, which needs

p_j=2^{-l_j}

. Try the "dyadic" source in the animation.

Practice

Coding pairsThe extension of a source

For the source with probabilities 0.9 and 0.1, code pairs of independent symbols. Build the Huffman code for the four pairs and find the average length per original symbol.

Solution

The pairs have probabilities 0.81, 0.09, 0.09, 0.01. Merge $0.01+0.09=0.10$ , then $0.09+0.10=0.19$ , then $0.19+0.81$ . Lengths: 1, 2, 3, 3, so $E(L)=0.81+0.18+0.27+0.03=1.29$ bits per pair, or 0.645 bits per symbol, against $H\approx0.469$ . The bound says blocks of length $m$ are within $\frac1m$ of $H$ per symbol.

Likely symbols get short wordsAn exchange argument

Show that in a code of minimal average length, if $p_i>p_j$ then $l_i\le l_j$ .

Solution

Suppose $p_i>p_j$ but $l_i>l_j$ . Swap the two codewords. The code is still prefix-free, and the average length changes by $p_il_j+p_jl_i-p_il_i-p_jl_j=-(p_i-p_j)(l_i-l_j)<0$ . So the original code was not minimal.

From Applebaum, Probability and Information: An Integrated Approach (2nd ed., Cambridge, 2008)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 7.9A ternary prefix-free code

Show that a prefix-free code over $\{0,1,2\}$ with word lengths $1,2,2,2,2,3,3,3,3,4,4$ exists, and find one.

Hint

Check Kraft's inequality $\sum3^{-l_i}\le1$ , then assign words greedily from shortest to longest.

Solution

$\tfrac13+\tfrac49+\tfrac4{27}+\tfrac2{81}=\tfrac{27+36+12+2}{81}=\tfrac{77}{81}\le1$ , so such a code exists. One choice:

0;\quad 10,\ 11,\ 12,\ 20;\quad 210,\ 211,\ 212,\ 220;\quad 2210,\ 2211.

No word is a prefix of another: after using $0$ , the length-2 words start with 1 or 2; after $10,11,12,20$ the unused prefixes are $21,22$ ; and so on.

Exercise 7.12Shannon–Fano versus Huffman

A source has probabilities $0.27,0.31,0.14,0.18,0.10$ . Find (a) a prefix-free binary code by Shannon–Fano coding, (b) an optimal code by Huffman coding.

Hint

Shannon–Fano: $l_j=\lceil-\log_2p_j\rceil$ . Huffman: repeatedly merge the two least likely.

Solution

(a) Lengths $2,2,3,3,4$ (e.g. $-\log_20.10\approx3.32$ ). A code: $0.27\to00$ , $0.31\to01$ , $0.14\to100$ , $0.18\to101$ , $0.10\to1100$ . Mean length $2.52$ .

(b) Merge $0.10+0.14=0.24$ , then $0.18+0.24=0.42$ , then $0.27+0.31=0.58$ . Code: $0.31\to10$ , $0.27\to11$ , $0.18\to00$ , $0.14\to010$ , $0.10\to011$ . Mean length $2.24$ , against entropy $H\approx2.21$ bits.

Exercise 7.15Two Huffman codes

(a) For probabilities $0.02,0.09,0.15,0.21,0.26,0.27$ , show the Huffman procedure can be carried out in two different ways; write down both codes. Is either better? (b) Find the redundancy $1-\eta$ of the optimal code, where $\eta=H/\mathbb E(L)$ .

Hint

After two merges there is a tie between two nodes of probability $0.26$ .

Solution

(a) Merge $0.02+0.09=0.11$ , then $0.11+0.15=0.26$ . Now $0.21$ must be merged with one of two $0.26$ 's: the symbol or the merged node. Either way the remaining two are merged next, then the root.

Merging $0.21$ with the merged node gives, for instance, $0.26\to00$ , $0.27\to01$ , $0.21\to10$ , $0.15\to110$ , $0.02\to1110$ , $0.09\to1111$ . Merging it with the symbol gives $0.21\to00$ , $0.26\to01$ , $0.27\to10$ , $0.15\to110$ , $0.02\to1110$ , $0.09\to1111$ . The codewords differ but the length profile is the same, $(4,4,3,2,2,2)$ , with $\mathbb E(L)=2.37$ . Both are optimal; neither is better.

(b) $H\approx2.324$ bits, so $\eta\approx2.324/2.37\approx0.981$ and the redundancy is about $0.019$ .

InteractiveApplebaum, Ch. 8 (§8.7) and Ch. 9 (§§9.6–9.7)

Entropy for densities and the Gaussian channel

Real signals (voltages, waveforms) take continuous values. Entropy carries over to densities only awkwardly, but mutual information carries over cleanly, and with it the capacity of the most important channel in practice: a signal plus Gaussian noise.

The idea

Entropy of a density (Applebaum (8.25)). For

X

with pdf

f

,

H(X)=-\int f(x)\log f(x)\,dx

. For

X\sim U(a,b)

,

H(X)=\log(b-a)

, which is negative when

b-a<1

: unlike the discrete case, this “entropy” can be below zero.

Why it is awkward. Chop the range into bins of width $\Delta$ and let $\hat X$ be the bin $X$ falls in. Then $H(\hat X)\approx H(X)-\log\Delta$ , which goes to $+\infty$ as $\Delta\to0$ : describing a continuous value exactly takes infinitely many bits. $H(X)$ is what remains after subtracting the infinite part, so it is a relative quantity, not an amount of information.

The Gaussian has the most entropy for its variance (Applebaum Thm 8.10). If

X

has a pdf, mean

\mu

and variance

\sigma^2

, then

H(X)\le\tfrac12\log(2\pi e\sigma^2),

with equality exactly when

X\sim N(\mu,\sigma^2)

. It is the maximum entropy principle again: knowing only the mean and variance, assume a normal law.

Mutual information (Applebaum §9.7).

I(X,Y)=\iint f_W(x,y)\log\frac{f_W(x,y)}{f_X(x)f_Y(y)}\,dx\,dy=H(Y)-H_X(Y)

. It is always

\ge0

, zero exactly for independence, and the infinite parts cancel under discretization:

I(\hat X,\hat Y)\to I(X,Y)

. For a bivariate normal with correlation

\rho

,

I(X,Y)=-\tfrac12\log(1-\rho^2)

.

The Gaussian channel (Applebaum Thm 9.8). Send

X

with mean 0 and variance (power)

\sigma_X^2

; receive

Y=X+Z

, with noise

Z\sim N(0,\sigma_Z^2)

independent of

X

. The capacity, the largest

I(X,Y)

over input laws, is

C=\tfrac12\log\Big(1+\frac{\sigma_X^2}{\sigma_Z^2}\Big)\ \text{bits per use},

attained when

X

is normal. The proof is three lines:

I=H(Y)-H_X(Y)=H(Y)-H(Z)

, since once

X

is known all uncertainty in

Y

is noise;

\mathrm{Var}(Y)=\sigma_X^2+\sigma_Z^2

is fixed, so

H(Y)

is largest when

Y

is normal, which happens when

X

is.

The ratio $\sigma_X^2/\sigma_Z^2$ is the signal-to-noise ratio. Capacity grows only logarithmically in it: quadrupling the power buys one more bit per use, at most.

Explore

Standard deviation σ Bin width Δ for discretizing Signal-to-noise ratio σ²ₓ/σ²_z

Four densities, all with mean 0 and the same variance

\sigma^2

. normal triangular Laplace uniform. The bars show the normal law discretized into bins of width

\Delta

.

Capacity

C=\tfrac12\log(1+\mathrm{SNR})

of the Gaussian channel, with the chosen SNR marked. The dashed line is

\tfrac12\log\mathrm{SNR}

: at high SNR, each doubling of power adds half a bit.

Worked example

Three short calculations, in bits.

$X\sim U(0.1,\,0.5)$ . Find $H(X)$ .

$\log_2(0.4)\approx-1.32$ bits. Negative: a density squeezed into an interval shorter than 1 has negative entropy.
$X,Y$ are jointly normal with correlation $\rho=0.8$ . Find $I(X,Y)$ .

$-\tfrac12\log_2(1-0.64)=-\tfrac12\log_2(0.36)\approx0.74$ bits. It depends only on $\rho$ , not on the variances.
A channel has signal power 15 and Gaussian noise power 1. Find the capacity, and the capacity if the power is doubled.

$C=\tfrac12\log_2(16)=2$ bits per use. With power 30: $\tfrac12\log_2(31)\approx2.48$ bits: doubling the power bought less than half a bit.

Check your understanding

Doubling $\sigma$ changes the entropy of a normal random variable by:

$+1$ bit.
A factor of 2. $H=\log(\sigma\sqrt{2\pi e})$ : scaling $\sigma$ adds to the logarithm.

H(cX)=H(X)+\log|c|

for any density. The mean does not appear at all: shifting a density doesn't change its uncertainty.

As the bin width $\Delta$ shrinks, the entropy $H(\hat X)$ of the discretized normal:

Grows without bound, like $H(X)-\log\Delta$ .
Converges to $H(X)$ .Only $H(\hat X)+\log\Delta$ does.

Each halving of the bins adds about one bit: you need one more binary digit to say which half of a bin the value is in. That is why mutual information, a difference in which this drift cancels, is the meaningful quantity for continuous signals.

For a fixed signal power, which input law gives the Gaussian channel its capacity?

Uniform, because it spreads the signal evenly.The uniform has less entropy than the normal for the same variance.
Normal: it makes $Y=X+Z$ normal, the variance- $(\sigma_X^2+\sigma_Z^2)$ law of maximum entropy.

I=H(Y)-H(Z)

and

H(Z)

is fixed, so the best input makes

H(Y)

as large as possible, and Theorem 8.10 says that is the normal law.

Practice

The normal's entropyA short integral

Show that $H(X)=\tfrac12\log(2\pi e\sigma^2)$ for $X\sim N(\mu,\sigma^2)$ .

Solution

$-\log f(x)=\log(\sigma\sqrt{2\pi})+\frac{(x-\mu)^2}{2\sigma^2}\log e$ . Take expectations: $\mathbb E(X-\mu)^2=\sigma^2$ , so $H=\log(\sigma\sqrt{2\pi})+\tfrac12\log e=\tfrac12\log(2\pi e\sigma^2)$ .

Noise sets the floorCorollary 9.6

For $Y=X+Z$ with $X,Z$ independent, explain why $H_X(Y)=H(Z)$ , and deduce that if $Z$ is normal with variance $\sigma_Z^2$ , no input can make $I(X,Y)$ exceed $\tfrac12\log(1+\sigma_X^2/\sigma_Z^2)$ .

Solution

Given $X=x$ , $Y=x+Z$ is $Z$ shifted by $x$ , and shifting doesn't change entropy, so $H_X(Y)=H(Z)$ . Then $I=H(Y)-H(Z)\le\tfrac12\log(2\pi e(\sigma_X^2+\sigma_Z^2))-\tfrac12\log(2\pi e\sigma_Z^2)$ , by Theorem 8.10 applied to $Y$ , whose variance is $\sigma_X^2+\sigma_Z^2$ .

SimulationApplebaum, Ch. 10: Markov chains and their entropy

Markov chains and entropy rate

A Markov chain forgets everything except where it is now. That one rule makes it settle into an equilibrium from any start, and it makes the information it produces per step easy to compute. Set the two switching probabilities and watch the chain converge.

The idea

Markov chain. A sequence

X_0,X_1,\dots

on a finite state space with

P(X_{n+1}=j\mid X_n=i,\ X_{n-1},\dots,X_0)=P_{ij}

, depending only on

i

and

j

. The transition matrix

P

has non-negative entries and rows summing to 1.

Chapman–Kolmogorov. The

n

-step transition probabilities satisfy

P^{(m+n)}_{ij}=\sum_kP^{(m)}_{ik}P^{(n)}_{kj}

, so

P^{(n)}=P^n

. If

\pi^{(n)}

is the law of

X_n

, written as a row vector, then

\pi^{(n)}=\pi^{(0)}P^n

.

Invariant distribution. A law

\rho

with

\rho P=\rho

. If the chain starts with law

\rho

, every

X_n

has law

\rho

and the process is stationary. If some power

P^m

has all entries positive,

\rho

is unique and

\pi^{(n)}\to\rho

from every starting law.

Entropy rate.

h=\lim_{n\to\infty}\frac1nH(X_0,\dots,X_{n-1})

. For a stationary Markov chain,

h=H(X_1\mid X_0)=-\sum_i\rho_i\sum_jP_{ij}\log P_{ij},

the average, under $\rho$ , of the entropies of the rows of $P$ . It satisfies $h\le H(\rho)$ , with equality exactly when all the rows are equal, that is, when the $X_n$ are i.i.d.

Explore

a = P(0 → 1) b = P(1 → 0)

The chain, and a simulated path: state 0 state 1

P(X_n=0\mid X_0=0)

P(X_n=0\mid X_0=1)

\rho_0

Worked example

A particle moves on the states $0,1,2$ with transition matrix

P=\begin{pmatrix}\frac12&\frac12&0\\ \frac14&\frac12&\frac14\\ 0&\frac12&\frac12\end{pmatrix}.

Starting from 0, what is the law of $X_2$ ?

It is the first row of $P^2$ : $\big(\frac12\cdot\frac12+\frac12\cdot\frac14,\ \frac12\cdot\frac12+\frac12\cdot\frac12,\ \frac12\cdot\frac14\big)=\big(\frac38,\frac12,\frac18\big)$ .
Find the invariant distribution.

Solve $\rho P=\rho$ . The first column gives $\rho_0=\frac12\rho_0+\frac14\rho_1$ , so $\rho_1=2\rho_0$ ; by symmetry $\rho_1=2\rho_2$ . With $\rho_0+\rho_1+\rho_2=1$ : $\rho=(\frac14,\frac12,\frac14)$ . $P^2$ has all entries positive, so this is the limit from any start.
Compute the entropy rate.

The rows have entropies 1, 1.5 and 1 bits. So $h=\frac14\cdot1+\frac12\cdot1.5+\frac14\cdot1=1.25$ bits per step.
Compare with $H(\rho)$ and interpret.

$H(\rho)=\frac14\cdot2+\frac12\cdot1+\frac14\cdot2=1.5$ bits. An i.i.d. sequence with the same one-step law would produce 1.5 bits per step; the chain produces only 1.25, because each step is partly predictable from the last. A source like this can be compressed to about 1.25 bits per symbol, but only by a code that uses the previous symbol.

Check your understanding

The two-state chain above has $P(0\to1)=a$ and $P(1\to0)=b$ , with $a+b>0$ . What is $\rho_0$ , the long-run fraction of time in state 0?

$\dfrac{b}{a+b}$
$\dfrac{a}{a+b}$ A large $a$ means the chain leaves 0 quickly, so it should spend less time there, not more.
$\frac12$ , by symmetryThe two states are only symmetric when $a=b$ .

In equilibrium the flow out of 0 balances the flow in:

\rho_0a=\rho_1b

. With

\rho_0+\rho_1=1

this gives

\rho_0=b/(a+b)

.

Take $a=b=1$ : the chain switches state at every step. Starting from 0, does $P(X_n=0)$ converge?

Yes, to $\frac12$ Starting from 0, the chain is at 0 at every even time and at 1 at every odd time. Set both sliders to 1.
No, it alternates between 1 and 0, although $(\frac12,\frac12)$ is invariant.
No, and there is no invariant distribution.Check $(\frac12,\frac12)P$ .

P^n

alternates between the identity and the swap matrix, so no power has all entries positive and the convergence theorem doesn't apply. The chain is periodic. Its invariant law

(\frac12,\frac12)

still gives the long-run fraction of time in each state.

For a stationary Markov chain with invariant law $\rho$ , which is always true?

$h\le H(\rho)$
$h\ge H(\rho)$ $h=H(X_1\mid X_0)$ , and conditioning cannot increase entropy on average.
$h=H(\rho)$ Only when $X_1$ is independent of $X_0$ . Try $a=0.1,\ b=0.3$ .

h=H(X_1\mid X_0)\le H(X_1)=H(\rho)

, with equality exactly when

X_1

and

X_0

are independent, which for a Markov chain means every row of

P

equals

\rho

. For two states that is the line

a+b=1

.

Practice

A walk around a cycleDoubly stochastic matrices

A particle on the cycle $0,1,\dots,N-1$ ( $N\ge3$ ) steps one place clockwise or anticlockwise with probability $\frac12$ each. Show that the uniform law is invariant and find the entropy rate. For which $N$ does $P(X_n=0\mid X_0=0)$ converge?

Solution

Every column of $P$ also sums to 1, so $\frac1N(1,\dots,1)P=\frac1N(1,\dots,1)$ . Each row has two entries $\frac12$ , so $h=1$ bit per step, while $H(\rho)=\log N$ . For even $N$ the chain alternates between even and odd states, so $P(X_n=0\mid X_0=0)=0$ for odd $n$ and there is no convergence. For odd $N$ some power of $P$ is positive and the probability tends to $\frac1N$ .

A sticky chainEntropy rate of two states

Compute $\rho$ , $h$ and $H(\rho)$ for the two-state chain with $a=0.1$ , $b=0.3$ . Check your answers in the explorer.

Solution

$\rho=(\frac{0.3}{0.4},\frac{0.1}{0.4})=(0.75,0.25)$ . $h=0.75\,H_b(0.1)+0.25\,H_b(0.3)\approx0.75\cdot0.469+0.25\cdot0.881=0.572$ bits, while $H(\rho)=H_b(0.25)\approx0.811$ bits. The chain stays put most of the time, which makes it more predictable than an i.i.d. sequence spending the same fraction of time in each state.

From Applebaum, Probability and Information: An Integrated Approach (2nd ed., Cambridge, 2008)

Numbers match the book. Each question is restated in our own words; the hints and solutions are written for this page.

Exercise 10.14Invariant distributions

Decide whether each chain has an invariant distribution and find it: (a) $\begin{pmatrix}0.7&0.3\\0.4&0.6\end{pmatrix}$ ; (b) $\begin{pmatrix}1/2&1/4&1/4\\1/8&1/2&3/8\\3/8&1/4&3/8\end{pmatrix}$ ; (c) $\begin{pmatrix}0&1&0\\0&2/3&1/3\\1/6&5/6&0\end{pmatrix}$ .

Hint

Solve $\pi P=\pi$ with $\sum\pi_i=1$ . A finite chain always has at least one invariant distribution; all three here are irreducible, so it's unique.

Solution

(a) $0.3\pi_1=0.4\pi_2$ , so $\pi=(4/7,3/7)$ .

(b) Each column sums to $1$ (the matrix is doubly stochastic), so the uniform $\pi=(1/3,1/3,1/3)$ is invariant.

(c) The equations give $\pi_1=\tfrac16\pi_3$ and $\pi_3=\tfrac13\pi_2$ . So $\pi\propto(1,18,6)$ : $\pi=(0.04,0.72,0.24)$ .

Exercise 10.23Entropy rates

Compute the entropy rates $h=\sum_i\pi_iH(P_{i\cdot})$ of the stationary chains in Exercise 10.14.

Hint

Weight the entropy of each row by the invariant probability of that state.

Solution

(a) $h=\tfrac47H_b(0.3)+\tfrac37H_b(0.4)\approx\tfrac47(0.881)+\tfrac37(0.971)\approx0.920$ bits.

(b) Row entropies $1.5$ , $\approx1.406$ , $\approx1.561$ ; averaged uniformly, $h\approx1.489$ bits.

(c) Row entropies $0$ , $H_b(1/3)\approx0.918$ , $H_b(1/6)\approx0.650$ . So $h\approx0.72(0.918)+0.24(0.650)\approx0.817$ bits.

Exercise 10.24Bounds on the entropy rate

For a stationary Markov chain on $N$ states, show $0\le h(X)\le\log N$ . When does equality hold?

Hint

$h=\sum_i\pi_iH(P_{i\cdot})$ is an average of entropies of distributions on $N$ points.

Solution

Each $H(P_{i\cdot})$ lies in $[0,\log N]$ , and the $\pi_i$ are weights summing to 1, so $h\in[0,\log N]$ .

$h=0$ iff every row with $\pi_i>0$ is deterministic (the chain moves deterministically from every state it visits). $h=\log N$ iff every row with $\pi_i>0$ is uniform; for an irreducible chain this means $P_{ij}=1/N$ for all $i,j$ , i.e. i.i.d. uniform symbols.