CS3236 Lecture Notes #1:

Information Measures
Jonathan Scarlett

February 5, 2026

Useful references:

• Cover/Thomas Chapter 2

• MacKay Chapters 2–4

1 Information of an Event
Problem.

• If we are told that random event A occurred (e.g., coin came up tails, two dice added up to 7, it rained
today), how much “information” have we learned?

• Approach: Quantify information without any regard to significance or importance. It is only Pr[A]
that matters.

– Things like “importance” are usually too subjective to quantify.

• Generically speaking, if A occurs with probability p, then

Information(A) = ψ(p)

for some function ψ(·). Perhaps a more intuitive interpretation of ψ(p) is that it quantifies how surprised
we are that event A occurred. What properties should this function satisfy?

Axiomatic view.

• Here are some very natural properties that we should expect ψ(p) to satisfy:

1. (Non-negativity) ψ(p) ≥ 0, i.e., we cannot learn a “negative amount” of information.

2. (Zero for definite events) ψ(1) = 0, i.e., if something was certain to happen, nothing is learned by
the fact that it occurred.
3. (Monotonicity) If p ≤ p′ , then ψ(p) ≥ ψ(p′ ), i.e., the less likely the event was, the more information
is learned by the fact that it occurred.

1
 4. (Continuity) ψ(p) is continuous in p, i.e., small changes in probability don’t cause drastic changes
in information.
5. (Additivity under independence) ψ(p1 p2 ) = ψ(p1 ) + ψ(p2 ). If A and B are independent events
with probabilities p1 and p2 , then A ∩ B has probability p1 p2 , and the information learned from
both A and B occurring is the sum of the two individual amounts of information (because they
are independent!)
1
• It can be shown that only ψ(p) = logb p (for some base b > 0) satisfies all three

– We focus on b = 2, which means information is measured in “bits”. Another common choice is

b = e, which means information is measured in “nats”.
– All choices of b are equivalent up to scaling by a universal constant (e.g., number of nats =
(loge 2) × number of bits). This is much the same as how we can measure distance in meters,
kilometers, inches, or miles, but converting from one to another just amounts to scaling.
1
– So being told that a probability-p event occurred gives us log2 p “bits” of information.
– An illustration:

2 Information of a Random Variable – Entropy

Definition.

• Let X be a discrete random variable with probability mass function (PMF) PX

1
• According to the previous section, if we observe X = x then we have learned log2 PX (x) bits of
information. The (Shannon) entropy is simply the average of this value with respect to PX :
 
1
H(X) = EX∼PX log2
PX (X)
X 1
= PX (x) log2 .
x
PX (x)

1 1
– Note the convention 0 log 0 = 0, which is reasonable since limp→0 p log2 p = 0.

• Can be viewed as a measure of information in X or uncertainty in X (these are not contradictory)

2
 • Note. Here and throughout the vast majority of the course, we only consider discrete-valued random
variables that can only take on a finite number of values. We will cover continuous-valued random
variables much later.

Examples.

• Binary source:

– Suppose X ∼ Bernoulli(p) for some p ∈ (0, 1) (i.e., PX (1) = 1 − PX (0) = p)

– Then we get
1 1
H(X) = p log2 + (1 − p) log2 . (1)
p 1−p
The right hand side, as a function of p, is known as the binary entropy function. Since this
quantity will be used frequently throughout the course, we give it a formal definition: H2 (p) =
1 1
p log2 p + (1 − p) log2 1−p for p ∈ [0, 1]. An illustration:

• Uniform source:
1
– Suppose X is uniform on a finite set X (i.e., PX (x) = |X | for each x ∈ X , where |X | is the
cardinality of X )
– Then we get  
1
H(X) = E log2 = log2 |X |.
1/|X |
This is intuitive, e.g., with 10 bits we can produce |X | = 210 combinations of bits.

Axiomatic view [Shannon].

