Distributed Source Coding

Let $r$ be a probability vector on an alphabet of size $m\ge 1$, and let $u_m$ be the uniform vector. Expanding the finite sum in [F3] gives $D(r\mathrm{\parallel }{u}_m)=\ln m-H(r)$, including zero coordinates by the stated convention. Since $u_m$ has full support, [F4] shows that $r\mapsto D(r\mathrm{\parallel }{u}_m)$ is continuous. Therefore finite entropy is continuous on every finite simplex.

For any joint vector $q_{UV}$, [F1] and [F2] give $H_q(U\mid V)=-{\sum }_{(u,v):q_{UV}(u,v)>0}{q}_{UV}(u,v)\ln \frac{q_{UV}(u,v)}{q_V(v)}=H(q_{UV})-H(q_V)$. The ratio is defined on every positive joint atom because then $q_V(v)>0$. The marginal map $q_{UV}\mapsto q_V$ is linear. By step 1.1, both terms on the right are continuous functions of $q_{UV}$, so their difference is continuous on the joint simplex.

For each $v$ with $q_V(v)>0$, let $J_v:=\{j:v_j=v\}$. The sets $J_v$ partition the positions of $v^n$. A word $u^n$ has joint type $q$ with this fixed $v^n$ exactly when, within each $J_v$, it places $nq(u,v)$ copies of symbol $u$. These counts sum to $n{q}_V(v)=\mathrm{\mid }{J}_v\mathrm{\mid }$, and their ratios define the attainable type $q_{U\mid v}$ of length $\mathrm{\mid }{J}_v\mathrm{\mid }$. Restriction to each $J_v$ gives a bijection from the joint-type fiber to the Cartesian product of these local type classes, so their cardinalities multiply and give the displayed product. Values with $q_V(v)=0$ have no positions and contribute factor $1$.

Apply [F3] to each factor in step 1.1, with blocklength $n{q}_V(v)$, to get $\mathrm{\mid }{T}_{q_{U\mid v}}\mathrm{\mid }\le e^{n{q}_V(v)H(q_{U\mid v})}$. Multiplying the finite bounds gives $\exp (n{\sum }_{v:q_V(v)>0}{q}_V(v)H(q_{U\mid v}))$, which equals $e^{n{H}_q(U\mid V)}$ by [F4] and [F5]. The omitted zero-mass rows contribute zero to the entropy sum.

For each coordinate $t$, support gives $P_{X_S,X_C}(x_{S,t},x_{C,t})>0$, and the finite marginal sum $P_{X_C}(x_{C,t})={\sum }_{x_S}{P}_{X_S,X_C}(x_S,x_{C,t})$ is therefore positive by [F3]. Summing the finite product law over all $x_S^n$ and distributing the finite sums gives $P_{X_C^n}^{\otimes n}(x_C^n)={\sum }_{x_S^n}{\prod }_{t=1}^n{P}_{X_S,X_C}(x_{S,t},x_{C,t})={\prod }_{t=1}^n{P}_{X_C}(x_{C,t})>0$. Thus the conditional block probability is defined by dividing its joint mass by this positive complement marginal.

Using [F1] for the numerator and step 1.1 for the denominator, that ratio is $\frac{{\prod }_{t=1}^n{P}_{X_S,X_C}(x_{S,t},x_{C,t})}{{\prod }_{t=1}^n{P}_{X_C}(x_{C,t})}={\prod }_{t=1}^n\frac{P_{X_S,X_C}(x_{S,t},x_{C,t})}{P_{X_C}(x_{C,t})}={\prod }_{t=1}^n{P}_{X_S\mid X_C}(x_{S,t}\mid x_{C,t})$, where each final factor is the conditional probability in [F2]. This proves the factorization.

By [F4], choose $\delta >0$ so that every joint probability vector $q$ with $\mathrm{\parallel }q-P{\mathrm{\parallel }}_{\mathrm{\infty }}\le \delta$ satisfies $\mathrm{\mid }{H}_q(X_S\mid X_C)-H_P(X_S\mid X_C)\mathrm{\mid }\le \eta$. The joint alphabet is identified with ${\mathcal{X}}_S\times {\mathcal{X}}_C$ by a coordinate permutation, so the same coordinatewise neighborhood applies to the joint type of $(x_S^n,x_C^n)$.

