Information theory

Billy Fang
Instructor: Thomas Courtade
Fall 2016

These are my personal notes from an information theory course taught by Prof. Thomas Courtade. Most of the
material is from [1]. Any errors are mine.

Contents
1 Entropy 1

2 Asymptotic Equipartition Property 2

3 Entropy rates of a stochastic process 4

4 Data compression 5

5 Channel capacity 6

6 Differential entropy 14

7 Gaussian channel 16

8 Entropy power inequality 17

9 Rate distortion theory 20

10 Approximating distributions and entropy 25

11 Computing rate distortion and channel capacity 27

12 Information theory and statistics 29

12.1 Theory of types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
12.2 Large deviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
12.3 Conditional limit theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
12.4 Fisher information and Cramer-Rao lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

13 Entropy methods in mathematics 36

13.1 Fisher information and entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
13.2 The logarithmic Sobolev inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
13.3 Concentration of measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
13.4 Talagrand’s information-transportation inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
13.5 The blowing-up phenomenon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1 Entropy
[Absent from first lecture; refer to Chapter 2 of [1] for missing introductory material.]
X
H(X) = − p(x) log p(x) = −E log p(X).
x
X
H(Y | X) = p(x)H(Y | X = x) = −E log p(Y | X).
x

Chain rule: H(X, Y ) = H(X) + H(Y | X).

H(X | Y ) ≤ H(X) (conditioning reduces uncertainty), but it is not always true that H(X | Y = y) ≤ H(X) for
each y (only true on average).
1 2
Pinsker’s inequality: D(pkq) ≥ 2 ln 2 kp − qk1 .
Entropy H(p1 , . . . , pn ) is concave in (p1 , . . . , pn ).
(i)
H(X) ≤ log|X |. Proof: use Jensen’s inequality. Let pX = (p1 , . . . , pn ) and let pX :=
(i)
(pi , . . . , pn , p1 , . . . , pn−1 ). Then H(pX ) = H(pX ). So,
n n
!
X 1 (i) 1 X (i)
H(X) = H(pX ) ≤ H p = H(1/n, . . . , 1/n) = log n.
i=1
n n i=1 X

I(X; Y ) is concave in pX for fixed pY |X . It is convex in pY |X for fixed pX . To see the first one, note I(X; Y ) =
H(Y ) − H(Y | X). For fixedP pY |X , we have H(Y | X) is linear in pX , and H(Y ) is concave function composed
with a linear function pY = x pY |X (y)pX (x) of pX .
Data processing inequality: if X → Y → Z is a Markov chain (X and Z independent given Y ), then I(X; Z) ≤
I(X; Y ).

I(X; Z) ≤ I(X; Z) + I(X; Y | Z) = I(X; Y, Z) = I(X; Y ) + I(X; Z) = I(X; Y ).

We discuss a connection between information and estimation. Consider the Markov chain X → Y → X(Y b )
where Y is the noisy observation of X, and X(Y ) is an estimator of X based on Y . Let Pe = P(X 6= X(Y )).
b b

Theorem 1.1 (Fano’s inequality).

H(Pe ) + Pe log|X | ≥ H(X | X).
b

Proof. Let E be the indicator for X 6= X

b so that H(E) = H(Pe ).
Using chain rule in two ways gives

H(E, X | X)
b = H(X | X)
b + H(E | X, X)
b
= H(X | X)
b

and

H(E, X | X)
b = H(E | X)
b + H(X | E, X)
b
≤ H(E) + pe H(X | X,
b E = 1) + (1 − pe )H(X | X,
b E = 0)
= H(Pe ) + pe log|X |

The log|X | can be replaced by log(|X | − 1).