• Suppose that X is a discrete random variable taking N values, with probabilities p = (p1 , . . . , pN ). If
we consider a general information measure of the form

Ψ(p) = Ψ(p1 , . . . , pN ),

then what properties should it satisfy?

• Three natural properties:

1. (Continuity) Ψ(p) is continuous as a function of p. Again, small changes in the distribution don’t
give large changes in information/uncertainty.

3
 1
2. (Uniform case) If pi = N for i = 1, . . . , N , then Ψ(p) is increasing in N . That is, being uniform
over a larger set of outcomes always means more information/uncertainty.
3. (Successive decisions) The following always holds:
 
p1 p2
Ψ(p1 , . . . , pN ) = Ψ(p1 + p2 , p3 , . . . , pN ) + (p1 + p2 )Ψ , .
p1 + p2 p1 + p2

This can be viewed as drawing from the distribution on X by first drawing from the correspond-
ing distribution that doesn’t distinguish two symbols (the ones with probabilities p1 and p2 ),
and then drawing another random variable to resolve those two symbols if needed (which only
happens a fraction p1 + p2 of the time). The total information/uncertainty is the sum of the
information/uncertainty from each of the two stages.

• It can be shown that only Ψ(X) = constant × H(X) satisfies all three.

Variations.

• Joint entropy of two random variables (X, Y ):

 
1
H(X, Y ) = E(X,Y )∼PXY log2
PXY (X, Y )
X 1
= PXY (x, y) log2 .
x,y
PXY (x, y)

We can similarly define H(X, Y, Z) or larger collections such as H(X1 , . . . , Xn ).

• Conditional entropy of Y given X:

 
1
H(Y |X) = E(X,Y )∼PXY log2
PY |X (Y |X)
X 1
= PXY (x, y) log2
x,y
P Y |X (y|x)
X
= PX (x)H(Y |X = x), (2)
x

1
P
where in the last line, H(Y |X = x) = y PY |X (y|x) log2 PY |X (y|x) is simply the entropy of the distri-
bution PY |X (·|x) on Y . We can similarly define quantities like H(Y1 , Y2 |X1 , X2 ).

– Intuition: H(Y |X = x) is the uncertainty in Y after having observed that X = x. The conditional
entropy H(Y |X) simply averages such a quantity over X, so it represents the average remaining
uncertainty in Y after observing X.

Example:

• Consider the joint distribution described as follows:

PX (0) = 1 − p, PX (1) = p,

1 − δ y=x
PY |X (y|x) =
δ y ̸= x,

4
 where X and Y are both {0, 1}-valued.

• That is, X ∼ Bernoulli(p) and then Y is generated by flipping X with probability δ.

• We have the following:

– H(X) = H2 (p) as already done above.

– Similarly, H(Y ) = H2 (q) where q = PY (1) = p(1 − δ) + (1 − p)δ.
P
– H(Y |X) = x H(Y |X = x), but H(Y |X = x) is H2 (δ) for both x values, so H(Y |X) = H2 (δ).
– H(X; Y ) could be computed directly based on the 4 joint probabilities (pδ, p(1 − δ), (1 − p)δ, (1 −
p)(1 − δ)), but an easier way it to use the property H(X, Y ) = H(X) + H(Y |X) (see chain rule
below), giving H(X, Y ) = H2 (p) + H2 (δ).
– Computing H(X|Y ) directly would require using Bayes’ rule to get an expression for PX|Y and
P
substituting into H(X|Y ) = y PY (y)H(X|Y = y). This gets a bit more tedious, so is deferred
to the tutorial. (Again, the chain rule gives an easier approach via H(X, Y ) = H(Y ) + H(X|Y ).)

2.1 Properties of Entropy

• Non-negativity:
H(X) ≥ 0

with equality if and only if X is deterministic.

– Intuition: Information/uncertainty cannot be negative

