Distributed Source Coding — Examples

The one-letter joint masses are $P(0,0)=P(1,1)=(1-p)\mathrm{/}2$ and $P(0,1)=P(1,0)=p\mathrm{/}2$. Summing rows and columns gives uniform marginals. For either $y$, the conditional law of $X$ given $Y=y$ has masses $1-p$ and $p$; the same holds for $Y$ given $X=x$. Therefore [F2] gives $H_P(X\mid Y)=H_P(Y\mid X)=h(p)$, including $p=0$ and $p=1\mathrm{/}2$ under the zero-term convention.

Directly summing the four joint entropy terms gives $H_P(X,Y)=\ln 2+h(p)$: the two diagonal terms contribute $-(1-p)\ln ((1-p)\mathrm{/}2)$ and the two off-diagonal terms contribute $-p\ln (p\mathrm{/}2)$, with zero terms omitted when $p=0$.

Since $0\le p\le 1\mathrm{/}2$, the binary entropy satisfies $0\le h(p)\le \ln 2$. The lower bound follows termwise from $\ln t\le 0$ for $0<t\le 1$ and [F5], while [F6] applied to $(p,1-p)$ and $(1\mathrm{/}2,1\mathrm{/}2)$ gives $\ln 2-h(p)\ge 0$. Thus the region from [F3] is $R_1\ge h(p)$, $R_2\ge h(p)$, and $R_1+R_2\ge \ln 2+h(p)$. For $h(p)\le R_1\le \ln 2$, the sum constraint gives the boundary $R_2=\ln 2+h(p)-R_1$, joining the stated endpoints; for $R_1\ge \ln 2$, the coordinate bound $R_2\ge h(p)$ is the active lower boundary.

If $p>0$, all four joint masses are positive, so the support bipartite graph in [F4] has every possible edge and is connected. Any common function $K=f(X)=g(Y)$ almost surely must then satisfy $f(0)=g(0)=f(1)=g(1)$, since each of the four pairs has positive probability. Hence the common part is constant and has entropy zero.

Under [F1], each of the pairs $(0,0)$ and $(1,1)$ has source probability $1\mathrm{/}4$. Under independent maps $F_X,F_Y:\{0,1\}\to [M]$, each equality $F_X(0)=F_X(1)$ and $F_Y(0)=F_Y(1)$ has probability $1\mathrm{/}M$, because the two labels in each map are independent and uniform. The two equalities are independent across encoders, so both competing pairs collide in both message coordinates with probability $M^{-2}$.

Under a shared map $F_X=F_Y=F$, both message-coordinate collision conditions are the same event $F(0)=F(1)$. Its probability is $1\mathrm{/}M$, not $1\mathrm{/}{M}^2$. At $M=2$, the two probabilities are $1\mathrm{/}4$ and $1\mathrm{/}2$.

The calculation identifies why the independent-map hypothesis in [F3] permits multiplication of per-encoder collision probabilities. It does not claim that every shared-map code is poor; it shows that this particular product bound cannot be used for the shared ensemble.