Finite-alphabet memoryless rate-distortion coding theorem

Let a deterministic length-$n$ code have $M_n$ messages and reconstruction ${\widehat{X}}^n$. Data processing [F6] gives $I(X^n;{\widehat{X}}^n)\le H(f_n(X^n))\le {\log }_2{M}_n$. Put $D_n=\mathbb{E}{d}_n(X^n,{\widehat{X}}^n)$, and let $T$ be uniform on $\{0,\dots ,n-1\}$, independent of all variables; set $(X,Y)=(X_T,{\widehat{X}}_T)$. Since the source symbols are iid, $H(X^n)={\sum }_{i}H(X_i)$. By [F5], the chain rule, and conditioning reducing entropy from [F7], $I(X^n;{\widehat{X}}^n)={\sum }_i[H(X_i)-H(X_i\mid X^{i-1},{\widehat{X}}^n)]\ge {\sum }_{i}I(X_i;{\widehat{X}}_i)\mathrm{.}$ Also $I(X;Y\mid T)=n^{-1}{\sum }_{i}I(X_i;{\widehat{X}}_i)$, while $I(X;T)=0$; the chain rule and nonnegative conditional information [F7] imply $I(X;Y)\le I(X;Y,T)=I(X;Y\mid T)$. Thus $R(D_n)\le I(X;Y)\le n^{-1}I(X^n;{\widehat{X}}^n)\le n^{-1}{\log }_2{M}_n$, since $\mathbb{E}d(X,Y)=D_n$.

Assume $D\ge D_{\min }$, and choose a minimizing test channel $W(\widehat{x}\mathrm{\mid }x)$ by [F3]. Let $Y$ have its induced output pmf, and let $(X_i,Y_i)$ be iid copies of the test-channel pair. Its information density $\mathrm{ı}(X;Y)={\log }_2[W(Y\mathrm{\mid }X)\mathrm{/}{P}_Y(Y)]$, on positive joint support, is finite-valued because the alphabets are finite; it has mean $I:=R(D)$. The block distortion is bounded with mean at most $D$. The iid law of large numbers therefore gives, for every $\eta ,\delta >0$, $\mathbb{P}\{d_n(X^n,Y^n)\le D+\eta ,{\sum }_{i<n}\mathrm{ı}(X_i;Y_i)\le n(I+\delta )\}⟶1.$ The distortion and information-density summands are bounded on finite alphabets, hence square-integrable; [F8] applied to each iid sequence proves both convergences in probability and the displayed joint event.

For an expected-distortion code sequence with ${\mathrm{lim\hspace{0.17em}sup}}_n{D}_n\le D$, eventually $D_n\le D+ϵ$, so step 1.1 and monotonicity give $R(D+ϵ)\le n^{-1}{\log }_2{M}_n$. For an excess-distortion sequence and any $ϵ>0$, boundedness gives $D_n\le D+ϵ+d_{\max }\mathbb{P}(d_n>D+ϵ)$, hence eventually $D_n\le D+2ϵ$; then $R(D+2ϵ)\le n^{-1}{\log }_2{M}_n$. Taking limsups and using [F4] as $ϵ\downarrow 0$ proves both operational rates are at least $R(D)$ whenever feasible. If $D<D_{\min }$, every reconstruction has block distortion at least $n^{-1}{\sum }_i{\min }_{\widehat{x}}d(X_i,\widehat{x})$; its mean is $D_{\min }$, and the iid law of large numbers makes it converge in probability to $D_{\min }$. Thus neither operational criterion is feasible below $D_{\min }$.

For each source word $x^n$, let $G_n(x^n)$ be the reproduction words satisfying both inequalities in step 1.2. The joint probability of this event tends to one, so the source probability of the set where $P(Y^n\in G_n(X^n)\mid X^n)<1\mathrm{/}2$ is at most twice the probability of the complement and tends to zero. On the other source words, every $y^n\in G_n(x^n)$ satisfies $P(y^n\mathrm{\mid }{x}^n)\mathrm{/}{P}_Y^n(y^n)\le 2^{n(I+\delta )}$; summing this likelihood-ratio inequality over the good set yields $P_Y^n(G_n(x^n))\ge \frac{1}{2}{2}^{-n(I+\delta )}$.

Draw $M_n=\lceil 2^{n(I+2\delta )}\rceil$ reproduction words independently from $P_Y^n$. For each source word in the high-probability set of step 2.2, the chance that no codeword belongs to $G_n(x^n)$ is at most $(1-q{)}^{M_n}\le e^{-M_{n}q}\le e^{-2^{n\delta }\mathrm{/}2}$. Source words outside that set have probability tending to zero, so the expected failure probability of the random codebook tends to zero. Since the codebook alphabet is finite, for each n there is a deterministic realization whose failure probability is at most twice this expectation (and if the expectation is zero, a realization with zero failure exists).

Encode each source word by the first codebook word in its good set; if there is none, use a fixed default reproduction word. Decode the selected codeword. This is a deterministic fixed-length code; its rate is at most $I+2\delta +o(1)$. Its distortion is at most $D+\eta$ on success and at most $d_{\max }$ on failure. Choose ${\eta }_j\downarrow 0$; for each j the failure probability is at most $1\mathrm{/}j$ for all sufficiently large n by step 3.1. Use increasing thresholds and at length n the largest available j=j(n). Then $j(n)\to \mathrm{\infty }$, expected distortion has limsup at most $D$, and for every fixed $ϵ>0$, eventually ${\eta }_{j(n)}<ϵ$, so $\mathbb{P}(d_n>D+ϵ)\le 1\mathrm{/}j(n)\to 0$.

For any target rate $R(D)+ϵ$, choose $\delta >0$ with $2\delta <ϵ$. Steps 1.2, 2.2, 3.1, and 4.1 give codes with both operational criteria and limiting rate at most $R(D)+2\delta <R(D)+ϵ$. Taking the infimum proves both operational rates are at most $R(D)$. Together with step 2.1 this proves the theorem.