Finite-alphabet memoryless Wyner-Ziv theorem

Fix a length-$n$ code, put $W=f_n(X^n)$, and write ${\widehat{X}}_i$ for the $i$th decoder output. Let $u_M$ be uniform on $[M]$. By [F13], $0\le D(P_W\mathrm{\parallel }{u}_M)={\sum }_{w:P_W(w)>0}{P}_W(w)\ln \frac{P_W(w)}{1\mathrm{/}M}=\ln M-H(W),$ so $\ln M\ge H(W)$. The conditional-mutual-information identity and nonnegativity in [F5] give $H(W)-H(W\mathrm{\mid }{Y}^n)=I(W;Y^n)\ge 0$ and $I(X^n;W\mathrm{\mid }{Y}^n)=H(W\mathrm{\mid }{Y}^n)-H(W\mathrm{\mid }{X}^n,Y^n)\le H(W\mathrm{\mid }{Y}^n),$ because conditional entropy is nonnegative by its finite-sum definition [F12]. Combining these inequalities gives $\ln M\ge H(W)\ge H(W\mathrm{\mid }{Y}^n)\ge I(X^n;W\mathrm{\mid }{Y}^n)$.

By [F6], choose a minimizing finite test channel $(U,P_{U\mathrm{\mid }X},g)$ with $\mathrm{\mid }\mathcal{U}\mathrm{\mid }\le \mathrm{\mid }\mathcal{X}\mathrm{\mid }+1$ and expected distortion at most $D$. Choose a codebook rate $\tilde{R}>I(X;U)$ and a bin rate $R>I(X;U\mathrm{\mid }Y)$ so that $s:=I(U;Y)-(\tilde{R}-R)>0$; this is possible because the test-channel factorization in [F1] gives $I(U;Y\mathrm{\mid }X)=0$ by [F3], and the chain rule [F4]–[F5] yields $I(X;U\mathrm{\mid }Y)=I(X;U)-I(U;Y)$. Put $\eta =s\mathrm{/}2$ and fix a final joint-typicality tolerance $ϵ>0$ small enough for [F10] with slack $\eta$ and for the bounded-distortion estimate, with error $\omega (ϵ)\to 0$ as $ϵ\downarrow 0$.

Generate $M_n=\lceil e^{n\tilde{R}}\rceil$ independent codewords with law $P_U^{\otimes n}$ and assign each codeword an independent uniform bin label in $[B_n]$, where $B_n=\lceil e^{nR}\rceil$. On a source block $x^n$, the encoder chooses the first codeword in the conditional typical set with the source/conditional tolerances chosen below from [F8]–[F9] and sends its bin; if none exists, it sends the first bin. Given $(m,y^n)$, the decoder finds the unique codeword in bin $m$ jointly typical with $y^n$ at tolerance $ϵ$ and applies $g$ coordinatewise, defaulting to a fixed reproduction block if uniqueness fails. These are finite code ensembles and deterministic maps once a realization is fixed.

Let $Y^{-i}$ denote all side-information coordinates except $Y_i$ and define $U_i=(W,Y^{-i})$. Memorylessness gives $H(X^n\mathrm{\mid }{Y}^n)={\sum }_{i}H(X_i\mathrm{\mid }{Y}_i)$, while the conditional entropy chain rule gives $H(X^n\mathrm{\mid }W,Y^n)={\sum }_{i}H(X_i\mathrm{\mid }{X}^{i-1},W,Y^n)\le {\sum }_{i}H(X_i\mathrm{\mid }W,Y^n)$. Subtracting yields $I(X^n;W\mathrm{\mid }{Y}^n)\ge {\sum }_{i=1}^{n}I(X_i;W,Y^{-i}\mathrm{\mid }{Y}_i)={\sum }_{i=1}^{n}I(X_i;U_i\mathrm{\mid }{Y}_i)\mathrm{.}$ Each $U_i-X_i-Y_i$: conditional on $X_i$, the independent pair $(X_i,Y_i)$ is independent of all other source pairs, and $W,Y^{-i}$ are functions of $X^n,Y^{-i}$.

