Finite-IID k-source Slepian–Wolf rate region

For the converse, suppose $R$ is achievable and fix nonempty $S\subseteq [k]$. Write $H_S:=H_P(X_S\mid X_{S^c})$ and $R_S:={\sum }_{i\in S}{R}_i$. If $R_S<H_S$, put $\gamma :=H_S-R_S>0$. By [F2], along the achieving blocklengths and for all sufficiently large $n$, the product message count $M_S:={\prod }_{i\in S}{M}_i$ obeys $n^{-1}\ln M_S\le R_S+\gamma \mathrm{/}4$, since each of the finitely many coordinate rate limsups is at most $R_i$.

Fix such a blocklength and a complement word $x_{S^c}^n$ of positive probability. Its complement message indices are then fixed. For each possible $S$-message tuple, the common decoder outputs at most one candidate $x_S^n$, so at most $M_S$ values of $x_S^n$ can be decoded correctly for this complement word.

For achievability, take any $R\in {\mathcal{R}}_{\mathrm{S}\mathrm{W}}(P)$ and any slack $a>0$. Put ${\rho }_i:=R_i+a$ and $\eta :=a\mathrm{/}2$. Then for every nonempty $S$, ${\sum }_{i\in S}{\rho }_i\ge H_S+\mathrm{\mid }S\mathrm{\mid }a\ge H_S+a$. Because there are finitely many such $S$, [F5] gives one empirical tolerance $\delta >0$ that works for every subset. Set $ϵ:=a\mathrm{/}4$ and use ${\mathcal{T}}_n(P,\delta ,ϵ)$.

For this $n$, set $M_i:=\lceil e^{n{\rho }_i}\rceil$. For every encoder $i$, independently assign each word in ${\mathcal{X}}_i^n$ a uniform label in $[M_i]$, with all word-label assignments independent across words and encoders. The decoder returns the unique jointly typical source tuple having the received vector of labels; if there is not exactly one, it returns a fixed default tuple from fixed finite listings of the nonempty alphabets. This defines a finite ensemble of valid codes of the form in [F2].

Fix a true tuple $z^n\in {\mathcal{T}}_n$ and a distinct jointly typical competitor ${\tilde{z}}^n$. Let $S$ be exactly the nonempty set of terminals where ${\tilde{x}}_i^n\mathrm{\ne }{x}_i^n$. For each $i\in S$, the two distinct source words receive independent uniform labels, so their collision probability is $1\mathrm{/}{M}_i$; assignments for distinct encoders are also independent. Therefore the probability that all message labels of the competitor equal the true labels is ${\prod }_{i\in S}{M}_i^{-1}$.

Choose the typical set ${\mathcal{T}}_n(P,1,\gamma \mathrm{/}4)$. For any supported block in this set, [F3] gives $P^{\otimes n}(x_S^n\mid x_{S^c}^n)\le e^{-n(H_S-\gamma \mathrm{/}4)}$. Summing over at most $M_S$ correctly decoded $S$-blocks from step 1.2 and then averaging over $X_{S^c}^n$ yields $P\{\text{correct decode and }{Z}^n\in {\mathcal{T}}_n\}\le M_S{e}^{-n(H_S-\gamma \mathrm{/}4)}\le e^{-n\gamma \mathrm{/}2}$.

If the true tuple is typical, decoding error requires at least one distinct typical competitor to share its message vector. For a fixed nonempty difference set $S$ and fixed true complement $x_{S^c}^n$, [F5] bounds the number of possible $S$-parts of such competitors by $(n+1{)}^m{e}^{n(H_S+a\mathrm{/}2)}$, where $m=\mathrm{\mid }\mathcal{X}\mathrm{\mid }$. By step 1.5 and the union bound over all nonempty $S$, the expected error over the finite random-code ensemble is at most $P(Z^n\mathrm{\notin }{\mathcal{T}}_n)+(2^k-1)(n+1{)}^m{e}^{-na\mathrm{/}2}$. Indeed, $M_i\ge e^{n(R_i+a)}$ and ${\sum }_{i\in S}(R_i+a)\ge H_S+\mathrm{\mid }S\mathrm{\mid }a$, leaving exponent at most $-a\mathrm{/}2$ for each $S$.

By [F4], $P(Z^n\mathrm{\notin }{\mathcal{T}}_n(P,1,\gamma \mathrm{/}4))\to 0$. Step 2.1 therefore implies the probability of correct decoding tends to zero, so the block-error probability tends to one. This contradicts [F2]. Thus every achievable $R$ satisfies $R_S\ge H_S$ for every nonempty $S$.

The first term in step 2.2 tends to zero by [F4]. For the second, [F6] and $1\mathrm{/}t\le 1\mathrm{/}\sqrt{t}$ for $t\ge 1$ give $\ln (n+1)\le 2(\sqrt{n+1}-1)$, hence $m\ln (n+1)\mathrm{/}n\to 0$ and $(n+1{)}^m{e}^{-na\mathrm{/}2}\to 0$. Since the ensemble is finite, at least one deterministic code has error no larger than the ensemble average; select the first such map tuple in a fixed finite listing. Thus for every fixed $a>0$ and all sufficiently large $n$, there is a deterministic code with error tending to zero and rates $\frac{1}{n}\ln M_i\le R_i+a+\frac{\ln 2}{n}$, using $\lceil x\rceil \le 2x$ for $x\ge 1$.

Finally take $a_j:=1\mathrm{/}j$ and choose recursively increasing $n_j$ large enough that the selected code's error is at most $1\mathrm{/}j$ and $(\ln 2)\mathrm{/}{n}_j\le 1\mathrm{/}j$. Step 3.2 then gives coordinate rate limsups at most $R_i$. These codes make $R$ achievable, including boundary points where one or more subset inequalities are equalities.