Random-cut stationary ergodic block-channel approximation

By [F2]–[F3], choose $k\ge 1$ and a length-$k$ test channel $W_k$ whose expected normalized distortion is at most $D$. Write $I_k:=I_2(X_0^{k-1};{\widehat{X}}_0^{k-1})$ bits for this channel and $r_k:=I_k\mathrm{/}k$. The choice can be made with $r_k<r$ because $R_{\mathrm{b}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}(D)={\inf }_k{R}_k(D)<r$ and the finite-block minimum is attained.

Fix $p\in (0,1)$. By [F4], the consistent finite-dimensional product laws of a mutually independent family $(B_t,U_t{)}_{t\in \mathbb{Z}}$, with each $B_t\sim \mathrm{B}\mathrm{e}\mathrm{r}\mathrm{n}\mathrm{o}\mathrm{u}\mathrm{l}\mathrm{l}\mathrm{i}(p)$ and each $U_t$ uniform on $[0,1]$, extend to a probability law $P_M$ on ${\mathrm{\Omega }}_M=(\{0,1\}\times [0,1]{)}^{\mathbb{Z}}$ with its product sigma-algebra; the marker and seed processes are independent. Let $({\mathrm{\Omega }}_X,P_X,T)$ be the source shift system and form the independent product extension $({\mathrm{\Omega }}_X\times {\mathrm{\Omega }}_M,P_X\otimes P_M,T\times S)$, where $S$ is the marker-seed shift. The product measure exists by [F4], and its rectangle formula makes the source independent of both marker and seed processes. Almost surely there are marker times $B_t=1$ arbitrarily far in both directions: for each fixed starting index, the probability of no marker in the next $N$ sites is $(1-p{)}^N\to 0$, and a countable union handles all starting indices. Thus the marker set partitions $\mathbb{Z}$ into finite segments between consecutive markers.

The product of the source system and the iid marker-seed shift is ergodic. To verify this, take two bounded real-valued rectangle cylinder functions $f_1(X)g_1(B,U)$ and $f_2(X)g_2(B,U)$. For all sufficiently large shifts $n$, the iid-coordinate windows of $g_1$ and $g_2\circ S^n$ are disjoint, so their expectation factors as $\mathbb{E}{g}_1\mathbb{E}{g}_2$. For the source factor, [F7] gives almost-sure convergence of $N^{-1}{\sum }_{n=0}^{N-1}{f}_2(T^{n}X)$ to a finite invariant function $f_2^{\ast }$. Ergodicity makes $f_2^{\ast }$ constant almost surely: for each rational $a$, the limsup orbit set ${\mathrm{lim\hspace{0.17em}sup}}_{n\to \mathrm{\infty }}{T}^{-n}\{f_2^{\ast }>a\}$ is strictly invariant and differs from $\{f_2^{\ast }>a\}$ by a null set, so it has probability zero or one; the rational level sets then force a constant value. Since $f_2$ is bounded, dominated convergence and preservation of the source law show this constant is $\mathbb{E}{f}_2$. Thus the time averages of $f_2$ converge almost surely to $\mathbb{E}{f}_2$, and bounded convergence gives $\frac{1}{N}{\sum }_{n=0}^{N-1}\mathbb{E}[f_1(X)f_2(T^{n}X)]⟶\mathbb{E}{f}_1\mathbb{E}{f}_2\mathrm{.}$ The Cesàro correlations of the rectangle functions therefore converge to the product of their means. Their finite linear combinations are dense in real product $L^2$: indicators of measurable rectangles form a generating $\pi$-system, and the class of sets whose indicators lie in the $L^2$-closure of their span is a Dynkin class, since increasing unions converge in $L^2$ on a probability space. The $\pi$-$\lambda$ theorem and density of simple functions give the claim. Cauchy–Schwarz and shift invariance extend the correlation limit to every real $L^2$ function. If $A$ is invariant, its indicator has correlation $\mathbb{P}(A)$ at every shift, while the limit is $\mathbb{P}(A{)}^2$; hence $\mathbb{P}(A)\in \{0,1\}$.

Fix a pointwise minimizer ${\widehat{x}}_{\ast }(x)$ for each source letter. For a segment beginning at marker $s$ and ending just before the next marker $s+L$, divide its first $k\lfloor L\mathrm{/}k\rfloor$ sites into consecutive length-$k$ blocks. At each such block start use its seed $U_t$ and the finite inverse-cumulative rule to sample an output block from $W_k(\cdot \mid X_t^{t+k-1})$; on the remaining $L<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>k<k$ sites, output ${\widehat{x}}_{\ast }(X_t)$. On the shift-invariant null set where markers do not occur arbitrarily far in both directions, define ${\widehat{X}}_t={\widehat{x}}_{\ast }(X_t)$ for every $t$. The resulting map is measurable because each good-segment event is determined by finitely many marker coordinates and each seed selects among finitely many outputs by measurable intervals; it is shift-equivariant because all rules translate with the markers.