For the fixed $x_C^n$, each $x_S^n$ in the set has a unique joint empirical type $q$ by [F2]. There are at most $(n+1{)}^m$ possible such types, since each of the $m$ joint symbol counts is an integer from $0$ to $n$; the sum constraint can only reduce this count.

For each feasible type $q$ arising from a typical block, [F1] and step 1.1 give $H_q(X_S\mid X_C)\le H_P(X_S\mid X_C)+\eta$. By [F3], its conditional type class has size at most $\exp (n(H_P(X_S\mid X_C)+\eta ))$. Summing this bound over the at most $(n+1{)}^m$ types from step 1.2 proves the claimed inequality. The empty-complement case uses its singleton alphabet and the same count.

Fix $a\in \mathcal{X}$ and put $B_{t,a}:={\mathbf{1}}_{\{Z_t=a\}}$. For any distinct $t_1,\dots ,t_r$ and sets $E_j\subseteq \{0,1\}$, ${\bigcap }_j\{B_{t_j,a}\in E_j\}={\bigcap }_j\{Z_{t_j}\in {\varphi }_a^{-1}(E_j)\}$, where ${\varphi }_a(z)={\mathbf{1}}_{\{z=a\}}$. Mutual independence in [F1, F4] factors the probability of this intersection, and the common law $P$ gives every $B_{t,a}$ the same distribution; hence $(B_{t,a})$ are IID. Their mean is $P(a)$ and variance is $P(a)(1-P(a))\le 1\mathrm{/}4$. Their sample mean is ${\widehat{P}}_{Z^n}(a)$ by [F3]. Independence gives $\mathbb{E}[({\widehat{P}}_{Z^n}(a)-P(a){)}^2]=\mathrm{Var}(B_{1,a})\mathrm{/}n\le 1\mathrm{/}(4n)$; since a square is at least ${\delta }^2$ on the event of deviation at least $\delta$, that event has probability at most $1\mathrm{/}(4n{\delta }^2)$. If $P(a)=0$, the probability that $a$ occurs at any of the first $n$ positions is zero. A union bound over the finite alphabet proves that the support and empirical-coordinate requirements in [F2] fail with probability at most $\mathrm{\mid }\mathcal{X}\mathrm{\mid }\mathrm{/}(4n{\delta }^2)$.

By [F5], the full-information requirement in [F2] fails with probability at most $V(P)\mathrm{/}(n{ϵ}^2)$.

Fix a nonempty $S\subseteq [k]$ and write $C=S^c$. On the support of $P$, define $W_t^S:=-\ln P_{X_S\mid X_C}(X_{S,t}\mid X_{C,t})$, and set it to $0$ off the support. This is a finite-valued function ${\psi }_S(Z_t)$. For distinct $t_1,\dots ,t_r$ and Borel sets $B_1,\dots ,B_r$, ${\bigcap }_j\{W_{t_j}^S\in B_j\}={\bigcap }_j\{Z_{t_j}\in {\psi }_S^{-1}(B_j)\}$; [F1, F4] therefore give mutual independence and a common law, so $(W_t^S)$ are IID. Its mean is $H_P(X_S\mid X_C)$ by the finite sum in [F6] and the zero-term convention in [F8], and its variance ${\sigma }_S^2$ is finite because its range is finite. By [F7], $J_{S,n}=n^{-1}{\sum }_{t=1}^n{W}_t^S$ almost surely. Independence gives $\mathbb{E}[(J_{S,n}-H_P(X_S\mid X_C){)}^2]={\sigma }_S^2\mathrm{/}n$, so the same squared-deviation argument bounds failure of this conditional requirement by ${\sigma }_S^2\mathrm{/}(n{ϵ}^2)$.

There are finitely many symbols and finitely many nonempty subsets $S$. The union bound over the failure events in steps 1.1, 1.2, and 1.3 is at most $\frac{\mathrm{\mid }\mathcal{X}\mathrm{\mid }}{4n{\delta }^2}+\frac{V(P)+{\sum }_{\mathrm{\varnothing }\mathrm{\ne }S\subseteq [k]}{\sigma }_S^2}{n{ϵ}^2}$, which tends to zero. Its complement is exactly the event in the Statement, proving the claimed limit.

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.