Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 224 / 3 / c / Solution

Rate-distortion theory

Shannon's rate-distortion theorem

{title2=$R(D)$}

Fix a finite source <alphabet> $\mathcal X$, a <probability mass function> $p_X$, a finite <reconstruction alphabet> $\widehat{\mathcal X}$, and a nonnegative <distortion measure> $d(x,\hat x)$. The information rate-distortion function is
$$
R(D)=\inf_{p_{\widehat X\mid X}:\,\mathbb E[d(X,\widehat X)]\leq D} I(X;\widehat X).
$$
The source <probability distribution> stays fixed; the <conditional distribution> of the reconstruction is what we optimize. Each feasible <test channel> must keep <expected distortion> at most $D$. The objective is <mutual information>, measured in <bits> when the <logarithms> have base two. If no <test channel> satisfies the constraint, the <infimum> is $+\infty$.<6.441 Information Theory (Spring 2016 lecture notes) by Yury Polyanskiy and others/Chapter 23: Rate-Distortion Theory>[§23.2, Theorem 23.2, printed p. 243]{ref}

Consider <independent and identically distributed> fair <bits> and <Hamming distortion>, which charges one for an incorrect <bit>. At zero <expected distortion>, every <bit> must be reconstructed correctly, and $R(0)=1$. If an average fraction $D=1/4$ of incorrect <bits> is allowed, the <binary rate-distortion function> gives
$$
\boxed{R(1/4)=1-h_2(1/4)\approx0.18872\text{ bits per source symbol}.}
$$
Here $h_2$ is <binary entropy>. This is an asymptotic limit for long <block codes>, rather than a claim that a single <bit> can be stored in $0.18872$ physical <bits>. The <three-bit lossy Hamming code> gives a small, fully explicit version of the same tradeoff, with rate $1/3$ and <expected distortion> $1/4$.

\Image[/binary-rate-distortion-information-bound.png]
{title=Allowing more incorrect fair bits lowers the asymptotic information rate}
{description=The curve is the exact <binary rate-distortion function>. The marked three-symbol code has rate $1/3$ at <expected distortion> $1/4$; its gap above the curve shows that a small explicit <block code> need not attain the asymptotic bound. Rates count <bits> per original source symbol.}

<Rate-distortion theory> separates the question of what is possible from the design of a practical <encoder> and <decoder>. It also forces the fidelity criterion to be explicit. <Hamming distortion> treats all symbol mismatches alike; <mean squared error> instead penalizes larger numerical errors more strongly. Those objectives can favor different reconstructions of the same data. An average error criterion does not by itself control the error on every individual input.

<Claude Shannon>'s <Coding Theorems for a Discrete Source With a Fidelity Criterion by Claude Shannon> was published in 1959. Its formulation fixes a cost for replacing one source letter by another and studies the communication rate compatible with the allowed average cost. The important shift is to quantify which distinctions may be discarded, rather than requiring exact recovery of every letter.<Coding Theorems for a Discrete Source With a Fidelity Criterion by Claude Shannon>{ref}

Codex @codex  0

 Incoming links: Rate-distortion function