The pair $(X,\widehat{X})$ is a shift-commuting factor of the ergodic product system from step 1.3, so it is stationary and ergodic: the preimage of a shift-invariant event in the factor is shift-invariant in the product and therefore has probability zero or one. Its source marginal is unchanged because the construction leaves X fixed.

Let $\alpha$ be the probability that coordinate zero lies in a leftover suffix. A segment of length $\mathrm{\ell }$ has $\mathrm{\ell }<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>k$ leftover sites. Summing over its possible start and length gives $\alpha =p^2{\sum }_{\mathrm{\ell }=1}^{\mathrm{\infty }}(\mathrm{\ell }<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>k)(1-p{)}^{\mathrm{\ell }-1}\le (k-1)p^2{\sum }_{\mathrm{\ell }=1}^{\mathrm{\infty }}(1-p{)}^{\mathrm{\ell }-1}=(k-1)p\mathrm{.}$ Marker events in this sum specify a cut at the segment start, no intervening marker, and a cut at the end; the leftover site is one of the final $\mathrm{\ell }<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>k$ positions.

The marker process is independent of X. For any length-$n$ window, condition on the markers and sum distortion over all test-channel blocks fully contained in the window; each such block has the stationary length-$k$ source law, so its expected total distortion is at most $kD$. At most two blocks intersect the window without being contained, and their total distortion is bounded by $2k{d}_{\max }$. Leftover sites have expected distortion $D_{\min }$ each. Divide by $n$, take expectations, and let $n\to \mathrm{\infty }$; the boundary contribution vanishes, while stationarity makes the expected mean distortion equal to $\mathbb{E}d(X_0,{\widehat{X}}_0)$ for every n. Since the expected leftover fraction is $\alpha$, this yields $\mathbb{E}d(X_0,{\widehat{X}}_0)\le (1-\alpha )D+\alpha D_{\min }\le D$.

Let E be the independent marker process B, leaving the independent uniform seeds unconditioned. Its value space $\{0,1{\}}^{\mathbb{Z}}$ is standard Borel by [F4] and [F8]. Put $U=X_0^{n-1}$ and $V={\widehat{X}}_0^{n-1}$. Independence in step 1.2 gives $P_{UE}=P_U\otimes P_E$, so $I_2(U;E)=D(P_U\otimes P_E\mathrm{\parallel }{P}_U\otimes P_E)\mathrm{/}\ln 2=0$. Coordinate-swap invariance and the first-argument chain rule in [F5] now give $I_2(U;(V,E))=I_2((E,V);U)=I_2(E;U)+I_2(V;U\mid E)=0+I_2(U;V\mid E)\mathrm{.}$ Expanding instead in the order $(V,E)$ gives $I_2(U;(V,E))=I_2(U;V)+I_2(U;E\mid V)\ge I_2(U;V)$. Thus $I_2(X_0^{n-1};{\widehat{X}}_0^{n-1})\le I_2(X_0^{n-1};{\widehat{X}}_0^{n-1}\mid E)$, using only nonnegative extended sums and the explicitly zero independent term. Conditional on E, outputs from distinct test-channel blocks are sampled independently according to $W_k$, and leftover outputs are deterministic. Enlarge the source window to include every source coordinate in a full length-$k$ block intersecting $[0,n-1]$, and enlarge the output to include each such full test-channel block output plus the leftover reconstructions inside the window. The original source and output windows are coordinate projections of these enlarged finite vectors, so [F6], applied conditionally on each marker realization, bounds the original information by the enlarged information. Conditional output entropy is subadditive across block outputs and leftover symbols. Given the enlarged source and E, the block outputs are independent and the leftover symbols are deterministic, so conditional output entropy is the sum of the block conditional entropies. Each length-$k$ block has the stationary source law followed by $W_k$, and hence contributes $I_k$ bits; each leftover symbol contributes at most ${\log }_2\mathrm{\mid }\widehat{\mathcal{X}}\mathrm{\mid }$ bits. There are at most $n\mathrm{/}k+2$ intersecting channel blocks, and stationarity makes the expected number of leftover sites in the window $n\alpha$. Therefore $\frac{1}{n}{I}_2(X_0^{n-1};{\widehat{X}}_0^{n-1})\le (\frac{1}{k}+\frac{2}{n})I_k+\alpha {\log }_2\mathrm{\mid }\widehat{\mathcal{X}}\mathrm{\mid }\mathrm{.}$

Since $r_k<r$, choose $p>0$ small enough that $(k-1)p{\log }_2\mathrm{\mid }\widehat{\mathcal{X}}\mathrm{\mid }<r-r_k$ (if the logarithm is zero, any $p\in (0,1)$ works). Taking $n\to \mathrm{\infty }$ in step 4.2 and using step 3.2 yields a limiting upper information rate at most $r_k+(k-1)p{\log }_2\mathrm{\mid }\widehat{\mathcal{X}}\mathrm{\mid }<r$. step 3.1 and step 4.1 give the required stationary ergodic pair and distortion bound.