1
– Proof: The “information of an event” log2 p is always non-negative for p ∈ [0, 1], so entropy is the
average of a quantity that is always non-negative, and so is itself non-negative. Moreover, only
1
p = 1 gives log2 p = 0, so H(X) = 0 if and only if X is deterministic.

• Upper bound: If X takes values on a finite alphabet X , then

H(X) ≤ log2 |X |

with equality if and only if X is uniform on X . This similarly implies H(X|Y ) ≤ log2 |X |.

– Intuition: The uniform distribution has the most uncertainty.

– Proof: Let P be the distribution of X, and let Q be the uniform distribution on X , so that
1
Q(x) = |X | for all x. Then note that

X P (x) X

P (x) log2 = P (x) log2 |X | · P (x)
x
Q(x) x
X
= log2 |X | + P (x) log P (x)
x

= log2 |X | − H(X).

In Section 3 we will show that the left-hand side is non-negative for any distributions P and
Q, with equality if and only if P = Q. Specialized to the above choices of P and Q, we get
log2 |X | − H(X) ≥ 0 with equality if and only if P is uniform, as desired.

5
 • Chain rule (two variables):
H(X, Y ) = H(X) + H(Y |X)

– Intuition: The overall information in (X, Y ) is the information in X plus the remaining information
in Y after observing X.
– Proof: For (X, Y ) ∼ PXY , we have
 
1
H(X, Y ) = E log2
PXY (X, Y )
 
1
= E log2
PX (X)PY |X (Y |X)
 
1 1
= E log2 + log2
PX (X) PY |X (Y |X)
= H(X) + H(Y |X).

– Note: We can swap the roles of X and Y , giving H(X, Y ) = H(Y ) + H(X|Y ).

• Chain rule (general):

n
X
H(X1 , . . . , Xn ) = H(Xi |X1 , . . . , Xi−1 ).
i=1

– Intuition: Similar to the two-variable case.

– Proof: Similar to the two-variable case, but instead use the expansion PX1 ...Xn = PX1 × PX2 |X1 ×
PX3 |X1 X2 × . . . × PXn |X1 ,...,Xn−1 .

• Conditioning reduces1 entropy:

H(X|Y ) ≤ H(X)

with equality if and only if X and Y are independent.

– Intuition: Having additional information cannot increase uncertainty on average.2

– Proof: Equivalent to the property I(X; Y ) ≥ 0 to be proved in Section 4.1.

• Sub-additivity:
n
X
H(X1 , . . . , Xn ) ≤ H(Xi )
i=1

with equality if and only if X1 , . . . , Xn are independent.

– Intuition: The uncertainty in several random variables is no more than the sum of individual
uncertainty in each one; this is because dependecies/correlations help to reduce the uncertainty.
– Proof: Apply “conditioning reduces entropy” to each summand in the general chain rule formula
above.
1 More precisely, does not increase
2 Incontrast, H(X|Y = y) for a particular y could exceed H(X). For example, suppose that PX (0) = 1 − PX (1) = 0.99,
so that X = 1 is very rare. But if Y is sufficiently correlated with X, we could have PX|Y (0|0) = 12 , meaning that being told
Y = 0 made us much less certain about X.

6
3 A Useful Measure Between Distributions – KL Divergence
• For two PMFs P and Q on a finite alphabet X , the Kullback-Leibler (KL) divergence (also known as
relative entropy) is given by

X P (x)
D(P ∥Q) = P (x) log2
x
Q(x)
 
P (X)
= EX∼P log2 .
Q(X)

• Can be viewed as a kind of “distance” between P and Q, but it is not a distance function in the
mathematical sense (in general it is not symmetric and doesn’t satisfy the triangle inequality).

• Claim. For any distributions P and Q, we have

D(P ∥Q) ≥ 0

with equality if and only if P = Q.

– Proof: Recall that changing the base of the logarithm only amounts to multiplying by a constant.
Here it is convenient to consider the natural logarithm ln = log2 e instead of log2 (·), giving