Apply [F9] with output tolerance $ϵ$ from step 1.2 to obtain its input tolerance ${\delta }_M$. Apply [F8] with target conditional tolerance ${\delta }_M$; it supplies a source tolerance ${\delta }_X>0$. Choose a relative source-pair tolerance ${\delta }_{XY}\le \min ({\delta }_M,{\delta }_X)$. In [F11], take the empirical tolerance below ${\delta }_{XY}{\min }_{P_{XY}(x,y)>0}{P}_{XY}(x,y)$; then the pair block belongs to $T_{{\delta }_{XY}}^{(n)}(P_{XY})$ with probability tending to one. Summing relative typicality errors over the $Y$-coordinates shows that its $X^n$ marginal is in $T_{{\delta }_X}^{(n)}(P_X)$, so [F8] makes covering failure tend to zero uniformly. Conditional on successful selection, its law is uniform within each conditional type class, and [F9] makes $(X^n,Y^n,U^n)$ jointly typical at tolerance $ϵ$ with probability tending to one. Therefore the selected true codeword is jointly typical with $Y^n$, except on an event whose probability tends to zero.

Let $T$ be uniform on $[n]$ and independent of the source, and put $(X,Y,U,\widehat{X})=(X_T,Y_T,(U_T,T),{\widehat{X}}_T)$. The just-proved Markov property gives $U-X-Y$, the reconstruction is a deterministic function of $(Y,U)$, and its expected distortion is ${\bar{D}}_n:=n^{-1}{\sum }_i\mathbb{E}d(X_i,{\widehat{X}}_i)$. Since $T$ is independent of $(X_T,Y_T)$, $I(X;U\mathrm{\mid }Y)=n^{-1}{\sum }_{i}I(X_i;U_i\mathrm{\mid }{Y}_i)$. Thus step 1.1 gives $n^{-1}\ln M\ge I(X;U\mathrm{\mid }Y)\ge R_{\mathrm{W}\mathrm{Z}}({\bar{D}}_n)$. For any operationally achievable sequence with distortion limsup at most $D$, for every ${\epsilon }_D>0$ we eventually have ${\bar{D}}_n\le D+{\epsilon }_D$; monotonicity and continuity in [F7], followed by ${\epsilon }_D\downarrow 0$, prove $R_{\mathrm{W}\mathrm{Z}}^{\mathrm{o}\mathrm{p}}(D)\ge R_{\mathrm{W}\mathrm{Z}}(D)$. If $D<D_{\min }$, every reproduction has pointwise distortion at least ${\min }_{\widehat{x}}d(X,\widehat{x})$, so no code can meet the target.

The codebook is independent of the source pair, and its bin labels are independent of source and codebook. Apply [F10] with selection data $Z^n=(X^n,Y^n)$, decoder side information $S^n=Y^n$, and $k=1$. The complementary-selection restriction is vacuous, and the changed candidate codeword is independent of $(X^n,Y^n)$; the codebook-to-bin exponent is at most $\tilde{R}-R+n^{-1}\ln 2<I(U;Y)-\eta$ for all sufficiently large $n$ by the choice of $s$ and $\eta$ in step 1.2. Thus the probability of a false jointly typical codeword together with a typical true codeword tends to zero. Together with step 2.2, this makes the ensemble probability ${\bar{q}}_n$ of the exceptional event (covering failure, an atypical true $(X^n,Y^n,U^n)$ tuple, or decoding failure) tend to zero. On the complementary event, the joint empirical type is within tolerance $ϵ$, so the bounded per-letter distortion of $g(Y,U)$ is at most $D+\omega (ϵ)$ for a deterministic $\omega (ϵ)\to 0$; on the exceptional event it is at most $d_{\max }$. Hence the ensemble mean distortion is at most $D+\omega (ϵ)+d_{\max }{\bar{q}}_n$.

For each fixed codebook and bin realization $C$, let $q_n(C)$ be the source probability of the exceptional event from step 3.2; its ensemble mean is ${\bar{q}}_n$. The finite-ensemble mean of expected distortion plus $d_{\max }{q}_n(C)$ is at most $D+\omega (ϵ)+2d_{\max }{\bar{q}}_n$. Some deterministic realization has this sum no larger than its ensemble mean; choose the first such realization in a fixed finite ordering. Its distortion is therefore at most $D+\omega (ϵ)+2d_{\max }{\bar{q}}_n$. Letting $ϵ$ and the rate slack decrease along an increasing sequence of blocklengths proves $R_{\mathrm{W}\mathrm{Z}}^{\mathrm{o}\mathrm{p}}(D)\le R_{\mathrm{W}\mathrm{Z}}(D)$. Together with step 3.1 this proves equality.