Stationary-ergodic bounded-distortion rate-distortion theorem

For any source word $x_0^{n-1}$, every reconstruction word satisfies $d_n(x_0^{n-1},{\widehat{x}}_0^{n-1})\ge \frac{1}{n}{\sum }_{i=0}^{n-1}{\min }_{\widehat{x}}d(x_i,\widehat{x})\mathrm{.}$ The right side has expectation $D_{\min }$ by stationarity, so every code has expected distortion at least $D_{\min }$. If $D<D_{\min }$, choose $ϵ>0$ with $D+ϵ<D_{\min }$ and put $g(X)={\min }_{\widehat{x}}d(X,\widehat{x})$. Birkhoff [F6] gives almost-sure convergence of the averages of this bounded function to a finite invariant function $g^{\ast }$. For every rational $a$, the limsup orbit set ${\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}{T}^{-n}\{g^{\ast }>a\}$ is strictly invariant and differs from $\{g^{\ast }>a\}$ by a null set. Ergodicity makes each such level set have probability zero or one, so $g^{\ast }$ is constant almost surely. Dominated convergence and stationarity identify the constant as $\mathbb{E}g=D_{\min }$. Hence the pointwise-minimum block average converges almost surely to $D_{\min }$, and the probability that any code's distortion exceeds $D+ϵ$ tends to one. Both operational criteria are therefore infeasible below $D_{\min }$. By [F2], no stationary coupling with mean distortion below $D_{\min }$ exists either, so $R_{\mathrm{e}\mathrm{r}\mathrm{g}}(D)=+\mathrm{\infty }$; [F3] gives $R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)=+\mathrm{\infty }$.

Let a deterministic length-$n$ code have $M_n$ messages and reconstruction ${\widehat{X}}^n$. Since $X^n\to f_n(X^n)\to {\widehat{X}}^n$ is a Markov chain, [F7] gives $I(X^n;{\widehat{X}}^n)\le H(f_n(X^n))\le {\log }_2{M}_n$. Its induced joint law is feasible in the definition of $R_n(D_n)$, where $D_n=\mathbb{E}{d}_n(X^n,{\widehat{X}}^n)$, so $R_n(D_n)\le n^{-1}{\log }_2{M}_n$.

For every jointly stationary ergodic pair feasible at $D$, the finite-block law is feasible in $R_n(D)$, so $R_n(D)\le n^{-1}{I}_2(X_0^{n-1};{\widehat{X}}_0^{n-1})$. Taking limits and then the infimum over such pairs gives $R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)\le R_{\mathrm{e}\mathrm{r}\mathrm{g}}(D)$.

For expected-distortion codes with $\mathrm{lim\hspace{0.17em}sup}{D}_n\le D$, eventually $D_n\le D+ϵ$, giving $R_n(D+ϵ)\le n^{-1}{\log }_2{M}_n$. For a positive-slack excess code, boundedness gives $D_n\le D+ϵ+d_{\max }\mathbb{P}(d_n>D+ϵ)$, so eventually $D_n\le D+2ϵ$; then $R_n(D+2ϵ)\le n^{-1}{\log }_2{M}_n$. Taking limits and using [F3], followed by right-continuity as $ϵ\downarrow 0$, proves $R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)\le R_{\mathrm{o}\mathrm{p}}^{\mathrm{a}\mathrm{v}\mathrm{g}}(D)$ and $R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)\le R_{\mathrm{o}\mathrm{p}}^{\mathrm{s}\mathrm{l}\mathrm{a}\mathrm{c}\mathrm{k}}(D)$.

Conversely, for any bit rate $r>R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)$, [F4] supplies a jointly stationary ergodic pair with mean distortion at most $D$ and limsup bit mutual-information rate less than $r$. Thus $R_{\mathrm{e}\mathrm{r}\mathrm{g}}(D)\le r$; letting $r\downarrow R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)$ proves $R_{\mathrm{e}\mathrm{r}\mathrm{g}}(D)=R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)$.