X Q(x)
−D(P ∥Q) = P (x) ln
x
P (x)
(a)
 
X Q(x)
≤ P (x) −1
x
P (x)
X X
= Q(x) − P (x)
x x

= 0,

where (a) uses the inequality ln α ≤ α − 1, which is easily verified graphically. Equality holds in
Q(x)
ln α ≤ α − 1 if and only if α = 1, which means that equality holds in (a) if and only if P (x) =1
for all x (i.e., P = Q).

• (**Optional**) While we will focus more on entropy and mutual information, we note that KL
divergence has other useful properties beyond the one above, e.g.:

– A chain rule holds; for two variables, it is

D(PXY ∥QXY ) = D(PX ∥QX ) + D(PY |X ∥QY |X |PX ),

P
where D(PY |X ∥QY |X |PX ) = x PX (x)D(PY |X (·|x)∥QY |X (·|x)).
– A data processing inequality holds: Given PX , QX , if we form PY , QY by applying the same
P P
transformation to X (i.e., PY (y) = x PX (x)V (y|x) and QY (y) = x QX (x)V (y|x) for some
randomized transformation V ), then

D(PY ∥QY ) ≤ D(PX ∥QX ).

7
 In other words, “processing” X to produce Y can only make the distributions become closer
together, not further apart.

• The KL divergence (and in fact, also entropy and mutual information) is used extensively in other
fields like statistics and machine learning. Some example uses (stated only very roughly here) are:

– In data compression, if the true source is distribution is P but we use an algorithm that wrongly
assumes it is Q, then we pay a penalty of D(P ∥Q) in the average number of bits per symbol;
– In statistics, if X = (X1 , . . . , Xn ) is i.i.d. with Xi ∼ Q, then the probability that X “looks like”
it was generated i.i.d. on P (yes, this is quite vague) is roughly 2−nD(P ∥Q) when n is large. Look
up Sanov’s theorem for a more precise statement.

4 Information Between Random Variables – Mutual Information

Definition.
• Mutual information:

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

• Intuition:

– H(Y ) is the a priori uncertainty in Y

– H(Y |X) is the remaining uncertainty in Y after observing X (on average)
– Hence, I(X; Y ) is the amount of information about Y we resolve by observing X (on average).

Variations.
• Joint version:
I(X1 , X2 ; Y1 , Y2 ) = H(Y1 , Y2 ) − H(Y1 , Y2 |X1 , X2 ).

• Conditional version:
I(X; Y |Z) = H(Y |Z) − H(Y |X, Z).

Examples.
1. If X and Y are independent, then it is straightforward to compute H(Y |X) = H(Y ), giving I(X; Y ) = 0
(i.e., independent random variables do not reveal any information about each other).

2. If Y = X, then it is straightforward to compute H(Y |X) = H(X|X) = 0, and hence I(X; X) = H(X)
(i.e., the amount of information a random variable reveals about itself is the entropy).

3. In the example given shortly after Eq. (2), we computed H(Y |X) = H2 (δ) and H(Y ) = H2 (p(1 − δ) +
(1 − p)δ), which we can substitute into I(X; Y ) = H(Y ) − H(Y |X) to get the mutual information. In
1
particular, when p = 2 we simply get

I(X; Y ) = 1 − H2 (δ).

This equation turns out to be a “channel capacity” formula in communication, and we will revisit it
(among many other examples) later in the course.

8
4.1 Properties of Mutual Information
• Alternative forms:

I(X; Y ) = D(PXY ∥PX × PY )

  X
PXY (X, Y ) PXY (x, y)
= E log2 = PXY (x, y) log2
PX (X)PY (Y ) x,y
PX (x)PY (y)
PY |X (Y |X)
  X
PY |X (y|x)
= E log2 = PXY (x, y) log2 .
PY (Y ) x,y
PY (y)

1
and H(Y |X) = E log2 PY |X1(Y |X) into the definition
   