b ) 6= X), we have
Corollary 1.2. With Pe := minXb P(X(Y

H(Pe ) + Pe log|X | ≥ H(X | Y )

1
 b ≤ I(X; Y ) which implies H(X | X)
Proof. By the data-processing inequality, I(X; X) b ≥ H(X | Y ).

We now clarify the interpretation of “entropy is the average number of bits needed to describe a random variable.”
Consider a function f : X → {0, 1}∗ that maps the alphabet to arbitrary length bit strings. We want f to be injec-
tive (able to distinguish between letters in the alphabet). Let `(f (x)) be the length of this description of x. Then
E[`(f (X))] is the average length of this description.

X
E[`(f (X))] = p(x)`(f (x))
x
X p(x)
= H(X) + p(x) log
x
2−`(f (x))
X X 0 X p(x)
= H(X) − p(x) log 2−`(f (x )) + p(x) log
2−`(f (x)) / 2−`(f (x0 ))
P
x x0 x x0
X 0
= H(X) − log 2−`(f (x )) + D(pX kQ)
x0
X 0
≥ H(X) − log 2−`(f (x )) .
x0

Proposition 1.3. X 0
2−`(f (x )) ≤ log 2|X |.
x0

Proof. Consider maximizing the sum on the left-hand side. Respecting injectivity of f , this is the first |X | terms of
the series
2−0 + 2−1 + 2−1 + 2−2 + 2−2 + 2−2 + 2−2 + · · ·

Continuing from above, we have shown

E[`(f (X))] ≥ H(X) − log log 2|X |.

Suppose we observe i.i.d. X1 , . . . , Xn . The alphabet has size |X |n . Any description of these n outcomes requires
at least H(X n ) − log(1 + n log|X|) bits. Using independence, we have the following lower bound on the average
number of bits per outcome.
1 1
E[`(fn (X n ))] ≥ H(X1 ) − log(1 + n log|X |). = H(X) − O(log(n)/n).
n n
Suppose X = {a, b, c} and f (a) = 0, f (b) = 1, and f (c) = 01. Concatenating is no longer injective: 01101 could
correspond to abbc or cbc. If we want uniquely decodable f , then the upper bound of the previous proposition is 1.
Consider X being uniform on the above alphabet. Let f (a) = Λ, f (b) = 0, and f (c) = 1. Then E[`(f (X))] =
2/3 < 1.58 ≈ H(X).

2 Asymptotic Equipartition Property

Suppose we observe i.i.d. Ber(1 − p) random variables. The “typical” sequence has pn zeros and (1 − p)n ones.
The probability of a single such sequence is ppn (1 − p)(1−p)n = 2−nH(X) .
Applying the law of large numbers to f (x) = − log pX (x) gives
1X 1 1 p
f (Xi ) = log → H(X)
n i n pX n (xn )

So pX n (xn ) ≈ 2−nH(X) .

2
Theorem 2.1.
1 p
− log pX n (xn ) → H(X).
n

Last time we saw a few examples where the formula for entropy “magically” appeared. One was that if f : X →
{0, 1}∗ is injective, then E`(f (X)) ≥ H(X) − log log 2|X |. Today we will show that there exists an f ∗ such that
E`(f ∗ (X)) . H(X).
We also saw that if we observe an i.i.d. sequence of Bern(1 − p) random variables, then the “typical” sequence of
length n has n(1 − p) ones and np zeros, and moreover pX n (xn ) ≈ 2−nH(X) .
To formally define “typical,” we will work backwards from the above example.
(n)
Definition 2.2. The typical set A ⊂ X n is defined as

A(n)
 = {xn : 2−n(H(X)+) ≤ pX n (xn ) ≤ 2−n(H(X)−) }.


Proposition 2.3 (Properties of typical sets).
(n)
1. x ∈ A ⇐⇒ H(X) −  ≤ − n1 log pX n (xn ) ≤ H(X) + .
(n)
2. P(X n ∈ A ) → 1.
(n)
3. |A | ≤ 2n(H(X)+) .
(n)
4. |A | ≥ (1 − 0 )2n(H(X)−) for n sufficiently large.

Proof. 1. follows by definition. 2. follows by the AEP/LLN.

3. follows by X
−n(H(X)+)
1≥ pX n (x) ≥ |A(n)
 |2 .
(n)
x∈A

4. X
−n(H(X)−)
1 −  ≤ P (X ∈ A(n)
 )= pX n (x) ≤ |A(n)
 |2 .
(n)
x∈A

(n) (n)
In summary, A together has almost all the proability mass, the probability on sequences in A is roughly
uniform, and the cardinality is roughly 2nH(X) .
(n) (n) (n)
If Bδ is the smallest set with probability ≥ 1 − δ, then |Bδ | ≈ |A | in some sense. More precisely,
1 (n)
log|Bδ | > H(X) − δ 0
n
Proof.
(n)
1 −  − δ ≤ P (Bδ ∩ A(n)
 ) union bound
X
n
= pX n (x )
xn ∈A∩B
X
≤ 2−n(H(X)−)
xn ∈A∩B
(n)
≤ |Bδ |2−n(H(X)−)
(n)
|Bδ | ≥ (1 −  − δ)2n(H(X)−)
1 (n)
log|Bδ | > H(X) −  + log(1 −  − δ)
n

3
 We now describe a scheme to describe X with H(X) bits on average: the typical set encoding.
(n) (n)
If we label all sequences in A , we need log|A | + 1 bits per label.
(n) (n) (n)
To encode x ∈ A , we put a flag 1 in front of the label (length log|A | + 2. If x ∈
/ A , we put a flag 0 in front
of the binary representation of the sequence (length n(log|X| + 1) + 1).

1 1 1
E`(f (X n )) ≤ P (A(n) (n)
 )(log|A | + 2) + (1 − P (A(n)
 ))(n(log|X | + 1) + 1)
n n n
1
≤ (H(X) + ) + + δ(n)((log|X | + 1) + 1/n)
n
≤ H(X) + 2
Although this scheme is not practical, we see that we get a matching upper bound to our earlier lower bound H(X) −
log log 2|X | on the expected length.

3 Entropy rates of a stochastic process

For a random process {Xi } the entropy rate is defined as
1
H({Xi }) = lim H(X1 , . . . , Xn )
n→∞ n
provided the limit exists.

Theorem 3.1 (Shannon-McMillan-Breiman). For stationary ergodic processes,

1
− log pX n (X1 , . . . , Xn ) → H({Xi })
n
with probability 1.
This is the AEP generalized to more general processes. AEP-like properties also generalize.
A stationary process has shift-invariant joint probabilities: pP
X1 ,...,Xk = pX`+1 ,...,X`+k . An ergodic process has
n
time averages equalling ensemble averages in some sense, e.g. n1 i=1 Xi → EX (a LLN-type property).
Non-ergodic process: choose a p-coin or a q-coin with equal probability (p 6= q) and flip it repeatedly. The space
average is (p + q)/2, but the time average is either p or q.
Lemma 3.2. For a stationary process,

H({Xi }) = lim H(Xn | X1 , . . . , Xn−1 ).

n→∞

Proof. 0 ≤ H(Xn+1 | X1 , . . . , Xn ) ≤ H(Xn+1 | X2 , . . . , Xn ) = H(Xn | X1 , . . . , Xn−1 ). So this is a nonnegative

decreasing sequence and therefore converges. Pn
If an → a then the Cesaro means bn P := n1 i=1 ai → a also converge to the same limit. Applying this to
n
an := H(Xn | X1 , . . . , Xn−1 ) and bn = n1 i=1 H(Xi | X1 , . . . , Xi−1 ) = n1 H(X1 , . . . , Xn ) concludes.
Markov chains are an example of stochastic processes. In particular if there is a stationary distribution π (satisfies
πP = π), then the Markov chain is stationary and we may use the previous lemma. So H({Xi }) = limn→∞ H(Xn |
Xn−1 ). We have
X X
H(Xn | Xn−1 ) = π(i)H(Xn | Xn−1 = i) = π(i)H(pi1 , . . . , pim )
i i

The Second Law of Thermodynamics: the entropy of an isolated system is not decreasing. We might model such
a system with a Markov process. [Example: Ehrenfest gas system?]
Suppose we start a Markov chain in two different states, and let their state distributions at time n be Pn and Qn
respectively, then
D(Pn+1 kQn+1 ) ≤ D(Pn kQn ).
If Pn is stationary, D(Pn kπ) is decreasing.

4
4 Data compression
We have seen that it takes H(X) bits on average to describe X. This is the fundamental idea behind data com-
pression.
From AEP, it takes about nH(X) bits to represent X1 , . . . , Xn . But this scheme (using typical set) is wildly
impractical.
Let c : X → {0, 1}∗ be a source code. We are interested in L(c) = x pX (x)`(c(x)).
P
x pX (x) c(x) `(c(x))
a 1/5 00 2
For example, has L(c) = 1.6 and H(X) = 1.52.
b 2/5 01 2
c 2/5 1 1
This defines the extension code c∗ defined by c∗ (x1 · · · xn ) = c(x1 ) · · · c(xn ).
A nonsingular code c is an injective code. A code is uniquely decodable if c∗ is nonsingular (injective).
A code is prefix-free (a.k.a. instantaneous) if no code word is a prefix of any other code word. Confusingly, such
codes are sometimes called prefix codes.

codes ⊃ nonsingular cords ⊃ uniquely decodable codes ⊃ prefix-free codes.

PN
Theorem 4.1 (Kraft inequality). Any prefix code satisfies i=1 2−`i ≤ 1.
PN −`i
Also, for any numbers (`i )N
i=1 satisfying i=1 2 , there exists a prefix code with these codeword lengths.

Proof. Sort `1 ≤ · · · ≤ `N . Draw a binary tree of code words. If `1 = 2 for example, let the first code word be 00 and
prune the children at that node. Then choose the next smallest available word of length `2 and so on. The inequality
guarantees that this is possible and we don’t run out of words.
We now show any prefix code satisfies the inequality. Consider inputting a sequence of random coin flips into a
decoder which spits out x if the input is a code word.
[ X X
1 ≥ P(some x comes out) = P {x comes out} = P(x comes out) = 2−`(c(x))
x∈X x∈X x∈X

2−`i ≤ 1.
P
Theorem 4.2 (McMillan inequality). Any uniquely decodable code has codeword lengths satisfying i

We prove McMillan’s inequality on the homework. Recall that for any f , we proved
X
E[`(f (X))] = H(X) + D(pX kq) − log 2−`(f (x))
x

where q(x) ∝ 2−`(f (x)) . If c is uniquely decodable, then applying McMillan’s inequality shows that E`(c(X)) ≥
H(X).
How do we design good codes? Consider choosing `i to minimize i pX (i)`i subject to i 2−`i ≤ 1. Then the
P P
optimal `i s satisfy `i = − log pX (i). This is natural when considering D(pX kq).
However, our code lengths must be integers, so we can consider instead `i = d− log pX (i)e.
X X
pX (i)`i ≤ pX (i)(1 − log pX (i)) = H(X) + 1.
i i

Theorem 4.3. Any uniquely decodable code c satisfies E`(c(X)) ≥ H(X) (impossibility), and there exists a code c∗
such that E`(c∗ (X)) ≤ H(X) + 1 (achievability).

The Huffman code is an “efficient” construction of the best prefix code.

Consider the following alphabet and distribution.
x a b c
pX 1/5 2/5 2/5

5
 At each stage we group the two least probable symbols into one and add their probabilities. We start with {a}, {b},
and {c}. After the first stage we have {a, b} w.p. 3/5 and c w.p. 2/5. Finally, we merge everything to get {a, b, c}. At
each grouping, label the edges 0 and 1. Read backwards to get the code: a = 00, b = 01, and c = 1.
E`(c(X)) = 2/5 + 4/5 + 2/5 = 8/5 ≈ 1.6. While H(X) ≈ 0.722.

Theorem 4.4. Huffman coding is optimal among all uniquely decodable codes. That is, if c∗ is the Huffman code,
then E`(c∗ (X)) ≤ E`(c(X)) for any uniquely decodable code c.

See book for proof.

Aside: consider the above distribution with code a = 00, b = 1, and c = 0. This is not uniquely decodable
(although it is nonsingular). Its expected length is 6/5, shorter than the Huffman code.
So we showed
H(X) ≤ L∗ ≤ H(X) + 1.
One “trick” to get rid of the +1 is to group symbols together and give a code X n → {0, 1}∗ . Then we have the
following bounds on the number of bits to describe n symbols: H(X n ) ≤ E`(c∗ (X)) ≤ H(X n ) + 1. Dividing by n
gives the following bounds on the number of bits per symbol:
1 1
H(X) ≤ E`(c∗ (X n )) ≤ H(X) + .
n n
The Huffman code for X n requires building a tree with |X |n leaves. We have a tradeoff between length of the code
and computational complexity.
[See Lempel-Ziv for universal coding: variable length coding.]
This motivates arithmetic coding, which has complexity linear in n (instead of exponential as in the above discus-
sion). We discuss Shannon-Fano-Elias coding. We will see that E`(cSF E (X)) ≤ H(X) + 2.
Let the distribution of X be (p1 , . . . , p3 ). We partition [0, 1) into half-open intervals each of length pi . [So, [0, p1 ),
[p1 , p1 + p2 ), and [p1 + p2 , p1 + p2 + p3 ).] To encode i, take the midpoint of interval of length pi , write it in binary,
and truncate to d− log pi e + 1 bits. The truncation will always lie in the same interval, since truncation subtracts at
most 2−(d− log pi e+1) ≤ 2−(− log pi +1) = pi /2. We can also readily see E`(cSF E (X)) ≤ H(X) + 2.
Suppose X takes values a, b, c with probabilities 0.6, 0.3, 0.1 respectively. The intervals are
[0, 0.6), [0.6, 0.9), [0.9, 1). The mid points are 0.3 = 0.0100112 , 0.75 = 0.112 , and 0.95 = 0.1111001 . . ..
So our code words are 01, 110, and 11110. It is clear this is not really optimal. However it is good for scaling up.
Consider another example where X takes values a, b, c with probabilities 1/2, 1/3, 1/6 respectively. Then the
product distribution is a distribution over 9 outcomes, e.g. ab has probability 1/6.
Compare the interval representations for the X and X 2 codes. In the latter, we would simply partition each of the
three half-open intervals of the former into three to get a total of nine intervals.
In general if we want to encode a sequence of n bits, keep partitioning the intervals in the same way, and return
any binary string in the small interval (e.g., truncating the midpoint to d− log pX n (xn )e + 1).
Note this procedure is linear in n.
Asymmetric Numeral System (ANS)? Coping with distributions that are less uniform; some probabilities very
high. Skew binary representation? See paper.

5 Channel capacity
The communication problem:

msg → transmitter → Channel (noisy) → receiver → msg

Assumptions
1. Messages are random variables uniformly distributed over {1, . . . , M }.

2. Channel has known statistical properties. Input X and output Y , know PY |X . Justification: in real life we can
take measurements.

6
 3. Discrete time, discrete alphabet, memoryless channel. Statistics of PY |X do not change over time. [If X1 , X2
are i.i.d. and input sequentially, then output Y1 , Y2 are i.i.d.]
Example 5.1 (Binary symmetric channel). The binary symmetric channel BSC(p) takes binary input x ∈ {0, 1}
and outputs either x or 1 − x with probability 1 − p and p respectively. 
A (M, n)-block code for the channel (X , PY |X , Y) uses n symbols from X to transmit one of M messages Wi ,
i = 1, . . . , M .
X n (W ) Yn c (Y n )
W → (M, n)-block code −→ PY n |X n −→ decoder → W
The rate of an (M, n) code is R = lognM = number of information bits
number of channel uses = bits/channel use. We also write an (M, n) code
nR
as a (2 , n) code.
A good code should have high rate and good reliability, but these are in conflict.
A rate R is achievable if there exists a sequence of (2nR , n) such that
c 6= Wi | W = Wi ) → 0
max P(W
i

We call this reliable communication.

Definition 5.2 (Operational definition of channel capacity). The capacity C of a channel PY |X is
sup{R : R is achievable}.

Consequently,
1. If R < C, then R is achievable. That is, for any  > 0, there exists an n and a (2nR , n) code with maxi P(W
c 6=
Wi | W = Wi ) < .
2. If R > C, then R is not achievable. That is, there exists c such that for any sequence of (2nR , n) codes,
c 6= Wi | W = Wi ) > c.
lim inf n→∞ P(W

Theorem 5.3 (Shannon’s channel coding theorem).

C = max I(X; Y ).
PX

Properties of C.
1. C ≥ 0.
2. C ≤ min(log|X |, log|Y|). (Just note I(X; Y ) ≤ H(X) ≤ log|X |.) This is equality when the channel is a
deterministic map from X → Y, and |Y| = |X |.
3. Recall I(X; Y ) is concave in PX for fixed PY |X . Computing C is a convex optimization problem.
Example 5.4 (Binary symmetric channel). Consider BSC(p). Note I(X; Y ) = H(Y ) − H(Y | X) = H(Y ) −
H(p) ≤ 1 − H(p) for any distribution on X. If X ∼ Ber(1/2), then Y ∼ Ber(1/2), which gives equality, so this is
the maximizing distribution. C = 1 − H(p). For example if p = 0.1, we have C ≈ 0.6. 
Example 5.5 (Binary erasure channel). Consider the binary erasure channel BEC(p). Input x ∈ {0, 1} and output x
with probability 1 − p or e (erasure) with probability p. Letting E be the indicator for erasure, we have
I(X; Y ) = H(Y ) − H(Y | X) = H(Y ) − H(p)
= H(Y, E) − H(p)
= H(E) + H(Y | E) − H(p)
= H(Y | E)
= pH(Y | E = 1) + (1 − p)H(Y | E = 0)
≤ (1 − p).

7
Taking X ∼ Ber(1/2) gives equality again, so C = 1 − p. This makes sense: if we knew where the erasures were
(proportion p of the time), we can send perfectly. What is surprising that we don’t need to know where the erasures
are. 

Recall the setup.

W ∈{1,...,2nR } X n (W ) Y Yn c (Y n )
W
−→ encoder −→ PYi |Xi −→ decoder −→

A rate R is achievable if there exists a sequence of (2nR , n) codes such that maxi P(W c 6= Wi | W = Wi ) → 0 as
n → ∞. The channel capacity C is a supremum of achievable rates; can be interpreted as the maximum rate at which
information can be transmitted reliably.
We showed that the channel capacities for BSC(p) and BEC(p) are 1 − H(p) nad 1 − p respectively.
Heuristic explanation for channel capacity of BEC(p): First we argue an upper bound on achievable rates R.
Suppose we have extra information: we know the location of the [on average] ≈ pn erasures. Then we could send [on
average] ≈ (1 − p)n bits reliably, i.e. 1 − p bits per channel use. This implies R ≤ 1 − p for achievable R.
Now, how do we actually achieve this without the actual information?
Consider a G ∈ {0, 1}n×(1−p−)n that is full rank (over F2 ). Let X n (W ) := GW ∈ {0, 1}n where W ∈
{0, 1}(1−p−)n . Once we send it through the channel, [on average] proportion ≈ p bits are erased, so after the channel
we have n(1 − p) bits that are not erased. Then we can invert the system since 1 − p −  < 1 − p. Regarding finding
a G, one can show that with i.i.d. Bernoulli entries, the resulting matrix is full rank with high probability. Note that in
this scheme, the probability of error is the probability that the number of erasures is > (p + )n.
Example 5.6 (Noisy typewriter). X = {A, . . . , F }, and for each letter X, the distribution Y | X is equally likely to
be X or X + 1.
I(X; Y ) = H(Y ) − H(Y | X) = H(Y ) − 1 ≤ log(6) − 1 = log 3.
If we choose PX to be uniform on {A, C, E}, then we have equality I(X; Y ) = log 3. 
Preview of Achievability in Channel Coding Theorem: all channels look like the noisy typewriter for n sufficiently
large.
Example 5.7√(Additive Gaussian white noise). Let PY |X ∼ N (X, 1). Then the typical set is a ball centered at X n on
the order of n. Then a simple encoding/decoding scheme is to choose (for the input distribution) a packing of the
space so that these balls are disjoint; decoding just chooses the nearest center. 
We now prove the theorem.
Proof of channel coding theorem (converse/impossibility). We begin with the converse: if R is achievable, then R ≤
C := maxPX I(X; Y ). If R is achievable, there exists a sequence of (2nR , n) code with maxi P(W c (n) 6= Wi |
(n) (n) (n)
W = Wi ) = n with n → 0. This implies P(W
c 6= W ) ≤ n (average is less than maximum).
Note

nR = H(W (n) )
= H(W (n) | W
c (n) ) + I(W (n) ; W
c (n) )

≤ 1 + n nR + I(W (n) ; W
c (n) ) Fano, W
c is estimator of W

≤ 1 + n nR + I(X n ; Y n ) data proc. on W (n) → X n → Y n → W

c (n)
= 1 + n nR + H(Y n ) − H(Y n | X n )
Xn
≤ 1 + n nR + H(Yi ) − H(Y n | X n ) indep. bound (chain rule + cond. reduces entropy)
i=1
Xn n
X
= 1 + n nR + H(Yi ) − H(Yi | X n , Y i−1 )
i=1 i=1
n
X n
X
= 1 + n nR + H(Yi ) − H(Yi | Xi ) memorylessness/Markov
i=1 i=1

8
 n
X
= 1 + n nR + I(Xi ; Yi )
i=1
≤ 1 + n nR + nC.

Divide by n and take n → ∞ (recall n → 0) gives R ≤ C.

Note that the above proof works fine even if we only have the weaker condition P(W c (n) 6= W (n) ) ≤ n (average
error over uniform on W ). The other direction also only requires this weaker assumption.
Also note that the uniformity of W over the possible messages is crucial (appears in the step nR = H(W (n) )).
Note at the end of the above proof, we had n ≥ 1 − C 1 C
R − nR ≈ 1 − R . If R > C, then the probability of error is
bounded from below. This is the weak converse.
There is a strong converse: if R > C, P(Wc 6= W ) ≥ 1 − 2−E(R,C) where E(R, C) > 0 is some function(?)
Suppose R is very close to C. What do the above inequalities tell us?

• The use of Fano’s inequality says we should use the best estimator W
c of W ...

• The use of data processing inequality implies W 7→ X n and Y n → W

c should be close to bijective.

• The next inequality implies the Yi should be close to independent (i.e. the Xi should be close to independence).

• The last inequality implies that the distribution of X n is close to i.i.d. from argmaxPX I(X; Y ). [Capacity-
achieving input distribution (CAID).]

(n)
The set A of jointly typical sequences (X n , Y n ) with respect to a distribution PXY is the set of n-sequences
with empirical entropies -close to true entropy, that is,
(
1
A(n)
 = (xn , y n ) : − log pX n ,Y n (xn , y n ) − H(X, Y ) < ,
n
1
− log pX n (xn ) − H(X) < ,
n
)
1 n
− log pY n (y ) − H(Y ) < 
n

∗
If a rate R is close to C, then the function X n (W ) ought to be “random” (specifically, i.i.d. from PX , the optimizer
of I(X; Y )).
Well-known codes like algebraic codes (Reed-Solomon, Gaulay, PCH) have a lot of structure and redundancy for
the sake of simple decoding. However, this is at odds with the above intuition of a capacity-achieving code.
Today we will prove the achievability direction of the channel coding theorem.

Theorem 5.8 (Joint AEP). Let (X n , Y n ) ∼ PXY

n
.
(n)
1. P((X n , Y n ) ∈ A (X, Y )) → 1.
(n)
2. |A (X, Y )| ≤ 2n(H(X,Y )+) .
e n , Ye n ) ∼ (PX × PY )n , then
3. If (X

e n , Ye n ) ∈ A(n) −n(I(X;Y )−3)

P((X  )≤2 .

The third statement is new. Independence causes the probability of being in the typical set to be vanishing. Note
all pairings of typical X sequences and typical Y sequences are not necessarily jointly typical (in fact, most of them
are not).

9
Proof. The first statement follows by the law of large numbers. The second statement follows by
X
−n(H(X,Y )+)
1≥ p(xn , y n ) ≥ |A(n)
 (X, Y )|2 .
xn ,y n

For the third statement

X
e n , Ye n ) ∈ A(n) ) =
P((X pX n (xn )pY n (y n )

(n)
(xn ,y n )∈A
X
≤ 2−n(H(X)−) 2−nH(Y )−)
(n)
(xn ,y n )∈A
−n(H(X)+H(Y )−2)
= |A(n)
 |2

≤ 2−n(H(X)+H(Y )−H(X,Y )−3) .

Proof of achievability in channel coding theorem. We now prove that all rates R < C are achievable. This is a non-
constructive proof. We will use the probabilistic method: we will show that some object in a finite class C satisfies
property P by exhibiting a distribution over C, drawing an object from this distribution, and show that this object
satisfies P with probability > 0.
In our setting C is a set of (2nR , R) codes and P is “code has small probability of error.”
We will use random coding. Fix some PX and  > 0 and R. Generate a (2nR , n) code at random according to PX .
The codebook is nR
C = [Xi (w)]i,w ∈ R2 ×n .
The wth row of C is the codeword for the wth message. Each letter of each code word is generated i.i.d. from PX , so
nR
2Y n
Y
P(C) = PX (Xi (w)).
w=1 i=1

We have decided the encoding scheme. For decoding, we will use typical set decoding. The receiver declares that
W
c was sent if both of the following happen.
(n)
c ), Y n ) ∈ A (X, Y ), that is, the received message Y n is jointly typical with code word X n (W
1. (X n (W c ).

c also satisfies (X n (k), Y n ) ∈ A(n)

2. No other index k 6= W  (X, Y ).

Otherwise, the decoder declares an error.

We now compute the expected probability of error for this scheme, averaged over codebooks C drawn from the
above distribution.
The probability of error is
c 6= i | X n = X n (i)).
λi (C) = P(W
This probability is over the randomness of the channel, but the codebook fixed.
The average [over all messages] probability of error for a fixed code C is
nR
2
1 X
Pe(n) (C) = EλW (C) = λw (C)
2nR w=1

[This is a function of C, can be thought of as a conditional probability.]

10
 The average over all codes is
X
Perror = P(C)P(n) (C)
C
nR
2
X 1 X
= P(C) λw (C)
2nR w=1
C
nR
2
1 XX
= P(C)λw (C)
2nR w=1
C
X
= P(C)λ1 (C) rows of C are exchangeable
C
= P(error | W = 1). error prob. averaged over all codes
(n)
Define error events Ei = {(X n (i), Y n ) ∈ A (X, Y )} for i = 1, . . . , 2nR . Continuing from above,

P(error | W = 1) = P(E1c ∪ E2 ∪ · · · ∪ E2nR | W = 1)

nR
2
X
≤ P(E1c | W = 1) + P(Ei | W = 1)
i=2
nR
2
X
n n
= P((X , Y ) ∈
/ A(n)
 ) + e n , Ye n ) ∈ A(n) )
