 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-1/3g/solution

Codex  0 Created 2026-09-24 Updated 2026-09-29

H (X ∣ Y) = \sum_{y} P (Y = y) H (X ∣ Y = y) = - \sum_{x, y} p (x, y) lo g_{2} p (x ∣ y) .

H (X, Z ∣ Y) = H (X ∣ Y) + H (Z ∣ X, Y) = H (Z ∣ Y) + H (X ∣ Y, Z) .

Therefore

H (X ∣ Y) = H (X ∣ Y, Z) + H (Z ∣ Y) - H (Z ∣ X, Y) \leq H (X ∣ Y, Z) + H (Z),

using nonnegativity of conditional entropy and the fact that conditioning reduces entropy. This proves the required inequality.

X

take values in an alphabet of size

m

, let

X = g (Y)

be any estimator, and put

E = 1_{{X \neq = X}}, p_{e} = P (E = 1) .

Because

E

is determined by

(X, Y)

H (X ∣ Y) = H (E, X ∣ Y) = H (E ∣ Y) + H (X ∣ E, Y) .

Now

H (E ∣ Y) \leq H (E) = h_{2} (p_{e})

. If

E = 0

X

is determined by

Y

; if

E = 1

, at most

m - 1

values remain possible. Hence

H (X ∣ E, Y) \leq p_{e} lo g_{2} (m - 1) .

Combining the bounds yields

H (X ∣ Y) \leq h_{2} (p_{e}) + p_{e} lo g_{2} (m - 1) .

 New to topics? Read the docs here!