– Proof: Substituting H(Y ) = E log2 PY (Y )
 P (Y |X) 
of mutual information gives I(X; Y ) = E log2 YP|XY (Y ) . Multiplying the numerator & denom-
inator by PX (X) gives E log2 PPXXY (X,Y ) 

(X)PY (Y ) , from which the remaining equalities follow easily.

– The expression D(PXY ∥PX × PY ) has the interpretation of measuring “how far X and Y are from
being independent”.

• Symmetry: We have
I(X; Y ) = H(X) + H(Y ) − H(X, Y )

and in particular
I(X; Y ) = I(Y ; X)

which also implies

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

– Intuition: X and Y reveal an equal amount of information about each other (or maybe this is not
that intuitive!)
– Proof: We have from the above alternative form that
 
PXY (X, Y )
I(X; Y ) = E log2
PX (X)PY (Y )
 
1 1
= E log2 + log2 + log2 PXY (X, Y )
PX (X) PY (Y )
= H(X) + H(Y ) − H(X, Y ),

where we first expanded the logarithm, and then applied the definition of (joint) entropy.

• Non-negativity: I(X; Y ) ≥ 0 with equality if and only if X and Y are independent.

– Intuition: One random variable cannot tell us a “negative amount” of information about the other.
– Proof: Using the above-established identity I(X; Y ) = D(PXY ∥PX × PY ), this is just a special
case of D(P ∥Q) ≥ 0 with equality if and only if P = Q.

• Upper bounds: We have

I(X; Y ) ≤ H(X) ≤ log2 |X |

I(X; Y ) ≤ H(Y ) ≤ log2 |Y|.

9
 – Intuition: The information X reveals about Y (mutual information) is at most the prior informa-
tion in X (entropy).
– Proof: To show that I(X; Y ) ≤ H(X), combine I(X; Y ) = H(X) − H(X|Y ) (see above) and
H(X|Y ) ≥ 0 (conditional or unconditional entropy is never negative). We already showed H(X) ≤
log2 |X | earlier, and the remaining claims follow by symmetry, reversing the roles of X and Y .

• Chain rule:
n
X
I(X1 , . . . , Xn ; Y ) = I(Xi ; Y |X1 , . . . , Xi−1 ).
i=1

– Intuition: Similar to the chain rule for entropy.

– Proof: Write I(X1 , . . . , Xn ; Y ) = H(X1 , . . . , Xn ) − H(X1 , . . . , Xn |Y ) and apply the chain rule for
entropy to both terms.

• Data processing inequality: If Z depends on (X, Y ) only through Y (often stated via the terminol-
ogy “X → Y → Z forms a Markov chain”, and equivalent to the statement “X and Z are conditionally
independent given Y ”), then
I(X; Z) ≤ I(X; Y ).

– Intuition: Processing Y (to produce Z) cannot increase the information available regarding X.
– Proof: As stated above, the statement “Z depends on (X, Y ) only through Y ” is equivalent to “Z
and X are conditionally independent given Y ”. This means that the property PZ|XY = PZ|Y (as
assumed in the result) is equivalent to PX|Y Z = PX|Y . To deduce the result, we write

(a)
I(X; Z) = H(X) − H(X|Z) (3)
(b)
≤ H(X) − H(X|Y, Z) (4)
(c)
= H(X) − H(X|Y ) (5)
(d)
= I(X; Y ), (6)

where (a) and (d) use the definition of mutual information, (b) follows since conditioning reduces
1
= E log PX|Y 1(X|Y ) = H(X|Y )
   
entropy, and (c) holds because H(X|Y, Z) = E log PX|Y Z (X|Y,Z)
by the above-established fact PX|Y Z = PX|Y .
– Variations: (See the tutorial)
∗ If X → Y → Z then I(X; Z) ≤ I(Y ; Z).
∗ If W → X → Y → Z then I(W ; Z) ≤ I(X; Y ).