P((X 
i=2
nR −n(I(X;Y )−3)
≤+2 2 for n sufficiently large

≤ 2 for n sufficiently large, if R < I(X; Y ) − 3

For i 6= 1, Y n is independent of X n (i) because Y n came from Xn (1).

So, the average [over codebooks and messages] probability of error is vanishing in n, so there exists some sequence
of codebooks with vanishing probability of error [averaged over messages].
In conclusion, for any R < C and  > 0 there exists a (2nR , n) code with average [over messages, not codebooks]
probability of error < .
“Almost every code is a good code, except the ones we construct.” However, these codes are virtually impossible
to decode. [Codebook is of exponential size, decoding needs to check all codewords.]

Let X n be i.i.d. Bern(1/2). Suppose Y n is obtained by passing X n through BSC(α). [That is, Yi is equal to Xi
with probability 1 − α, and is flipped with probability α.] For any b : {0, 1}n → {0, 1} (one-bit function), is it true
that I(b(X n ); Y n ) ≤ 1 − H(α) = I(X1 ; Y1 )? This is the “most informative function conjecture.”
In the last few lectures we proved the channel coding theorem, which stated that the channel capacity is
maxPX I(X; Y ).
• Converse: If R is achievable, then R < C. This holds using either definition of achievability (involving maximal
c 6= Wi | W = Wi ) or average probability of error P (W
probability of error maxi P (W c 6= W )).

• Achievability: There exist (2nR , n) codes with P (W

c 6= W ) → 0 as n → ∞ provided R < C.

We just need to tidy up the achievability result by proving the version with maximum probability of error. This is an
application of Markov’s inequality. Note
nR
2
X
c 6= W ) =
P (W c 6= Wi | W = Wi )P (W = Wi )
P (W
i=1

11
Since messages are uniformly distributed,
c 6 W)
c 6= Wi | W = Wi ) ≥ λ}/2nR ≤ P (W =
#{i : P (W .
λ
c 6= W ) gives
Taking λ = 2P (W
c 6= W )} ≤ 2nR /2.
c 6= Wi | W = Wi ) ≥ 2P (W
#{i : P (W

If we throw away these bad messages (left-hand side), then the new rate is

log(#codewords) log(2nR /2) 1

= =R− .
n n n
In the new code, all the codewords have probability of error ≤ 2P (W
c 6= W ) by definition, so

c0 6= W0i | W0 = W0i ) ≤ 2P (W
max P (W c 6= W ) → 0.
i

What is the rate of information sent from eye to brain? Measure signal X entering eye, signal Y entering brain,
estimate I(X; Y ), gives upper bound on rate. [Estimating I(X; Y ) needs some shift to align due to delay, quantize
time, etc.]
Suppose that we are the encoder that sends Xi through a channel, which sends Yi to a decoder. What if we get
feedback: we see Yi (what the decoder receives)? We argued before that in the binary erasure channel, the capacity
with feedback is the same. Is this true in general? [We know trivially that capacity with feedback must be at least as
large as the capacity without feedback: just ignore the feedback.]
More explicitly, the encoder sends Xi , which can depend on W , as well as X i−1 and Y i−1 .

Theorem 5.9. The feedback does not improve the channel capacity. However, it can simplify the encoding scheme. It
can also get us to capacity much more quickly. That is, Pe (best code) ≈ 2−nE without feedback, but with feedback
nE 0
Pe (best code) ≈ 2−2 .

Proof. We already know CF B ≥ C so it suffices to prove the other direction.

nR = H(W ) messages are uniformly distributed

≤ I(W ; W
c ) + nRn + 1 Fano

≤ I(W ; Y n ) + nRn + 1 data-processing, W → Y n → W

c

= H(Y n ) − H(Y n | W ) + nRn + 1

X
≤ (H(Yi ) − H(Yi | W, Y i−1 )) + nRn + 1 independence bound, chain rule
i

X
= (H(Yi ) − H(Yi | W, Y i−1 , Xi )) + nRn + 1 Xi is function of (W, Y i−1 )
i

X
= (H(Yi ) − H(Yi | Xi )) + nRn + 1 Yi is conditionally independent of all past things given Xi
i

X
= I(Xi ; Yi ) + nRn + 1
i
≤ n max I(X; Y ) + nRn + 1.
PX

12
Thus R ≤ C.
Remark: In the channel coding theorem, we had

I(X n ; Y n ) = H(Y n ) − H(Y n | X n ) + nn

X
≤ H(Yi ) − H(Y n | X n ) + nn .
i

n n
P
We then used H(Y | X ) = i H(Yi | Xi ) because the Yi were conditionally independent given the corresponding
Xi . This is no longer the case with feedback.
Preview of another problem (to be continued later):
Consider the following compression example. [No channel.] Suppose we have X n and Y n are correlated, and we
want to encode each separately, and then a decoder takes both. (If the first encoder sents nRX bits and the second
sends nRY , then the rate is RX + RY .) How much worse is this than encoding (X n , Y n ) together? Chapter 15.4.
We say RX and RY are achievable if there exists a sequence of functions f : X n → [2nRX ] and g : Y n → [2nRY ]
and φ : [2nRX ] × [2nRY ] → X n × Y n such that

P (φ(f (X n ), g(Y n )) 6= (X n , Y n )) → 0

as n → ∞. (X b n , Yb n ) := φ(f (X n ), g(Y n )). The achievable rate region is the closure of achievable rates.
Recall that if RX ≥ H(X) then we can send the information losslessly. So the achievable rate region definitely
contains [RX , ∞) × [RY , ∞). Considering the special case where we can encode everything together, we see that the
achievable rate region must lie in the region {RX + RY ≥ H(X, Y )}.
The answer: any rates satisfying RX ≥ H(X | Y ), RY ≥ H(Y | X), and RX + RY ≥ H(X, Y ).

In channel coding, high rate is desirable, but hard because of the channel. In compression, low rate is desirable
(communicate using fewer bits) but hard. That is why achievable rates in channel coding has an upper bound, while
in compression there is a lower bound.
We will discuss Problem 4 on the midterm.
(X n , Y n ) are drawn i.i.d. from some distribution. Y n is encoded into f (Y n ) ∈ {0, 1}nR . The decoder receives
both f (Y n ) and X n , and gives an estimate Yb n .
(n)
The probability of error is Pe = P (b y n (X n , f (Y n ) 6= Y n ). We say R is achievable if there exists a sequence of
nR (n)
(2 , n) codes with Pe → 0.
First, we prove that if R is achievable, then R ≥ H(Y | X).

nR ≥ H(f (Y n ))
≥ H(f (Y n ) | X n ) conditioning reduces entropy
n n n n n n
= H(Y , f (Y ) | X ) − H(Y | f (Y ), X ) chain rule
n n n
≥ H(Y , f (Y ) | X ) − (nPe(n) log|Y| + 1)
n n n n n
= H(Y | X ) + H(f (Y ) | Y , X ) − nn
= nH(Y | X) + 0 − nn .
(n) (n)
Next, we prove a lemma about typical sets. We define A (Y | xn ) = {y n : (xn , y n ) ∈ A (X, Y )}. We prove
(n)
|A (Y | xn )| ≤ 2nH(Y |X)+2) .

2−n(H(X)−) ≥ p(xn )
X
≥ p(xn , y n )
(n)
y n :(xn ,y n )∈A (X,Y )
X
≥ 2−n(H(X,Y )+)
(n)
y n :(xn ,y n )∈A (X,Y )

= |A(n)
 (Y | x )|2−n(H(X,Y )+)
n

13
6 Differential entropy
R
The differentiable entropy of a continuous random variable with density f is h(X) := − f (x) log f (x) dx =
−E log f (X).
If X is discrete and Y is continuous, then I(X; Y ) = H(X) − H(X | Y ) = h(Y ) − h(Y | X).
Ra
Example 6.1 (Uniform). If X is uniform on [0, a], then h(X) = − 0 a1 log a1 dx = log a. In particular, h(X) can be
negative! 
P∞
Why can entropy be negative? Consider approximating the integral by − i=−∞ N1 f (i/N ) log f (i/N ). Consider
[X]N , a discretized version of f taking values 1/N with probabilities f (i/N )/N . Then the above approximation to
the integral is H([X]N ) − log N = H([X]N ) − H([U ]N ), where [U ]N is the discretization of a Unif(0, 1) random
variable. This is the “differential” in the name: it is in some sense the difference in discrete entropy of quantized
versions of X and U .
The relative entropy is D(P kQ) = p(x) log dp dp
R
dq (x) dx = EP log dq (X). Note that we can rewrite this as
R dp dp
dq (x) log dq (x) dq(x). So, differential entropy can be written as −D(P k dx) where “dx” denotes the Lebesgue
measure.
2 2
Example 6.2 (Gaussian). Let f (x) = √ 1
2πσ 2
e−x /2σ .
Z
1
h(X) = f (x) log dx
f (x)
x2
Z
1
= log 2πσ 2 + f (x) log(e) 2 dx
2 2σ
1 1
= log 2πσ 2 + log e
2 2
1 2
= log 2πeσ
2

R
Joint density is h(X1 , . . . , Xn ) = − f log f where f is the joint density.
Let f (x) = (2π)−n/2 |K|−1/2 exp − 12 (x − µ)> K −1 (x − µ) .


Example 6.3 (Multivariate Gaussian).
Z
1
h(X) = f log
f
1 1 1
= log(2π)n |K| + log(e) + log(e)E(X − µ)K −1 (X − µ)
2 2 2
1 n
= log(2π)n |K| + log e trace trick
2 2
1
= log(2πe)n |K|.
2
Note that µ does not appear. This is because entropy is invariant to shifting. 
R
Conditional differential entropy is h(Y | X) = − fX,Y (x, y) log fY |X (y | x) dy dx = −E log fY |X (Y | X).
Chain rule: h(Y, X) = h(X) + h(Y | X).
Relative entropy: if supp(f ) ⊂ supp(g), D(f kg) = f log fg ≥ 0 by Jensen’s inequality.
R

Mutual information is I(X; Y ) = D(fXY kfX fY ) = h(X) − h(X | Y ) ≥ 0. From this we see conditioning still
decreases entropy. Pn Pn
We still have h(X1 , . . . , Xn ) = i=1 h(Xi | X1 , . . . , Xi−1 ) ≤ i=1 h(Xi ).
Also, h(X + c) = h(X) and h(aX) = h(X) + log|a|. [Recall if Y = aX then fY (y) = fX (y/a)/|a|.] More
generally, for a matrix A, h(AX) = h(X) + log|A|.
Aside:

14
Proposition 6.4 (Entropy power inequality). Let X and Y be independent random vectors on Rn .

22h(X+Y )/n ≥ 22h(X)/n + 22h(Y )/n .

Suppose X is uniform on some set A, so fX (x) = 1/ vol(A)1A . Then h(X) = log vol(A). Similarly if Y is
uniform on another set B, then h(Y ) = log vol(B). Then, the entropy power inequality implies

22h(X+Y )/n ≥ vol(A)2/n + vol(B)2/n .

The Brunn-Minkowski inequality states vol(A + B)1/n ≥ vol(A)1/n + vol(B)1/n , where A + B is the Minkowski
sum {a + b : a ∈ A, b ∈ B}. If we take 22h(X+Y )/n ≈ vol(A + B)2/n (note this is not true, due to the convoluting),
then we see that the entropy power inequality suggests a stronger inequality than the Brunn-Minkowski inequality.

Rough volume argument for strong converse of channel coding: if R > C, The number of typical y n is ≈ 2nH(Y ) .
For each xn , number of conditionally typical y n is 2nH(Y |X) . If these sets are disjoint, the number of sets in y n is
about 2nI(X;Y ) . If we have R > C then we have overlap.
If X is discrete and Y is continuous, no notion of joint entropy. However, we can talk about mutual information.

I(X; Y ) = H(X) − H(X | Y ) = h(Y ) − h(Y | X).

For general random variables, we have another equivalent definition of mutual information.

I(X; Y ) = sup I([X]P ; [Y ]P ),

P

where the supremum is over all partitions. Note that this is essentially the definition of Lebesgue integration from
approximation by simple functions. For continuous Y , we recover the earlier definition.

I(X; Y ) = sup H([Y ]N )−H([Y ]N | [X]N ) ≈ h(Y )+H([U ]N )−h(Y | [X]N )−H([U ]N ) → h(Y )−h(Y | X).
N

The fact that mutual information can be defined between discrete and continuous random variables is good in
practice. Consider a codeword X n ∈ [2nR ] being sent through a channel; such channels usually produce continuous
output.
Last time we showed for X ∼ N (µ, K), we have h(X) = 21 log(2πe)n |K|.

Theorem 6.5. For any random variable Y with covariance K,

1
h(Y ) ≤ h(X) = log[(2πe)n |K|].
2
Moreover, equality holds if and only if Y is Gaussian.

So, the Gaussian distribution maximizes entropy under a second moment constraint.
Aside: Note that for the discrete case, uniform distribution over finite alphabet maximizes entropy without moment
conditions. It does not usually make sense to impose moment conditions since we usually do not care about the values
of X, unlike the continuous case. For nonnegative integers with a mean constraint, geometric distribution maximizes
entropy.
> −1
Proof. Let φ(x) = (2π)−n/2 |K|−1/2 e−x K x/2 be the Gaussian density and f arbitrary. [WLOG both f and φ
have zero mean.] Then − loge φ = 12 log[(2π)n |K|] + 12 x> K −1 x.

15
 0 ≤ De (f kφ)
Z
f
= f loge
φ
Z
= − f loge φ − he (f )

= EX∼f [− loge φ(X)] − he (f )

1 1
= log[(2π)n |K|] + EX∼f X > K −1 X −he (f )
2 2| {z }
=n
1 1
= log[(2π)n |K|] + loge en − he (f )
2 2
1
= loge [(2πe)n |K|] − he (f )
2
= he (φ) − he (f ).

7 Gaussian channel
The Gaussian channel takes input X and outputs Y = X + Z where Z ∼ N (0, σ 2 ) is independent of X.
We have supPX I(X; Y ) = ∞ because we do not have constraints on X. We could spread the distribution of X
so widely such that the Gaussian Z does not perturb by much, and Y can easily be decoded.
We consider instead supPX :EX 2 ≤P I(X; Y ). [WLOG we assume X is zero mean; shifting does not change any-
thing.] We have

I(X; Y ) = h(Y ) − h(Y | X) = h(Y ) − h(Z)

1
= h(Y ) − log 2πeσ 2
2
1 1
≤ log 2πe(σ 2 + P ) − log 2πeσ 2
2   2
1 P
= log 1 + 2 .
2 σ

Equality is attained by X ∼ N (0, P ), so C = 12 log 1 + σP2 . The ratio p/σ 2 is the signal-to-noise (SNR).

For the Gaussian channel, a (2nR , n, P ) code c is a map from w ∈ [2nR ] and outputs X n (w) ∈ Rn such that
kX (w)k2 ≤ nP . [The idea is that we have limited energy; we cannot amplify arbitrarily large.]
n

nR ≤ H(W )
≤ I(X n ; Y n ) + nPe(n) R + 1 data proc., Fano
Xn
≤ I(Xi ; Yi ) + 1 + nPe(n) R
i=1
n
1X
R≤ I(Xi ; Yi ) + n
n i=1
n 2
We cannot take the supremum over PX because we have the constraint
1
PnkX (w)k ≤ nP . WeR use the fact that for
fixed PY |X , the map PX 7→ I(X; Y ) is concave. We define PX = n i=1 PXi . Then PY = PY |X dPX . Then
n
1X
I(Xi ; Yi ) ≤ I(X; Y ) ≤ max2 I(X; Y )
n i=1 PX :EX ≤P

16
 Pn
because EX 2 = n1 i=1 EXi2 ≤ P . With a little more work, the constraint kX n (W )k2 ≤ nP could be relaxed to
hold on average over messages W .
Let X1 , X2 , . . . be i.i.d. with density f , mean zero, and second moment equal to 1. The central limit theorem
states
n
1 X d
Sn := √ Xi → N (0, 1).
n i=1

Note that Sn all have the same second moment 1. We suspect h(Sn ) is increasing, since the limiting distribution is
Gaussian.
Recall the entropy power inequality, which implies
√ 1 2h(X1 )
22h((X1 +X2 )/ 2)
= 22(h(X1 +X2 )−log 2) ≥ (2 + 22h(X2 ) ) = 22h(X1 ) .
2
This argument shows h(S2k ) ≥ h(S2` ) for k ≥ `.
But does h(Sn ) increase monotonically? This was an open problem since Shannon, and solved in 2004.
Note that h(Sm ) ≥ h(Sn ) is equivalent to D(Sm kN (0, 1)) ≥ D(Sn kN (0, 1)). [Convergence in entropy implies
convergence in distribution. See Pinsker?] So a strong central limit theorem holds.

8 Entropy power inequality

Theorem 8.1.
22h(X+Y ) ≥ 22h(X) + 22h(Y ) .

• 1948: proposed by Shannon (proof was wrong)

• 1959: Stam (semigroup / Fisher information)
• 1965: Blachman (same technique)
• 1991: Carlen, Soffer (same technique)
• ?: Dembo, Cover
√ √
Let U = λX and V = 1 − λY .

2h(U +V ) ≥ 22h(U ) + 22h(V )

√ √ √ 1
22h( λX+ 1−λY )
≥ λ22h(X) + (1 − λ)22h(Y ) h( λX) = h(X) + log λ
2
≥ 22λh(X)+2(1−λ)h(Y ) Jensen
√ √
h( λX + 1 − λY ) ≥ λh(X) + (1 − λ)h(Y ).

This last inequality is Lieb’s inequality, and we have shown it is a consequence of the entropy power inequality. This
2h(U )
is actually equivalent to the entropy power inequality: choose λ = 22h(U2 ) +22h(V ) .1 The latter form is more convenient
for proving, but the original form is more convenient for applications.
Without loss of generality, we may assume the densities of X and Y do not vanish. [Else convolve with a Gaussian
with low variance; does not change much.]
22h(U )/n
1 Suppose we want to prove the n-dimensional EPI 22h(U +V )/n ≥ 22h(U )/n + 22h(V )/n . Let λ = .
22h(U )/n +22h(V )/n
√ √
h(U + V ) = h( λX + 1 − λY )
≥ λh(X) + (1 − λ)h(Y )
 n   n 
= λ h(U ) − log λ + (1 − λ) h(Y ) − log λ
2 2
n  
= log 22h(U )/n + 22h(V )/n .
2

17
 We will be using results from optimal transport theory (but we will derive things from scratch). This is an adapta-
tion of Olivier Rioul’s proof (2016).
Let FX and FY be the cdfs of X and Y respectively. If X ∗ ∼ N (0, 1), then Φ(x∗ ) is uniform on [0, 1], and
−1 −1
FX (Φ(X ∗ )) is distributed as X. So let TX = FX ◦ Φ so that TX (X ∗ ) is distributed as X. Note that TX is an
0
increasing function. [We assumed the densities are nonvanishing so the CDFs are strictly increasing.] Thus TX > 0.
Define TY similarly.
d
Let X ∗ , Y ∗ ∼ N (0, 1) be i.i.d. Then (TX (X ∗ ), TY (Y ∗ )) = (X, Y ) in distribution.
e Ye ∼ N (0, 1) be i.i.d. Then we can write
Let X,
√ √
X ∗ = λX e − 1 − λYe
√ √
Y ∗ = 1 − λX e + λYe

[This is a unitary transformation; Gaussian distribution is rotation invariant.]

Consider √ √
x) = λTX (x∗ ) + 1 − λTY (y ∗ ).
Θye(e
Then √ √
d
ΘYe (X)
e = λX + 1 − λY.
We also have
d 0
Θye(e
x) = λTX (x∗ ) + (1 − λ)TY0 (y ∗ ).
de
x
√ √
Let f be the density of λX + 1 − λY . By the change of variables formula,

fye(e x))Θ0ye(e
x) = f (Θye(e x)

is a density.

√ √ 1
h( λX + 1 − λY ) = E log √ √
f ( λX + 1 − λY )
1
= E log
f (Θ e (X))
Y
e
Θ0ye(e
x)
= E log
fYe (e
x)

e + E log φ(X) + E log Θ0 (X)

e
= h(X) Y
e
fYe (X)
e
e
" #
φ( X)
e
= h(X)
e + E e E e log
Y X | Ye + E log Θ0Ye (X)
e
f e (X)
Y
e
e + E e D(gkf e ) + E log Θ0 (X)
= h(X) e
Y Y Y
e
e + E log Θ0 (X)
≥ h(X) e
Y
e
0 e
≥ h(X)
e + λE log TX (X) + (1 − λ)E log TY0 (Ye ) concavity of logarithm
0 e
= λ(h(X)
e + E log TX (X)) + (1 − λ)(h(Ye ) + E log TY0 (Ye ))
= λh(X) + (1 − λ)h(Y ).

0 e
The last step is due to the change of variables φ(e
x) = fX (TX (e
x))TX (X),
0 e
0 e TX (X) 1 1
h(X)
e + E log TX (X) = E log = E log = E log = h(X).
φ(X)
e fX (TX (e
x )) f X (X)

18
 √
To relax the condition that the densities of X and Y are non-vanishing, we use an approximation h(X + Z) →
h(X) as  → 0.
We proved the entropy power inequality in dimension 1. In higher dimensions it takes a similar form in that the
constants do not degrade; it is dimension free.

Theorem 8.2 (Conditional EPI). If X and Y are conditionally independent given U .

22h(X+Y |U ) ≥ 22h(X|U ) + 22h(Y |U ) .

Proof. By the EPI,

 
2h(X + Y | U = u) ≥ log 22h(X|U =u) + 22h(Y |U =u)
 
2h(X + Y | U ) ≥ log 22h(X|U ) + 22h(Y |U ) concavity of log-sum-exp.

Theorem 8.3 (EPI in n dimensions). If X n and Y n are random vectors in Rn ,

n
2
+Y n ) 2 n 2 n
2 n h(X ≥ 2 n h(X )
+ 2 n h(Y )
.

Proof.

h(X n + Y n ) = h(Xn + Yn ) + h(X n−1 + Y n−1 | Xn + Yn )

 2 n−1 2 n−1

2h(X n−1 + Y n−1 | Xn , Yn ) ≥ (n − 1) log 2 n−1 h(X |Xn ,Yn ) + 2 n−1 h(Y |Xn ,Yn )

 2 n−1 2 n−1

2h(X n−1 + Y n−1 | Xn + Yn ) ≥ (n − 1) log 2 n−1 h(X |Xn ) + 2 n−1 h(Y |Yn )

 
2h(Xn + Yn ) ≥ log 22h(Xn ) + 22h(Yn )
2  2 n 2 n

h(X n + Y n ) ≥ log 2 n h(X ) + 2 n h(Y ) concavity of log-sum-exp
n

Consider a adversarial channel who sees the distribution of X, chooses distribution Z and outputs Y = X + Z.
We want to find the capacity
sup inf I(X; X + Z)
PX PZ

subject to EX 2 ≤ σX
2
and EZ 2 ≤ σZ
2
.

I(X; X + Z) = h(X + Z) − h(Z)

≥ h(X + Z) − h(Z ∗ ) Z ∗ ∼ N (0, σZ
2
)
≥ h(X ∗ + Z ∗ ) − h(Z ∗ ) EPI
2
 
1 σX
= log 1 + 2
2 σZ

sup inf h(X + Z) − h(Z) ≤ sup h(X + Z ∗ ) − h(Z ∗ )

PX PZ PX
2
 
1 σX
= log 1 + 2 Gaussian channel
2 σZ

19
 Thus, we have the Gaussian channel saddle point property:
2
 
1 σX
log 1 + 2 = sup inf I(X; X + Z) = inf sup I(X; X + Z)
2 σZ PX PZ PZ PX

In other words,
I(X; X + Z ∗ ) ≤ I(X; X + Z) ≤ I(X ∗ ; X ∗ + Z).
So non-Gaussian channels have higher capacity.
Getting Gaussian codes to work for any channel: perform unitary transformation before sending to channel, and
then perform inverse on output. CLT?

9 Rate distortion theory

Lossy compression. Encoder observes X n , sends nR bits to decoder, who then outputs estimate X
b n.
n n
If R > H(X), then X = X is possible with high probability.
b
If R < H(X), then what can we say? Trade-off between dimension reduction (rate, number of bits in the repre-
sentation) and fidelity of the reconstruction.
To measure fidelity, we need some distortion function (measure) d : X × Xb → R+ . For convenience we
b)2 is
b) < ∞. For example, (x − x
sometimes consider bounded distortion functions that satisfy dmax = maxx,bx d(x, x
unbounded. Most results generalize to the unbounded case.
Some distortion functions are
• Hamming distortion d(x, x
b) = 1[x 6= x
b], used in the case where X = Xb (or some subset relationship). Note
Ed(X, X) = P (X 6= X).
b b

• Squared error / quadratic loss d(x, x b) = (x − x b)2 . Again, this is unbounded on R2 .

Pn
We can extend distortion functions to sequences by d(xn , x bn ) = n1 i=1 d(xi , x bi ), the average per-symbol dis-
tortion. Other possibilities that we will not consider include d(xn , x bn ) = maxi d(xi , xbi ).
We have a encoding function fn : X n → [2nR ] and a decoding function gn : [2nR ] → Xbn .
The central quantity is the expected distortion
X
Ed(X n , gn (fn (X n ))) = p(xn )d(xn , gn (fn (xn ))).
xn
| {z }
bn
X

A rate distortion pair (R, D) is achievable if there exists a sequence of (2nR , n) codes (fn , gn ) such that

lim Ed(X n , gn (fn (X n ))) ≤ D.

n→∞

Note that if (R, D) is achievable, then (R, D0 ) and (R0 , D) are also achievable if D0 ≥ D and R0 ≥ R.
The achievable rate distortion region is also convex: if you have two codes, you can flip a coin to choose which
code to use for a particular block. The rate and distortion will just be the convex combinations.
The point where the boundary of the achievable region hits the D = 0 axis is (H(X), 0). Where the boundary
hits R = 0 is (0, minxb Ed(X, x b)) (output the least offending guess on average). If dmax exists, it is larger than this
minimum.
Note that the achievability definition can be restated  > 0 such that P (d(X n , gn (fn (X n )) > D + ) → 0 for all
 > 0. (???)
The rate distortion function is R(D) = inf{R : (R, D) achievable}, the lower boundary of the achievable rate
distortion region.

Theorem 9.1. For Xi ∼ PX i.i.d., |X |, |Xb| < ∞, and distortion bounded by dmax ,

R(D) = min I(X; X).

b
PX|X
c :Ed(X,X)≤D
b

20
 In channel coding, the channel is fixed and we control the distribution over the input. In this setting, the input PX
is given, and we control the encoding/decoding scheme that gives the output.
Recall PX|X
b 7→ I(X; X)b is convex for fixed PX , so this is a convex optimization problem. [Note that the
b = P p(x)p(b
constraint on the expected distortion is a linear constraint: Ed(X, X) x | x)d(x, xb).]
x,b
x
In channel coding, if we did not choose too many inputs, their typical images under the channel would hopefully
be disjoint. This is a packing argument. We could use a volume argument to estimate how many inputs we can send.
In our setting, we have some subset of Xbn of size 2nR , and we consider the “preimage” of inputs in X n that are
within distortion D of these outputs X(i).
b We want enough in the output space so that their “preimages” cover X n .
This is in some sense a dual of channel coding. Note that R controls the number of “preimages,” and with lower R, it
becomes harder to cover. D controls the size of each “preimage” and lower D makes it harder to cover.
Example 9.2. Let X ∼ Ber(p) with p ≤ 1/2. Let ⊕ be the XOR operation, and consider the Hamming distortion.
Lower bounding I(X, X) b ≤ D gives
b subject to Ed(X, X)

b = H(X) − H(X | X)
I(X; X) b
≥ H(p) − H(X ⊕ X
b | X)
b
≥ H(p) − H(X ⊕ X)
b
≥ H(p) − H(D).

H(p) − H(D) is the mutual information corresponding to the BSC with transition probability D taking some input
e and having output distribution Y following (p, 1 − p). Indeed, I(X; Y ) = H(Y ) − H(Y | X) = H(p) − H(D).
X
How do we use this information to achieve this rate in our original problem?
Put X b through a BSC(D) channel so that X has distribution (p, 1 − p). Using Bayes’s Rule gives P (b
x = 0) =
1−p−D
1−2D .
So, (
H(p) − H(D) D ≤ p
R(D) =
0 D>p
If D ≥ p, we can simply output 0 all the time, and then the expected distortion is p. 

Example 9.3. Consider a Gaussian randomqvariable X ∼ N (0, σ 2 ). How would we do a one-bit quantization? Let
2 π−2 2
b1[X ≥ 0] − x
f (X) := x b1[X < 0]. If x
b= π σ, then E(X − f (X))2 = π σ ≈ 0.36σ 2 .
We want to find R(D) = minP c b 2 ≤D
:E(X−X) I(X; X).
b
X|X

b = h(X) − h(X | X)
I(X; X) b
= h(X) − h(X − X
b | X)
b
≥ h(X) − h(X − X)
b
1 1
≥ log(2πeσ 2 ) − log(2πeD)
2 2
1 σ2
= log .
2 D
We have shown a lower bound. Is equality attained?
Recall the theorem about the Gaussian channel: if Y = X + Z where X ∼ N (0, P ) and Z ∼ N (0, N ), then
I(X; Y ) = 21 log NN +P
.
Consider a Gaussian channel X = X b + Z where X b ∼ N (0, σ 2 − D) and Z ∼ N (0, D), then X ∼ N (0, σ 2 ).
2 2
Then I(X; X)b = 1 log σ . So, R(D) = 1 log σ .
2 D 2 D
Now compare with our one-bit quantizer. With the same second fidelity constraint D = 0.36σ 2 , the optimal rate
is R(0.36σ 2 ) = 12 log 0.36
1
≈ 0.737. This is a significant improvement over the rate 1 of the one-bit quantizer. It is
suboptimal to quantize on a symbol-by-symbol basis; we gain by quantizing on blocks. 

21
 Suppose X ∼ N (0, 1) is the input to a neural network which outputs X. b 2 = 1/2.
b Suppose we have E(X − X)
The information flow through any layer is ≥ R(1/2) = 1/2.
We now prove the theorem.
Proof of achievability. Fix PX|X
b
b ≤ D. We want to show that there exists a sequence of (2nR , n)
such that Ed(X, X)
b and achieve E[d(X n , gn (fn (X n ))) → D as n → ∞.
codes that have rate R ≈ I(X; X)
We define a distortion-typical set.

(n)
n 1
bn ) : − log p( xn , x
Ad, := (xn , x bn ) − H(X, X)
b < ,
n
1
− log p(xn ) − h(X) < ,
n
1
− log p(b xn ) − h(X)
b < ,
n
o
|d(xn , x
bn ) − Ed(X, X)|
b <

= A(n) n
bn ) : |d(xn , x
 (X, X) ∩ {(x , x
b bn ) − Ed(X, X)|
b < }
⊆ A(n)
 (X, X).
b

()
1. We have P (Ad,n ) → 1 since the two sets in the intersection have probability tending to 1, both by the weak law
of large numbers.
(n)
2. p(b xn | xn )2−n(I(X;X)+3) for all (xn , x
xn ) ≥ p(b bn ) ∈ Ad, .
b

xn , xn )
p(b
xn | xn ) = p(b
p(b xn ) xn )2−n(H(X,X)−H(X)−H(X)+3) = p(b
≥ p(b xn )2n(I(X;X)+3)
b b b
p(xn )p(bxn )

3. If 0 ≤ x, y ≤ 1 and n ≥ 0, then (1 − xy)n ≤ 1 − x + e−yn . To see this, note x 7→ (1 − xy)n is convex and
nonincreasing for fixed y. Also, x 7→ 1 − x + e−yn is linear and nonincreasing for fixed y. Also, 1 − y ≤ e−y .
[See Lemma 10.5.3.]
We describe the random code.
1. Generate 2nR sequences X
b n (i), i = 1, . . . , 2nR i.i.d. from P b .
X

b n (i)) ∈ A(n) if possible.

2. Typical set encoding: for each X n , select i such that (xn , X d,

• If there are multiple such i, break ties arbitrarily.

• If no such i exists, then send i = 1. This happens with small probability Pe .

Then,

Ed(X n , X
b n (i)) ≤ (1 − Pe )(D + ) + Pe dmax b) < ∞
dmax can be relaxed to min Ed(X, x
x
b
≤ D +  + Pe dmax .

It now suffices to show Pe → 0 provided R > I(X; X).

b

(n)
X
P ((xn , X
b n) ∈
/ Ad, ) = 1 − xn )1A(n) (xn , x
p(b bn )
d,
bn
x
" #2nR
(n)
X
P (@i : (xn , X
b n (i)) ∈ Ad, ) = 1− xn )1A(n) (xn , x
p(b bn ) independence
d,
bn
x

22
 " #2nR
X X
Pe = p(xn ) 1 − xn )1A(n) (xn , x
p(b bn )
d,
xn bn
x
" #2nR
X X
n n n −n(I(X;X)+3) n n
≤ p(x ) 1 − x | x )2
p(b 1A(n) (x , x
b )
b
d,
xn bn
x
 2nR
X  X 
−n(I(X;X)+3)
= p(xn )1 − 2 p(b
x n
| x n
)1 n
(n) (x , x
n 
)
 b
Ad,
| {z } b 
xn
 
y bn
x
| {z }
x
" #
−2−n(I(X;X)+) 2nR
X X
n n n n n
c
≤ p(x ) 1 − x | x )1A(n) (x , x
p(b b )+e inequality in “3” above
d,
xn bn
x
(n) n(R−(I(X;X)+3))
= P ((X n , X / Ad, ) + e−2
b n) ∈
c

→0+0 R > I(X; X)

b + 3

Recall the rate distortion setup. We give X n (drawn i.i.d. from some PX ) to an encoder, who then sends nR bits
to a decoder, who then outputs X b n which hopefully has distortion Ed(X n , X
b n ) ≤ D.
We want to characterize R(D) = inf{R : (R, D) achievable}, the lowest possible rate at which it is possible to
obtain [asymptotically] expected distortion ≤ D.
It turns out that
R(D) = min I(X; X).
b
PX|X
c :Ed(X,X)≤D
b

Last time, we proved achievability: if R > R(D), then there exists a sequence of (2nR , n) codes with
limn→∞ Ed(X n , X
b n ) ≤ D.
Sketch:

1. Fix PX|X
b such that EPX PX|X b ≤ D.
d(X, X)
c

2. We picked 2nR sequences X

b n (1), . . . , X
b n (2nR ). For each, there is a distortion ball {X n : d(X n , X(i))
b ≤ D}.

3. If R > R(D), then we have chosen enough X b n (i) so that the set of all corresponding distortion balls is so large
that the probability of error is small...

We now turn to proving the converse. First, we need the following lemma.

Lemma 9.4. D 7→ minP c :Ed(X,X)≤D

b I(X; X)
b is convex.
X|X

We proved convexity of the operational definition of R(D) last time by showing the set of achievable pairs (R, D) is
convex. However, this lemma asserts convexity of the thing that we have yet to prove is equal to R(D).
(0) (1)
Proof. Let PX|X
b achieve R(D0 ), and let PX|X
b achieve R(D1 ).
(λ) (0) (1)
Define PX|X
b = λPX|X
b + λPX|X
b .
Since P b 7→ I(X; X) is convex for fixed PX , we have
X|X
b

b ≤ λI (0) (X; X)
IP (λ) (X; X) b + λI (1) (X; X)
b = λR(D0 ) + λR(D1 ).
P P
X|X
c X|X
c X|X
c

EP (λ) d(X, X)
b = λE (0) d(X, X) b ≤ λD0 + λD1 .
b + λE (1) d(X, X)
P P
X|X
c X|X
c X|X
c

23
 Thus
b ≥
IP (λ) (X; X) min I(X; X)
b = R(λD0 + λD1 ).
X|X
c PX|X
c :Ed(X,X)≤λD
b 0 +λD1

We now prove the converse. We want to prove that if R < R(D), then (R, D) is not achievable by any scheme.

Proof of the converse. Consider a (2nR , n) code with encoder fn and decoder gn that achieves Ed(X n , X
b n) = D
n n
b = gn (fn (X )). We want to show R ≥ R(D).
where X

nR ≥ H(Xb n)
b n; X n)
≥ I(X
= H(X n ) − H(X n | X
b n)
Xn
= (H(Xi ) − H(Xi | Xb n , X i−1 )
i=1
n
X
≥ H(Xi ) − H(Xi | X
bi ) conditioning reduces entropy
i=1
Xn
= I(Xi ; X
bi )
i=1
n
X
≥ R(Ed(Xi , X
bi )) def. of R(D)
i=1
n
!
1X
≥ nR Ed(Xi ; X
bi ) convexity, Jensen
n i=1
n
1X bi ) = Ed(X n ; X
b n) = D
= nR(D). E d(Xi ; X
n i=1

b n ; X n ) could be deduced directly by data-processing, since there is a “bottleneck” of nR bits

Remark: nR ≥ I(X
in the model. (?)

Let us see what happens when the inequalities become tight, in order to characterize a good scheme.
bn ): all 2nR reproductions X(i)
• nR = H(X b are equally likely.

• H(X b n | X n ) = 0, i.e. X
b n is a deterministic function of X n . [This shows that randomized decoding doesn’t
help.]
b n , X1 , . . . , Xi−1 ) = H(Xi | X
• H(Xi | X bi ), i.e. X
bi is a sufficient statistic for Xi .

• PXbi |Xi = argminP c :Ed(X, X≤D

b I(X; X).
b
X|X

• In the application of Jensen, either R(D) is linear (usually isn’t), or, in the strictly convex case, Ed(Xi , X
bi ) = D
(exactly the same) for all i.

We now consider joint source channel coding. Let V m be the observation (i.i.d. from PV ). We encode V m and
encodes it into X n , which gets sent through a discrete memoryless channel (DMC) PY |X . The channel outputs Y n is
then decoded into a reproduction Vb m of the original observation. We would like Ed(V m , Vb m ) ≤ D.
n
Theorem 9.5. Distortion D is achievable if and only if R(D) ≤ BC where B = m is the bandwith mismatch.

24
 This has a separation result, in that the following scheme is optimal. Do the rate-distortion optimal encoding to
nR(D) bits, and these are uniformly distributed. This what the channel likes. Use a channel code at rate C and send
it through the channel. Finally, do the corresponding channel decoding and the rate-distortion decoding.
The “if” part is simple: the rate R is lower than the capacity, so everything works.
For the reverse,
nC ≥ I(X n ; Y n ) channel coding converse
≥ I(V m ; Vb m )data processing
≥ mR(D). rate distortion converse
Thus R(D) ≤ BC.

10 Approximating distributions and entropy

“Approximating Probability Distributions with Dependence Trees” (Chow-Liu 1968)
P is a joint didstribution on n variables x = (x1 , . . . , xn ). Estimating this is hard (curse of dimensionality). Note
n
Y
P (x) = P (xmi | xm1 , . . . , xmi−1 )
i=1

where m1 , . . . , mn is any permutation of [n].

We want to approximate P by a “second order” distribution This is also known as “tree dependence.”
n
Y
Ptree (x) = P (xmi | xmj(i) ),
i=1

where j(i) is the parent of i. Note that these approximations use the same P that we are estimating. So for each tree
we have an explicit approximation. We are not approximating P with any distribution with a tree structure.
We want to optimize
min D(P kPt )
t∈Tn
n−2
Note |Tn | = n .
Note D(P kPt ) ≥ ln22 kP − Pt k2T V .
A maximum weight dependence tree is a tree t satisfying
n
X n
X
I(Xi ; Xj(i) ) ≥ I(Xi ; Xj 0 (i) ), ∀t0 ∈ Tn .
i=1 i=1

In other words, if we consider the complete graph on n vertices with edge weights I(Xi , Xj ), then the maximum
weight spanning tree is this maximum weight dependence tree.
Theorem 10.1. t∗ ∈ argmint∈Tn D(P kPt ) if and only if it is a maximum-weight dependence tree.
Proof.
X P (x)
D(P kPt ) = P (x) log
x
Pt (x)
X X n
X
= P (x) log P (x) − P (x) log P (xi | xj(i) )
x x i=1
n n
X X P (xi , xj(i) ) X X
= −H(X) − P (x) log − P (x) log P (xi )
x i=1
P (xj(i) )P (xi ) x i=1
n
X n
X
= −H(X) + H(Xi ) − I(Xi ; Xj(i) ).
i=1 i=1
| {z }
no dependence on t

25
 Pn
So argmint D(P kPt ) = argmaxt i=1 I(Xi ; Xj(i) ).
If we want to do this approximation, we just need to estimate the O(n2 ) mutual informations, rather than the O(2n )
probabilities (if xi are binary).
Maximum likelihood estimator of the true tree is the plug-in estimator. (Estimate mutual informations using data
and take the empirical maximum spanning tree.)
Why relative entropy ends up being nice? Chain rule / factorization is one possibility.
Our problem is as follows. We have X (1) , . . . , X (m) and we want to get an estimate of the dependence tree. We
estimate the mutual informations I(Xi , Xj ) and find the empirical max weight tree.
Recall I(X; Y ) = H(X) + H(Y ) − H(X, Y ). So it suffices to estimate entropies.
How do we estimate H(P ) given n i.i.d. samples drawn from P ?
Classical statistics. Suppose |X | = S is fixed. Find the optimal estimator of H(P ) as n → ∞. Let Pn denote the
empirical distribution, then X
H(Pn ) = − pbi log pbi
i

where pbi is the relative frequency of symbol i in the data.

H(Pn ) is the MLE for H(P ), and it is asymptotically efficient (asymptotically, attains equality in the Cramer-Rao
bound) by Hajek-Le Cam theory.
What about non-asymptotics? What if n is not “huge” relative to the alphabet size S?
Decision theoretic framework. For an estimator H b n , the worst-case risk is

Rnmax (H b n )2 ,
b n ) = sup EP (H(P ) − H
P ∈MS

and the minimax risk is

b n )2 .
inf sup EP (H(P ) − H
b n P ∈MS
H

Classical asymptotics: for the plug-in estimator,

Var(− log P (X))

EP (H(P ) − H(Pn ))2 ∼
n
3
sup Var(− log P (X)) ≤ (log S)2
P ∈MS 4
Does n  (log S)2 imply consistency?
No. Bias-variance decomposition:
b 2 = (E[H]
EP (H(P ) − H) b − H(P ))2 + VarP (H)
b

Jiao Venkat Han Weissman (2014): for the plug-in estimator,

S2 (log S)2
Rnmax (H(Pn ))  +
n2
|{z} n }
| {z
bias squared variance

If n  S (e.g. n → ∞ while S fixed) then the bias term is small and we get the classical asymptotics. Otherwise,
bias term becomes important. So, consistency of MLE is equivalent to n = Θ(S).
Next time, we show we can do better.

Recall we are trying to estimate H(P ) for some distribution P , using i.i.d. samples X n . The MLE is H(Pn )
where Pn is the empirical distribution.
From classical statistics,
Var(− log P (X))
EP (H(P ) − H(Pn ))2 ∼
n
as n → ∞. If S is the support size, this suggests the sample complexity is Θ((ln S)2 ). However, this is only valid in
the asymptotic regime n → ∞ while support size is fixed.

26
 If the support as size S,
S2 (ln S)2
sup EP (H(P ) − H(Pn ))2  2
+ .
P ∈MS n n
So the sample complexity of MLE is actually Θ(S). If n is not large enough, the bias term (first term) is too large.
There is a phase transition: if sample complexity is & S then the risk is nearly zero, if it is less, than the risk is
high.
Can we do better than the MLE? Valiant and Valiant showed that the [minimax?] phase transition for entropy
estimation occurs instead at Θ(S/ ln S).
We get an “effective sample size enlargement phenomena.” This result implies that the risk with n samples has the
same error as the MLE estimator with n log n samples.
P P
Note that entropy is separable: H(P ) = − i pi log pi = i f (pi ) where f (x) = −x log x.
Recall the issue with the MLE is large P bias when n is not large enough.
The plug-in estimator is H(Pn ) = − pbi log pbi . Consider the function f (x) = −x log x. If pbi ≈ pi and pi is
near 1/2, then f (b pi ) ≈ f (pi ) because the slope of f is low. However, near zero, f has infinite slope, so f (b
pi ) and
f (pi ) differ greatly.
To fix this, we divide [0, 1] into a smooth regime (log n/n, 1] and a non-smooth regime [0, log n/n).
1 00
For the smooth regime we have a bias-corrected estimate f (b pi ) − 2n f (b pi (1 − pbi ).
pi )b
For the non-smooth regime [0, log n/n), use the best (sup norm) polynomial approximation of f order log n.
Note that this estimation procedure does not depend on S.
We compare the L2 rates:

S2 (ln S)2
minimax : 2
+
(n log n) n
2 2
S (ln S)
MLE : 2 +
n n

11 Computing rate distortion and channel capacity

Alternating minimization algorithm.
Example: Suppose we have disjoint sets A, B and we want to find mina∈A,b∈B ka − bk2 . We maintain a current
at and bt , and then update at+1 = argmina∈A ka − bt k2 and bt+1 = argminb∈B kat+1 − bk2 . This is guaranteed to
converge to the minimum for well-behaved distance functions and convex A and B.
For us, relative entropy is a good distance function.
Let A be the joint distributions with marginal PX and expected distortion ≤ D.
( )
X
A := Q b : Ed(X, X) b ≤ D, Q(x, xb) = PX (x)
X,X
x
b

R(D) = min I(X; X)

b
Q∈A

= min D(QX,Xb kQX QXb )

Q∈A

= min D(QX,Xb kPX QXb ).

Q∈A

Lemma 11.1.
R(D) = min min D(QX,Xb kPX RXb ).
Q∈A RX
c

Proof.

D(QX,Xb kPX RXb ) − D(QX,Xb kPX QXb ) = D(QXb kRXb ) ≥ 0.

27
 To implement the alternating minimization algorithm, we need to solve two problems.

• Given QX,Xb , find RXb that minimizes D(QX,Xb kPX RXb ). The above lemma implies RXb = QXb .

• Given RXb , find QX,Xb ∈ A that minimizes D(QX,Xb kPX RXb ). Since the marginal QXb is fixed, we just need to
find QX|X
b . The following lemma shows there is a closed form expression.

Lemma 11.2. The minimizing conditional distribution has the form

−λd(x,b
x)
RX(b
b x) e
QX|X x | x) = P
(b x0 )
−λd(x,b
RX(b
b x0 ) e
b
b0
x

where λ is such that EQ d(X, X)

b = D.

Proof. Lagrange multipliers.

X
J(QX|X
b ) = D(QX|X
b PX kRXb PX ) + λ1 EQ d(X, X)
b + λ2 PX (x)QX|X
b x | x)
(b
x,b
x

∂ QX|X
b x | x)
(b
J(QX|X ) = PX (x) log + PX (x) + λ1 PX (x)d(x, x
b) + λ2 PX (x)
∂QX|X x | x)
(b RXb (b
x)
b
b

Proof of second part of Lemma 10.8.1.

r∗ (x | y) r∗ (x, y)
  X
X r(x | y)
p(x)p(y | x) log − log = p(x)p(y | x) log
x,y
p(x) p(x) x,y
r(x | y)
X r∗ (x | y)
= p(y) r∗ (x | y) log
x,y
r(x | y)

= p(y)D(r∗ (x | y)kr(x | y))

≥ 0.

Similarly, there is an alternating maximization procedure for channel capacity.

C = max I(X; Y )
PX

= max D(PXY kPX PY )

PX
X QX|Y (x | y)
= max max RX (x)PY |X (y | x) log
QX|Y RX
x,y
RX (x)

For any RX ,
RX (x)PY |X (y | x)
Q∗X|Y (x | y) := P 0 0
.
x0 RX (x )PY |X (y | x )

For any QX|Y ,

PY |X (y|x)
Q
∗ y QX|Y (x | y)
RX (x) =P Q 0 PY |X (y|x0 )
x0 y QX|Y (x | y)

28
12 Information theory and statistics
12.1 Theory of types
Let X1 , . . . , Xn be a sequence of symbols from X = {ai }.
The type of X n , denoted PX n , is the empirical distribution associated to X n = (X1 , . . . , Xn ).
Pn denotes the set of types with denominator n, i.e., the possible types associated with a sample of size n.
Example 12.1. If X = {0, 1},   
k n−k
Pn := , :0≤k≤n
n n


The type class of P ∈ Pn is

T (P ) = {xn ∈ X n : PX n = P }.
Example 12.2. If P = (3/8, 5/8), then T (P ) are all 83 binary vectors of length 8 with exactly three zeros.




Theorem 12.3.
|Pn | ≤ (n + 1)|X | .

Proof. There are n + 1 choices {0, 1, . . . , n} for each numerator.

[The above bound is very crude, but it is good enough because we will be comparing this to things that grow
exponentially in n.]
Consequently, the number of type classes is polynomial in n.

Theorem 12.4. Let X1 , . . . , Xn ∼ Q be i.i.d. Then the probability of X n is

Qn (X n ) = 2−n(H(PX n )+D(PX n kQ)) .

It makes sense that the probability depends only on the type. (Permuting does not affect the empirical distribution.)
Recall Qn (X n ) ≈ 2−nH(Q) for typical X n and contrast this with the statement of the theorem.
Proof.
P 
1
P PX n (a)
−n PX n (a) log + PX n (a) log
2−n(H(PX n )+D(PX n kQ)) = 2 a∈X PX n (a) a∈X Q(a)

P
= 2n a∈X PX n (a) log Q(a)
Y
= Q(a)nPX n (a)
a∈X
= Qn (X n ),

where we note nPX n (a) is the number of times a appears in the sample.

Theorem 12.5.
1
2nH(P ) ≤ |T (P )| ≤ 2nH(P ) .
(n + 1)|X |
That is, the type class of P has about 2nH(P ) sequences.

This is a more precise notion than typical sets. Both shows how entropy is some notion of volume.

29
Proof.

1 ≥ P n (T (P ))
X
= P n (xn )
xn ∈T (P )

= |T (P )|2−nH(P ) .

The last equality is due to P Y

2−nH(P ) = 2n a P (a) log P (a)
= P (a)nP (a) .
a

[Alternatively, apply the previous theorem with Q = PX n .]

We now prove the lower bound. We will assume

P n (T (P )) ≥ P n (T (Pb)), ∀Pb ∈ Pn

and prove it later. Intuitively, it states that under a particular probability distribution, the type with maximum proba-
bility is the original distribution.

X
1= P n (T (Q))
Q∈Pn
X
≤ max P n (T (Q))
Q
Q∈Pn
X
= P n (T (P ))
Q∈Pn

≤ |Pn |P n (T (P ))
≤ (n + 1)|X | P n (T (P ))
= (n + 1)|X | |T (P )|2−nH(P ) .

It remains to prove the “maximum likelihood” result.

P n (T (P )) P (a)nP (n)
Q
|T (P )|
= · Qa
P n (T (Pb)) |T (Pb)| nPb(a)
a P (a)
n


nP (a1 ),...,nP (a|X | ) Y
=
· P (a)n(P (a)−P (a))
b
n
nP
b(a1 ),...,nP
b(a|X | ) a

(nPb(a1 ))! · · · (nPb(a|X | ))! Y

= · P (a)n(P (a)−P (a))
b
(nP (a1 ))! · · · (nP (a|X | ))! a
Y m!
≥ (nP (a))n(P (a)−P (a)) P (a)n(P (a)−P (a)) ≥ nm−n
b b

a
n!
Y
= nn(P (n)−P (a))
b

a
P
= nn a (P (a)−P (a))
b

= 1.

Theorem 12.6. For any P ∈ Pn and any distribution Q, the probability of type class T (P ) under Q is
1
2−nD(P kQ) ≤ Qn (T (P )) ≤ 2−nD(P kQ) .
(n + 1)|X |

30
The probability of observing some empirical distribution under Q is exponentially small in the relative entropy.
Proof.
X
Qn (T (P )) = Q( xn )
xn ∈T (P )
X
= 2−n(D(P kQ)+H(P ))
xn ∈T (P )

= |T (P )|2−n(D(P kQ)+H(P )) .

Applying the previous theorem finishes the proof.

In summary,
• |Pn | ≤ (n + 1)|X | . (Bound on number of types.)
• Qn (xn ) = 2−n(H(P )+D(P kQ)) for xn ∈ T (P ).
·
• |T (P )| = 2nH(P )
·
• Qn (T (P )) = 2−nD(P kQ)

Theorem 12.7. Let X1 , X2 , . . . be i.i.d. from P . Then

P(D(PX n kP ) > ) ≤ 2−n(− n |X | log(n+1))

1

P on P .
Note that the right-hand side does not depend
The Borel-Cantelli theorem implies that if n P(D(PX n kP ) > ) < ∞, then D(PX n kP ) → 0 almost surely.

Given  > 0, let

TQ := {xn : D(PX n kQ) ≤ }.

PQn {X n : D(PX n kQ) > } = 1 − Qn (TQ )

X
= Qn (T (P ))
P ∈Pn :D(P kQ)>
X
≤ 2−nD(P kQ)
P ∈Pn :D(P kQ)>

≤ (n + 1)|X | 2−n
|X | log(n+1)
= 2−n(− n )

This is a law of large numbers: the probability of getting a sample whose empirical distribution is far from Q in relative
entropy is exponentially small. Applying Borel-Cantelli implies

D(PX n kQ) → 0, almost surely.

This is a strengthening of the law of large numbers.

Note that relative entropy controls L1 distance between measures. On finite-dimensional spaces, all norms are
equivalent, so up to constants relative entropy controls all norms (in finite dimensions). More generally, relative
entropy controls many transportation distances.

31
12.2 Large deviations
Let X1 , X2 , . . . ∼ Q be i.i.d. on a finite alphabet X .
The weak law of large numbers states
n
!
1X
P Xi > EX1 +  → 0.
n i=1

The proof using Chebychev’s inequality actually gives us a rate

n
!
1X Var(X)
P Xi > EX1 +  ≤ .
n i=1 n 2 2

We usually rewrite the left-hand side as

n
!
·
X
P Xi > nEX1 + n = 2−nE ,
i=1

where n is called the large deviation. What is interesting is that E is an exponent that we can compute explicitly,
and the upper bound is tight up to a constant.
Pn
Example 12.8. Let Xi ∼ Ber(p) and Q = Ber(p). Note that n1 i=1 Xi = EX∼PX n X = PX n (1) (the proportion
of 1s under the empirical distribution).
n
!
1X X
P Xi ≥ p +  = Qn (T (P ))
n i=1
P ∈Pn :P (1)≥p+
 
|Pn | −n min D(P kQ) −n min D(P kQ)
∈ 2 , |Pn |2
(n + 1)X

where the minimum is over the same types in the sum.

n
!
1X ·
P Xi ≥ p +  = 2−n min D(P kQ)
n i=1


This example is a special case of the following theorem, with E being the collection of distributions on {0, 1} with
expectation ≥ p + .

Theorem 12.9 (Sanov’s theorem). Let X1 , X2 , . . . ∼ Q be i.i.d. and let E be a collection of probability distributions
on X . Then the probability that the empirical distribution PX n lies in E is
∗
Qn (E) = Qn (E ∩ Pn ) ≤ (n + 1)|X | 2−nD(P kQ)
,

where P ∗ := argminP ∈E D(P kQ). Moreover, if E is the closure of its interior, then

1
log Qn (E) → −D(P ∗ kQ),
n
that is, the lower bound matches the upper bound.
 P 
Common example of the collection E is E := P : x∈X g(x)P (x) ≥ α , that is, the set of distributions whose
such that EX∼P g(X) ≥ α. If g(x) = xk , this is a moment constraint. We could also have many constraints (gj and
αj for j = 1, . . . , J).

32
Proof.
X
Qn (E) = Qn (T (P ))
P ∈E∩Pn
X
≤ 2−nD(P kQ)
P ∈E∩Pn

≤ (n + 1)|X | 2−n minP ∈E∩Pn D(P kQ)

∗
≤ (n + 1)|X | 2−nD(P kQ)
.

X
Qn (E) = Qn (T (P ))
P ∈E∩Pn
n
≥ Q (T (Pn )) for any Pn ∈ E ∩ Pn
1
≥ 2−nD(Pn kQ) .
(n + 1)|X |

We need to find a sequence {Pn : Pn ∈ E ∩ Pn }n≥1 such that D(Pn kQ) → D(P ∗ kQ). If E has nonempty interior
and E is the closure of its interior, then we can approximate any interior point by a sequence of types, and this is
possible.

We review Sanov’s theorem. We consider the collection of probability distributions on X and observe
X1 , . . . , Xn ∼ Q for one particular distribution. Let E be a collection of other distributions, e.g., set of distribu-
tions with expected value ≥ 0.8. We want to understand the probability that the empirical distribution PX n is in E.
Sanov’s theorem implies that this probability exponentially small with exponent minP ∈E D(P kQ).
−nD(P ∗ kQ)
If P ∗ := argminP ∈E D(P kQ), then we get the lower bound Qn (T (P ∗ )) ≥ (n+1) 1
|X | 2 for free. The
“closure of the interior” condition allows use to use denseness of types to extend to the case where P ∗ is not a type.
Example 12.10. Suppose we have a fair coin. What is the probability of ≥ 700 heads in 1000 tosses? Let E =
{P : EX∼P X ≥ 0.7}. Why does this make sense? If the observations X n have ≥ 700 heads then PX n ∈ E (here
n = 1000). Note that Q is the fair distribution. Sanov’s theorem implies
1
log P(≥ 700 heads) ≈ −D((0.7, 0.3)k(0.5, 0.5)) ≈ 0.119
n
More precisely,

2−138.9 = 2−n(0.119+0.0199) ≤ P(≥ 700 heads) ≤ 2−n(0.119−0.0199) = 2−99.1 .

Again, n = 1000 (but the same argument works for any n). The upper and lower bounds differ only in an exponential
factor of log n/n; as n → ∞ these are very close. 
To compute P ∗ = argminP ∈E D(P kQ) where E is convex, this becomes a convex optimization problem: use
Lagrange multipliers.
The more general version of Sanov’s theorem (continuous distributions, etc.) is as follows.

Theorem 12.11 (Sanov’s theorem).

1
− inf D(P kQ) ≤ lim inf log Qn (E)
P ∈int(E) n→∞ n
1
≤ lim sup log Qn (E)
n→∞ n
≤ − inf D(P kQ).
P ∈cl(E)

33
12.3 Conditional limit theorem
Suppose I am manufacturing bolts, each of which is supposed to nominally weight 10 grams. I find a batch of
1000 bolts that weighs ≥ 10.5 kilograms. What is the probability that any given bolt weights 11 grams?
[What does the bulk measurement tell us about the marginal distributions of the individual measurements?]

Theorem 12.12 (Conditional limit theorem). Suppose X1 , X2 , . . . ∼ Q are i.i.d. and we observe PX n ∈ E with
Q∈/ E and E is closed and convex.
p
P(X1 = a | PX n ∈ E) → P ∗ (a),
where P ∗ = argminP ∈E D(P kQ).

We need two intermediate results along the way.

/ E, let P ∗
Theorem 12.13 (Pythagorean theorem). For E ⊂ P(X ) closed and convex, and Q ∈ :=
argminP ∈E D(P kQ). Then,
D(P kQ) ≥ D(P kP ∗ ) + D(P ∗ kQ)
for all P ∈ E.

Proof. Let P ∈ E and define Pλ = λP + λP ∗ . By definition of P ∗ , we have d

dλ D(Pλ kQ) ≥ 0 at λ = 0.
X Pλ (x)
D(Pλ kQ) = Pλ (x) log
x
Q(x)
d X Pλ (x)

D(Pλ kQ) = (P (x) − P ∗ (x)) log + P (x) − P ∗ (x)
dλ x
Q(x)
X Pλ (x)
= (P (x) − P ∗ (x)) log
x
Q(x)
d X P ∗ (x)
0≤ D(Pλ kQ) = (P (x) − P ∗ (x)) log
dλ λ=0 x
Q(x)
X P ∗ (x)
= P (x) log − D(P ∗ kQ)
x
Q(x)
= D(P kQ) − D(P kP ∗ ) − D(P ∗ kQ).

Theorem 12.14 (Pinsker’s inequality).

log e
D(P kQ) ≥ kP − Qk21 .
2

Note that for A = {x : P (x) ≥ Q(x)},

X
kP − Qk1 = |P (x) − Q(x)|
x
= (P (A) − Q(A)) − (1 − P (A) − (1 − Q(A))
= 2(P (A) − Q(A))
= 2 max (P (B) − Q(B)).
B⊂X

Proof. For binary distributions, one can prove the following (exercise):

p p log e
p log + p log ≥ (2(p − q))2 .
q q 2

34
 The data processing inequality for relative entropy: if P 0 = PY |X P and Q0 = PY |X Q, then
D(P kQ) ≥ D(P 0 kQ0 ).
Define a channel Y = 1{X∈A} . Then
D(P kQ) ≥ D((P (A), 1 − P (A))k(Q(A), 1 − Q(A)))
log e
≥ (2(P (A) − Q(A)))2
2
log e
= kP − Qk21 .
2

Intuition for the conditional limit theorem: P ∗ completely dominates the behavior of the marginal.
Proof of conditional limit theorem. Let St := {P ∈ P(X ) : D(P kQ) ≤ t}. This is a convex set.
Let D∗ := D(P ∗ kQ) = minP ∈E D(P kQ).
Let A := SD∗ +2δ ∩ E and B := E \ A = E \ SD∗ +2δ .

X
Qn (B) = Qn (T (P ))
P ∈E∩Pn :
D(P kQ)>D ∗ +2δ
X
≤ 2−nD(P kQ)
P ∈E∩Pn :
D(P kQ)>D ∗ +2δ
∗
≤ (n + 1)|X | 2−n(D +2δ)
.

Qn (A) ≥ Qn (SD∗ +δ ∩ E)
X
= Qn (T (P ))
P ∈E∩Pn :
D(P kQ)≤D ∗ +δ
1 ∗
≥ |X |
2−n(D +δ) .
(n + 1)

∗
Qn (B ∩ E) Qn (B) (n + 1)|X | 2−n(D +2δ)
P(PX n ∈ B | PX n ∈E ) = n
≤ n ≤ 1 −n(D ∗ +δ)
= (n + 1)2|X | 2−nδ → 0.
Q (E) Q (A) (n+1)|X |
2
[So, the probability that our empirical distribution is outside a KL-ball around P ∗ (given it lies in E) vanishes.] Thus,
P(PX n ∈ A | PX n ∈ E) → 1.
By the Pythagorean inequality, for P ∈ A we have
D(P kP ∗ ) + D∗ = D(P kP ∗ ) + D(P ∗ kQ) ≤ D(P kQ) ≤ D∗ + 2δ,
so D(P kP ∗ ) ≤ 2δ. This combined with Pinsker’s inequality implies
P(PX n ∈ A | PX n ∈ E) ≤ P(D(PX n kP ∗ ) ≤ 2δ | PX n ∈ E) ≤ P(kPX n − P ∗ k1 ≤ δ 0 | PX n ∈ E),
and by our earlier work, these three quantities tend to 1 as n → ∞. Consequently
P(|PX n (a) − P ∗ (a)| ≤  | PX n ∈ E) → 1.

Aside: after proving Sanov’s theorem, we proved D(PX n kP ) → 0 almost surely which implies kPX n − P k1 → 0
almost surely, by Pinsker’s inequality.

35
12.4 Fisher information and Cramer-Rao lower bound
Let f (x; θ) be a family of densities indexed by θ. For example, the location family is f (x; θ) = f (x − θ) for some
f.
An estimator for θ from a sample of size n is a function T : X n → Θ. The error of this estimator T (X n ) − θ is a
random variable. Pn
For example, Xi ∼ N (θ, 1) i.i.d. and T (X n ) = n1 i=1 Xi .
An estimator is unbiased if Eθ T (X n ) = θ.
The Cramer-Rao bound states that the variance of an unbiased estimator is lower bounded by 1/J(θ).
R 0 2
Example 12.15. Let f (x; θ) := f (x − θ). Then J(θ) = ff(x) (x) dx. This is a measure of curvature/smoothness. If f
is very spread out, it is hard to estimate θ; indeed then 1/J(θ) will be large. 

We will see later that there is a finer inequality.

1 1 2h(X)
≤ 2 ≤ Var(X).
J(X) 2πe

13 Entropy methods in mathematics

13.1 Fisher information and entropy
Let u(t, x) denote the temperature at time x at time t, where x ∈ Rn . The heat equation is
n
∂ 1 X ∂2
u(t, x) = u(t, x).
∂t 2 i=1 ∂x2i

Consider the initial condition u(0, x) = δ(x) (all heat starts at 0). Then a solution is
2
u0 (t, x) = (2πt)−n/2 e−|x| /2t
.

That is, at time t, the temperature profile is the Gaussian density with variance t.
R More generally, if the initial condition is u(0, x) = f (x), then a solution is the convolution u(t, x) =
f (s)u0 (t, x − s) ds where u0 is the Gaussian kernel above. Note that if we integrate over x, we get the “total
energy” which is conserved (constant in t). This is easy to see in the special case where f is a density (in x), in which
case the convolution will also be a density, which integrates (over x) to 1, which is constant in t.
√ us focus on this special case. Let X ∼ f and Z ∼ N (0, I). Then u(t, x) = ft (x) where ft is the density of
Let
X + tZ. [Convolution √ of densities is density of sum.]
We claim h(X + tZ) is nondecreasing in t. [This matches our intuition from the second law of thermodynamics.]
√ √
h(X + tZ) ≥ h(X + tZ | Z) = h(X).

This implies √ √ √ √
h(X + t + t0 Z) = h(X + tZ + t0 Z 0 ) ≥ h(X + tZ)
which implies our claim.
Amazingly, we not only know it is increasing in t, but we have a formula for the rate of increase.

Proposition 13.1 (de Bruijn’s identity).

d √ 1 √
h(X + tZ) = J(X + tZ).
dt 2
That is,
d 1
h(ft ) = J(ft ).
dt 2

36
 We will define the Fisher information J now. Given a parametric family of densities {f (x; θ)} parameterized by
θ, the Fisher information at θ is  2
∂
J(θ) = E log f (X; θ) .
X∼f (x;θ) ∂θ

We will focus on location families where f (x; θ) := fX (x − θ) for some fixed density fX . In this case, the Fisher
information is
(f 0 (x))2
Z
J(θ) = dx,
f (x)
which is free of θ. We then use the compact notation J(θ) = J(f ) = J(X) to denote the Fisher information associated
with this density. This is the Fisher information that we will consider from now on.
In n dimensions, this generalizes to

|∇f (x)|2
Z Z p 2
J(f ) = J(X) = dx = 4 ∇ f (x) dx .
f (x)
√
The last expression shows how the Fisher information corresponds to the smoothness of f (actually, of f ).
We now prove de Bruijn’s identity.
Proof.
Z
d d
− h(ft ) = ft (x) log ft (x) dx
dt dt
Z Z
∂ ∂
= (log ft (x)) ft (x) dx + ft (x) dx
∂t ∂t
n
1 X ∂2
Z Z
d
= (log ft (x)) ft (x) dx + ft (x) dx
2 i=1 ∂x2i dt
| {z }
d
= dt 1=0
n Z
1 X ∂2
= (log ft (x)) ft (x) dx .
2 i=1
∂x2i

∂
Assuming (log ft (x)) ∂x i
ft (x) → 0 as |x| → ∞, integration by parts for each summand indexed by i (with respect
to dxi ) gives
n
∂2
Z
d 1X
− h(ft ) = (log ft (x))
ft (x) dx
dt 2 i=1 ∂x2i
 2
n Z ∂
1 X ∂xi f t (x)
=− dx
2 i=1 ft (x)
|∇ft (x)|2
Z
1
=− dx
2 ft (x)
1
= − J(ft ).
2

Note that nonnegativity of Fisher information also shows that h(ft ) is nondecreasing in t.
We will use de Bruijn’s identity to prove an uncertainty principle for entropy and Fisher information.
The entropy power inequality gives
2
√ 2 2
√ 2
e n h(X+ tZ)
≥ e n h(X) + e n h( tZ)
= e n h(X) + 2πet
2
√ 2
e n h(X+ tZ)
− e n h(X)
≥ 2πe.
t

37
Taking t → 0 makes the left-hand side equal to
d 2 h(X+√tZ) 1 2
en = J(X)e n h(X) ,
dt t=0 n
by de Bruijn’s identity. Thus, we arrive at the following.
Proposition 13.2 (Stam’s inequality).
2
J(X)e n h(X) ≥ 2πen.
This is an uncertainty principle: product of two uncertanties is greater than some constant.
Note that in dimension n = 1, we have h(X) ≤ 12 log[2πe Var(X)], so we recover the Cramer-Rao bound
J(X) Var(X) ≥ 1.

13.2 The logarithmic Sobolev inequality

Let φ be the density of Z ∼ N (0, I). Let φ(x) dx = dγ. We have
Z Z
f (x) f f
D(XkZ) = f (x) log = log dγ
φ(x) φ φ
The relative Fisher information is
Z 2 Z 2
f (x) f f
I(XkZ) = f (x) ∇ log dx = ∇ log dγ .
φ(x) φ φ
Recalling h(X) = − f log f dx and J(X) = f |∇ log f |2 dx, we see that the above two quantities are parallel
R R

analogues of entropy and Fisher information.

The above two quantities can be simplified to be
n 1 n
D(XkZ) = log(2πe) + E|X|2 − − h(X)
2 2 2
I(XkZ) = J(X) − 2n + E|X|2 .
Using the bound log x ≤ x − 1, we have
 
1 2 1
log 2πe ≤ log J(X) + h(X) ≤ J(X) − 1.
n n n
Combining this bound with the above implies the following.
Theorem 13.3 (Log Sobolev inequality, information-theoretic form).
1
I(XkZ) ≥ D(XkZ).
2

de Bruijn 2 1
EPI =⇒ J(X)e n H(X) ≥ 2πen ⇐⇒ D(XkZ) ≤ I(XkZ)
2
We only showed the forward implication of the last “if and only if.” The reverse is simple too.
Note that the last result is dimension free.
Let g 2 := f /φ. We can reformulate the last result.
Z Z
2 |∇g|2 dγ ≥ g 2 log g 2 dγ .

Noting that g 2 dγ = 1, we can write

R
Z Z Z Z
2 |∇g| dγ ≥ g log g dγ − g dγ log g 2 dγ .
2 2 2 2

This inequality still holds if we scale g by a constant. (Log terms will cancel.)

38
Theorem 13.4 (Log Sobolev inequality for Gaussian measure). For “smooth” g,
Z Z Z Z
2 |∇g| dγ ≥ g log g dγ − g dγ log g 2 dγ =: Entγ (g 2 ).
2 2 2 2

This is equivalent to the previous formulation of the log Sobolev inequality.

EPI =⇒ Fisher information-entropy uncertainty principle ⇐⇒ LSI (info. th.) ⇐⇒ LSI (functional form)

13.3 Concentration of measure

F : Rn → R is L-Lipschitz (denoted kF kLip ≤ L) if |F (x) − F (y)| ≤ L|x − y|, for all x and y.

Theorem 13.5 (Borell’s inequality). Let Z ∼ N (0, I). If kF kLip ≤ L, then

r2
P(F (Z) ≥ E[F (Z)] + r) ≤ e− 2L2 .
2
Consider U ∼ N (0, 1). We have P(U ≥ r) ≤ e−r /2 . So, the theorem states that under a Lipschitz function, the
tail behavior is still the same.
2
Without loss of generality suppose L = 1. We consider g 2 (x) := eλF (x)−λ /2 (and assume F dγ = 0) and plug
R
2
it into the LSI. We have ∇g(x) = λ2 (∇F (x))eλ/2F (x)−λ /4 , so

λ2
Z Z
2
2 2
|∇g| dγ = |∇F |2 eλF −λ /2 dγ
2
λ2
Z
2
≤ eλF −λ /2 dγ .
2
2
eλF −λ /2
R
Let Λ(λ) := dγ. The LSI implies

λ2 λ2
Z
2
eλF −λ /2
dγ =
Λ(λ)
2 2
Z
2
≥ eλF −λ /2 (λF − λ2 /2) dγ −Λ(λ) log Λ(λ)
Z
2
Λ(λ) log Λ(λ) ≥ eλF −λ /2 (λF − λ2 ) dγ = λΛ0 (λ).

1
We define the Herbst argument H(λ) = λ log Λ(λ). Then

λ2 Λ(λ)H 0 (λ) = λΛ0 (λ) − Λ(λ) log Λ(λ) ≤ 0.

Since λ2 Λ(λ) > 0 for λ > 0, we have H 0 (λ) ≤ 0.

0
We have H(0) = ΛΛ(0) (0) R
= F dγ = 0. Thus H(λ) ≤ 0 for all λ ≥ 0. This gives Λ(λ) ≤ 1, and so
Z
2
L2 /2
eλF dγ ≤ eλ .

Markov’s inequality with λ = r gives

2 2
P(F (Z) ≥ r) ≤ eλ /2−λr
= e−r /2
.

39
13.4 Talagrand’s information-transportation inequality
The quadratic Wasserstein distance between two probability measures µ and ν (on the same space) is
W22 (µ, ν) = inf E|X − Y |2
PXY :PX =µ,PY =ν

We can think of this as a distance between measures, motivated by moving probability mass from one to the other. It
is actually a metric (satisfies triangle inequality, etc.). Also, it admits a nice dimension decomposition.
W22 (µ, ν) = inf E|X − Y |2
Xn
≥ E|Xi − Yi |2
i=1
n
X
= W22 (µi , νi ).
i=1

Theorem 13.6 (Talagrand’s inequality).

2D(µkγ) ≥ W22 (µ, γ).
Note that both sides grow “linearly” in dimension n. Contrast this with Pinsker’s inequality, where the total variation
is bounded by 1 regardless
Pn of dimension, rendering it rather unhelpful.
Let PX n := n1 i=1 δXi be the empirical distribution of X1 , . . . , XN ∼ N (0, I). The following are true.
1. EW2 (PX n , γ) → 0.
2. Et = {µ : W2 (µ, γ) > t} is open in the topology of weak convergence.
3. gn : (x1 , . . . , xn ) 7→ W2 (Pxn , γ) is n−1/2 -Lipschitz.
Concentration of Lipschitz functions implies
2
P (W2 (PX n , γ) > t) ≤ e−n(t−EW2 (PX n ,γ)) /2
.
Sanov’s theorem implies
1
− inf D(µkγ) ≤ lim inf log P(W2 (PX n , γ) > t)
µ∈Et n→∞ n
≤ − lim sup(t − EW2 (PX n , γ))2 /2
n→∞
= −t2 /2.
If W2 (µ, γ) > t (i.e. µ ∈ Et ) then
2D(µkγ) ≥ t2 .
Taking t = W2 (µ, γ) −  and  → 0 proves the theorem.
Combining with the previous results gives the nice chain
I(µkγ) ≥ 2D(µkγ) ≥ W22 (µ, γ).

13.5 The blowing-up phenomenon

For B ⊂ Rn , let Bt := {x : d(x, B) ≤ t} be the t-blowup of B.
p
Theorem 13.7. Let B ⊂ Rn . If t ≥ −2 log γ(B) where γ is the standard Gaussian measure. Then,
 
1 p 2
1 − γ(Bt ) ≤ exp − (t − −2 log γ(B)) .
2
Roughly, if B contains a sufficient amount of the mass of γ, then Bt contains almost all of the mass!
Concretely, if γ(B) = 10−6 ,√ then γ(B13 ) ≥ 1 − 3 × 10−13 . If we consider Rn for n large,
√ most Gaussian vectors
lie on a spherical shell of radius n. Note that 13 is a very small distance compared to this n.

40
References
[1] Cover, Thomas and Thomas, Joy. Elements of information theory. John Wiley & Sons. 2012.

41