Fix a jointly stationary ergodic pair $(X,\widehat{X})$ supplied by step 2.2. By [F8], each of the source, reproduction, and joint-pair normalized block entropies has a limit; [F9] therefore gives convergence of $n^{-1}{I}_2(X_0^{n-1};{\widehat{X}}_0^{n-1})$ to a finite bit rate $\bar{I}\le \mathrm{lim\hspace{0.17em}sup}{n}^{-1}{I}_2(X_0^{n-1};{\widehat{X}}_0^{n-1})<r$. By [F5] applied to those three stationary ergodic processes, their normalized negative log probabilities in bits converge almost surely to their entropy rates. Subtracting the three limits shows that the information density $i_n(x^n;{\widehat{x}}^n):={\log }_2\frac{P_{{\widehat{X}}^n\mathrm{\mid }{X}^n}({\widehat{x}}^n\mathrm{\mid }{x}^n)}{P_{{\widehat{X}}^n}({\widehat{x}}^n)}$ divided by $n$ converges almost surely to $h(X)+h(\widehat{X})-h(X,\widehat{X})=\bar{I}$, with each entropy rate in bits.

On the ergodic pair shift let $g=d(X_0,{\widehat{X}}_0)$. By [F6], its time averages converge almost surely to a finite invariant function $g^{\ast }$. Apply the rational-level-set argument from step 1.1 to this bounded function on the ergodic pair system; its limit is constant, and dominated convergence with stationarity identifies that constant as $\bar{d}:=\mathbb{E}d(X_0,{\widehat{X}}_0)\le D$. Thus $d_n(X^n,{\widehat{X}}^n)\to \bar{d}$ almost surely. Fix $\eta >0$ and $\delta >0$. The event $G_n:=\{d_n(X^n,{\widehat{X}}^n)\le D+\eta ,i_n(X^n;{\widehat{X}}^n)\le n(\bar{I}+\delta )\}$ has probability tending to one by step 3.1 and this distortion convergence. Hence the set of source words whose conditional probability of this event is at least $1\mathrm{/}2$ has source probability tending to one: its complement probability is at most twice $\mathbb{P}(G_n^c)$.

For any such source word $x^n$, on its good reproduction set the likelihood ratio $P_{{\widehat{X}}^n\mathrm{\mid }{x}^n}\mathrm{/}{P}_{{\widehat{X}}^n}$ is at most $2^{n(\bar{I}+\delta )}$. Therefore an independent reproduction word sampled from $P_{{\widehat{X}}^n}$ lands in that set with probability at least $\frac{1}{2}{2}^{-n(\bar{I}+\delta )}$. Draw $M_n=\lceil 2^{n(\bar{I}+2\delta )}\rceil$ independent reproduction words. The probability that none works for this source word is at most $(1-q{)}^{M_n}\le e^{-M_{n}q}\le e^{-2^{n\delta }\mathrm{/}2}$. Averaging over source words shows the expected failure probability of the random codebook tends to zero.

Some deterministic realization of each random codebook has failure probability at most twice its ensemble mean (if the mean is zero, choose a realization with zero failure). Encode a source word by the first codeword satisfying the good conditions, and use a fixed default reproduction if none does. The decoder outputs the selected codeword, so the code is deterministic and has $M_n$ messages. On success its distortion is at most $D+\eta$; on failure it is at most $d_{\max }$.

To obtain expected distortion at most $D$ in the limit and positive-slack excess distortion, choose a decreasing sequence ${\eta }_j\downarrow 0$. For each $j$, the failure probability in step 6.1 is at most $1\mathrm{/}j$ for all sufficiently large $n$; choose increasing thresholds and at each length use the largest such $j=j(n)$ available. Then $j(n)\to \mathrm{\infty }$, expected distortion is at most $D+{\eta }_{j(n)}+d_{\max }\mathrm{/}j(n)$, and for every fixed slack $ϵ>0$, eventually ${\eta }_{j(n)}<ϵ$, so $\mathbb{P}(d_n>D+ϵ)\le 1\mathrm{/}j(n)\to 0$. The code rate has limsup at most $\bar{I}+2\delta$.

Given any target rate $R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)+ϵ$, choose $r=R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)+ϵ\mathrm{/}3$. Step 2.2 gives $\bar{I}<r$, so choose $\delta >0$ with $\bar{I}+2\delta <R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)+ϵ$. Steps 5.1, 6.1 and 7.1 give both operational criteria at rate below the target. Thus $R_{\mathrm{o}\mathrm{p}}^{\mathrm{a}\mathrm{v}\mathrm{g}}(D)\le R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)$ and $R_{\mathrm{o}\mathrm{p}}^{\mathrm{s}\mathrm{l}\mathrm{a}\mathrm{c}\mathrm{k}}(D)\le R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)$. Together with steps 2.1 and 2.2 this proves all equalities. The excess criterion used positive slack throughout; it does not imply the unclaimed exact-threshold assertion at $D_{\min }$.