• Partial sub-additivity: If (Y1 , . . . , Yn ) are conditionally independent given (X1 , . . . , Xn ), and in

addition Yi depends on (X1 , . . . , Xn ) only through Xi , then

n
X
I(X1 , . . . , Xn ; Y1 , . . . , Yn ) ≤ I(Xi ; Yi ).
i=1

However, without the conditional independence assumptions, this property may fail to hold. This will
be proved in a later tutorial, and will be important when we get to the topic of channel coding.

10
5 (Optional) Entropy of English Text
• Shannon’s famous 1948 paper discussed several (intentionally over-simplified) probabilistic models for
generating English text; see Figure 1 below.

Figure 1: Excerpt from Shannon’s paper.

• Stated differently, #3 generates each letter conditioned on the previous one, #4 conditions on the
previous two, #5 lets the “alphabet” X be the set of all words rather than the set of all characters and
generates each word independently, and #6 generates each word conditioned on the previous one.

• Fundamental question: How much information (entropy) does each letter of English text tell us?

– The entropy H(X) of a single character doesn’t capture the fact that previous characters help in
predicting the next one.
– As detailed in Chapter 4 of Cover/Thomas, a more meaningful measure in such scenarios is

H(Xn |X1 , . . . , Xn−1 ),

representing the uncertainty of a given character given all of the previous ones.

11
 – Fitting a model to English text and then calculating the entropy of that model is prone to be
inaccurate (too complex to fit a very accurate model!) – is there a simpler approach?

• Key idea: The entropy is closely related to how many guesses are needed (on average) before the
correct character is guessed, by an optimal guessing algorithm.

– Intuitively, entropy is a measure of uncertainty, and higher uncertainty means more guesses will
be needed on average.
– Writing an optimal guessing algorithm is hard (though an interesting machine learning problem!),
so experiments were done under the assumption that humans are near-optimal guessers.
– Using some theory behind the “optimal guessing” viewpoint, and observing the average number
of guesses that several humans required, it was estimated that the entropy of English text is at
most 1.34 bits per character
– This is much less than the highest possible value of log2 27 ≈ 4.75 with 27 characters (a-z and
“space”)
– Note: Recent developments in Language Models suggest that the “correct” value may even be
significantly smaller than 1.34 (details omitted).

• See Chapter 6 of Cover/Thomas for further details.

6 (Optional) Other Properties

More properties of entropy.

• Functions of random variables: For a deterministic function f , we have

H(f (X)) ≤ H(X)

– Intuition: Transforming a random variable doesn’t increase its information content.

– Proof: Since f (X) is deterministic given X, we have H(f (X)|X) = 0, and hence

H(X) = H(X) + H(f (X)|X)

= H(X, f (X))
= H(f (X)) + H(X|f (X))
≥ H(f (X)),

where the first and third lines use the chain rule, and the last line uses non-negativity.
– An alternative proof is explored in the tutorial.

• Information-preserving transform: If Y depends on X only through f (X), then

H(Y |X) = H(Y |f (X)).

– Intuition: By the assumption, f (X) already gives us all that X can tell us about Y .

12
 – Proof: Let F = f (X). By assumption PY |X (y|x) = PY |F (y|f (x)) for some PY |F , and hence
   
1 1
H(Y |X) = E log2 = E log2 = H(Y |f (X)).
PY |X (Y |X) PY |F (Y |f (X))

• Concavity: The entropy H(X) satisfies a useful property known as concavity (as a function of the
distribution PX ).

More properties of mutual information.

• Functions of random variables. If Y depends on X only through f (X), then

I(X; Y ) = I(f (X); Y ).

This follows easily from the analogous conditional entropy property above upon applying I(X; Y ) =
H(Y ) − H(Y |X).

• Convexity properties: Mutual information I(X; Y ) is concave in PX for fixed PY |X , and is convex
in PY |X for fixed PX .

– For an introduction to convexity, see the book “Convex Optimization” by Boyd and Vandenberghe

13