Finite-alphabet Berger-Tung multiterminal lossy inner bound

First fix one product test channel and reconstruction tuple. For each encoder $i$, choose ${\tilde{R}}_i=I(X_i;U_i)+\alpha \mathrm{/}4$ with $\alpha >0$, generate $M_i=\lceil e^{n{\tilde{R}}_i}\rceil$ independent $P_{U_i}^{\otimes n}$ codewords, and let encoder $i$ select the first codeword in the conditional typical set using the input and conditional tolerances specified by the following tolerance selection. It sends the selected index's bin, where each codeword is assigned independently and uniformly to $B_i=\lceil e^{n(R_i+\alpha )}\rceil$ bins. If no typical codeword exists, it selects index 1.

Fix a final relative typicality tolerance ${\tau }_k>0$ small enough for [F10] and the bounded-distortion estimate below. Work backward for $i=k,k-1,\dots ,1$: apply [F9] with output tolerance ${\tau }_i$ to obtain an input tolerance ${\delta }_i>0$, then apply [F8] with target conditional tolerance ${\delta }_i$ to obtain a source tolerance ${\sigma }_i>0$, and choose $0<{\tau }_{i-1}\le \min ({\delta }_i,{\sigma }_i)$. By [F3], the full source block belongs with probability tending to one to a jointly typical set whose empirical tolerance is small enough to ensure membership in the relative typical set $T_{{\tau }_0}^{(n)}(P_{X_1\cdots X_k})$; support is automatic there. Before stage $i$, if the source block together with $U_1^n,\dots ,U_{i-1}^n$ is in $T_{{\tau }_{i-1}}$ for its target law, projection shows that $(X_i^n,\text{all other source blocks and }{U}_1^n,\dots ,U_{i-1}^n)$ is ${\delta }_i$-typical and that $X_i^n$ is ${\sigma }_i$-typical. Conditional on the source and previous selections, codebook $i$ is independent of them, so [F8] gives a successful first-match selection with probability tending to one, uniformly over these blocks; its selected word is conditionally type-uniform. The product factorization gives $U_i-X_i-\text{(the other sources and previous auxiliaries)}$, so [F9] puts the enlarged tuple in $T_{{\tau }_i}$ except with probability tending to zero. A finite union bound over the $k$ stages proves that the selected full tuple is jointly typical with probability tending to one.

The decoder searches for a unique tuple of codewords in the received bins whose auxiliary sequences are jointly typical according to $P_{U_1\cdots U_k}$, so [F10] applies with a singleton side-information alphabet. The true tuple passes by step 1.2. For a nonempty subset $S$ of encoders whose candidate indices differ from the true indices, [F10] makes the expected number of false tuples on the typical-true-tuple event vanish if ${\sum }_{i\in S}({\tilde{R}}_i-R_i-\alpha )<{\sum }_{i\in S}H(U_i)-H(U_S\mathrm{\mid }{U}_{S^c})-\eta$ for some $\eta >0$. The selections in step 1.1 are functions only of the source and their respective codebooks, so they satisfy [F10]'s complementary-selection condition. The product test channel and [F6]–[F7] give $I(X_S;U_S\mathrm{\mid }{U}_{S^c})=H(U_S\mathrm{\mid }{U}_{S^c})-{\sum }_{i\in S}H(U_i\mathrm{\mid }{X}_i),$ because $U_S$ is conditionally independent of $U_{S^c}$ given $X_S$ and the $U_i$ are conditionally independent given their source symbols. Consequently, ${\sum }_{i\in S}I(X_i;U_i)-I(X_S;U_S\mathrm{\mid }{U}_{S^c})={\sum }_{i\in S}H(U_i)-H(U_S\mathrm{\mid }{U}_{S^c})\mathrm{.}$ The ceiling inequalities $M_i\le 2e^{n{\tilde{R}}_i}$ and $B_i\ge e^{n(R_i+\alpha )}$ give $n^{-1}\ln (M_i\mathrm{/}{B}_i)\le I(X_i;U_i)-R_i-3\alpha \mathrm{/}4+n^{-1}\ln 2$. For all sufficiently large $n$, this is at most $I(X_i;U_i)-R_i-\alpha \mathrm{/}2$. The assumed subset inequality and the preceding entropy identity then leave at least $\mathrm{\mid }S\mathrm{\mid }\alpha \mathrm{/}2$ of margin for every nonempty $S$; taking the packing slack $\eta =\alpha \mathrm{/}3$ makes the strict hypothesis of [F10] hold for every subset.

On the event that the source and selected auxiliary tuple are jointly typical and the decoder has no false tuple, decoding succeeds and the relative empirical-frequency bounds give ${\sum }_a\mathrm{\mid }\widehat{P}(a)-P(a)\mathrm{\mid }\le {\tau }_k{\sum }_{a:P(a)>0}P(a)={\tau }_k$; hence every empirical distortion differs from its test-channel expectation by at most $d_{i,\max }{\tau }_k$. The complement event has ensemble probability tending to zero by step 1.2 and step 2.1. For each fixed codebook and bin realization, let $p_n$ be the source probability of this complement event. Its ensemble average tends to zero, so there is a deterministic realization with $p_n$ no larger than that average; choose the first such realization in a fixed finite listing. For that one code, simultaneously for every $i$, expected distortion is at most $D_i+d_{i,\max }{\tau }_k+d_{i,\max }{p}_n$. Let $\alpha ,{\tau }_k\downarrow 0$ along increasing blocklengths to attain the closed subset inequalities.

A finite convex combination of fixed-test-channel rate-distortion operating points is achieved by splitting a long block into subblocks with integer lengths whose proportions converge to the combination weights, applying the corresponding code on each subblock, and concatenating their reconstructions and message indices. The rounding discrepancy in every rate and expected distortion is $O(1\mathrm{/}n)$ because there are finitely many modes and all distortions are bounded. Hence the convex hull of the union of the fixed-test-channel inner regions is achievable. No step identifies this inner bound with the full region.