Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Lossy Source Coding with Side Information

1 · Prerequisites

2 · Summary

This page proves the finite-alphabet memoryless Wyner-Ziv theorem for expected normalized additive distortion, with natural logarithms and rates in nats. The encoder sees $X^{n}$ only, the decoder sees both the message and $Y^{n}$ , and the single-letter distortion $d (x, \hat{x})$ does not depend on $Y$ . The exact rate is the minimum of $I (X; U ∣ Y)$ over $U - X - Y$ and reconstructions $\hat{X} = g (Y, U)$ ; the finite auxiliary bound is $∣ U ∣ \leq ∣ X ∣ + 1$ .

For multiple encoders, the page proves the finite-alphabet Berger-Tung subset inequalities as an achievable inner bound. It does not claim those inequalities characterize the general multiterminal lossy rate-distortion region. Random codebook covering, selected-codeword Markov typicality, and joint-bin packing are proved locally before either coding theorem uses them.

The first data-flow diagram depicts the Wyner-Ziv operational model. The source feeds only the encoder; the decoder uses both the message and the side-information block to form the reconstruction. The second diagram depicts separate encoders with one shared decoder. Both are schematic descriptions of the code maps defined in the items above; neither diagram is used as proof evidence.

\begin{tikzpicture}[>=stealth]
\node (x) at (0,0) {$X^n$};
\node[draw] (enc) at (2,0) {encoder $f_n$};
\node (m) at (4,0) {$M$};
\node[draw] (dec) at (6,0) {decoder $g_n$};
\node (y) at (6,-1.4) {$Y^n$};
\node (xh) at (8,0) {$\widehat X^n$};
\draw[->] (x)--(enc);
\draw[->] (enc)--(m);
\draw[->] (m)--(dec);
\draw[->] (y)--(dec);
\draw[->] (dec)--(xh);
\end{tikzpicture}

\begin{tikzpicture}[>=stealth]
\node (x1) at (0,1) {$X_1^n$};
\node[draw] (e1) at (2,1) {encoder $f_{1,n}$};
\node (m1) at (4,1) {$M_1$};
\node (x2) at (0,-1) {$X_2^n$};
\node[draw] (e2) at (2,-1) {encoder $f_{2,n}$};
\node (m2) at (4,-1) {$M_2$};
\node[draw] (dec) at (6,0) {common decoder};
\node (xh) at (9,0) {$(\widehat X_1^n,\widehat X_2^n)$};
\draw[->] (x1)--(e1);
\draw[->] (e1)--(m1);
\draw[->] (x2)--(e2);
\draw[->] (e2)--(m2);
\draw[->] (m1)--(dec);
\draw[->] (m2)--(dec);
\draw[->] (dec)--(xh);
\end{tikzpicture}

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite strongly typical sets with support restriction

Definition

Let $A$ be a finite nonempty alphabet, let $P$ be a probability vector on $A$ in the sense of Finite distributions, entropy, divergence, and stochastic matrices, and let $n \geq 1$ . Write $supp (P) : = {a \in A : P (a) > 0}$ . For $a^{n} = (a_{1}, \dots, a_{n}) \in A^{n}$ , its empirical distribution is ${\hat{P}}_{a^{n}} (a) : = n^{- 1} ∣ {t : a_{t} = a} ∣$ . For $δ > 0$ , define the support-restricted strongly typical set by $T_{δ}^{(n)} (P) : = {a^{n} \in supp (P)^{n} : ∣ {\hat{P}}_{a^{n}} (a) - P (a) ∣ \leq δ P (a) for every a with P (a) > 0} .$ For a finite joint law $P_{X A}$ and a fixed $x^{n}$ , write $T_{δ}^{(n)} (P_{A ∣ X} ∣ x^{n}) : = {a^{n} : (x^{n}, a^{n}) \in T_{δ}^{(n)} (P_{X A})}$ . This conditional set is empty if $x^{n}$ is outside the support of $P_{X}$ . Zero-probability letters are excluded exactly, so no logarithm of zero occurs in likelihood calculations on these sets.

Remarks

The relative tolerance is used to keep support and likelihood ratios explicit. Each finite alphabet gives finitely many empirical distributions, and every sequence in $T_{δ}^{(n)} (P)$ has its empirical frequencies within a stated multiplicative tolerance of $P$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Finite type-class cardinality bounds

Statement

Let $A$ be a finite nonempty alphabet of size $m$ , let $n \geq 1$ , and let $q$ be an attainable empirical distribution with integer counts $n_{a} = n q (a)$ . Its type class $T_{q} : = {a^{n} \in A^{n} : {\hat{P}}_{a^{n}} = q}$ satisfies $(n + 1)^{- m} \exp (n H (q)) \leq ∣ T_{q} ∣ \leq \exp (n H (q)),$ where $H (q) : = - \sum_{a : q (a) > 0} q (a) \ln q (a)$ and $0 \ln 0 : = 0$ .

Facts & Assumptions

Given: The finite alphabet, positive blocklength, and attainable type $q$ .

[F1]

Finite strongly typical sets with support restriction: ${\hat{P}}_{a^{n}} (a)$ is the count of $a$ in $a^{n}$ divided by $n$ , and a type class is the set of sequences with that count vector.

[F2]

Finite distributions, entropy, divergence, and stochastic matrices: for a finite probability vector, $H (q) = - \sum_{a : q (a) > 0} q (a) \ln q (a)$ , with $0 \ln 0 = 0$ .

Proof

1.1F1F2algebra

Under the product law $q^{\otimes n}$ , every $a^{n} \in T_{q}$ has probability $\prod_{a} q (a)^{n_{a}} = \exp (- n H (q))$ , omitting zero-count coordinates. Since the total probability of $T_{q}$ is at most one, $∣ T_{q} ∣ \exp (- n H (q)) \leq 1$ , which gives the upper bound.

1.2F1algebra

To bound the probability of $T_{q}$ below, compare it with an arbitrary attainable type $r$ with counts $m_{a} = n r (a)$ . If $m_{a} > 0 = n_{a}$ for some $a$ , then $\Pr_{q^{\otimes n}} (T_{r}) = 0$ . Otherwise let $k_{a} = m_{a} - n_{a}$ for each $a$ with $n_{a} > 0$ . The ratio is $\frac{\Pr_{q^{\otimes n}} (T_{r})}{\Pr_{q^{\otimes n}} (T_{q})} = \frac{\prod_{a} n_{a}!}{\prod_{a} m_{a}!} \prod_{a : n_{a} > 0} {(\frac{n_{a}}{n})}^{k_{a}} .$ For $k_{a} \geq 0$ , the corresponding factor is at most $n^{- k_{a}}$ because $(n_{a} + 1) \dots (n_{a} + k_{a}) \geq n_{a}^{k_{a}}$ . For $k_{a} = - s_{a} < 0$ , it is at most $n^{s_{a}}$ because $n_{a} (n_{a} - 1) \dots (n_{a} - s_{a} + 1) \leq n_{a}^{s_{a}}$ . The equal-total-count relation gives $\sum_{k_{a} > 0} k_{a} = \sum_{k_{a} < 0} s_{a}$ , so the product of these bounds is at most one. Thus $T_{q}$ has maximum probability among all type classes under $q^{\otimes n}$ .

2.1F1F2step 1.2algebra∎

Each of the $m$ counts has at most $n + 1$ values, so there are at most $(n + 1)^{m}$ types. Their probabilities sum to one; since $T_{q}$ is a most probable type class by step 1.2, its probability is at least $(n + 1)^{- m}$ . Using $\Pr (T_{q}) = ∣ T_{q} ∣ \exp (- n H (q))$ proves the lower bound.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

Finite random-codebook covering and selected-codeword law

Statement

Let $P_{X U} = P_{X} P_{U ∣ X}$ be a joint law on finite nonempty alphabets, with marginal $P_{U}$ . Fix $η > 0$ and a target joint-typicality tolerance $ϵ > 0$ . There are a source-typicality tolerance $δ > 0$ and an integer $n_{0}$ such that, for every $n \geq n_{0}$ , every $x^{n} \in T_{δ}^{(n)} (P_{X})$ , and every $R > I (X; U) + η$ , an iid codebook of $M_{n} = ⌈ e^{n R} ⌉$ independent $P_{U}^{\otimes n}$ words contains a word in $T_{ϵ}^{(n)} (P_{X U} ∣ x^{n})$ with probability tending to one uniformly in $x^{n}$ . If the encoder selects the least index with a jointly typical word, then, conditional on a match, its selected word has law $P_{U}^{\otimes n}$ conditioned on $T_{ϵ}^{(n)} (P_{X U} ∣ x^{n})$ ; conditional on any particular joint type, this law is uniform on the associated conditional type class.

Facts & Assumptions

Given: A finite joint pmf $P_{X U}$ , its factorization $P_{X} P_{U ∣ X}$ , $η > 0$ , and the target tolerance $ϵ > 0$ .

[F1]

Finite strongly typical sets with support restriction: $T_{δ}^{(n)} (P)$ consists of support-restricted blocks whose empirical probabilities are within relative tolerance $δ$ of $P$ ; the conditional set is defined by joint typicality with the fixed block.

[F2]

Finite type-class cardinality bounds: for an attainable type $q$ on $m$ letters, $(n + 1)^{- m} e^{n H (q)} \leq ∣ T_{q} ∣ \leq e^{n H (q)}$ .

[F3]

Finite mutual information: $I (X; U) = D (P_{X U} ∥ P_{X} P_{U})$ , with natural logarithms and the finite support convention.

[F4]

Finite conditional entropy: $H (U ∣ X)$ is the finite average of $H (P_{U ∣ x})$ over positive-mass $x$ .

[F5]

Finite distributions, entropy, divergence, and stochastic matrices: $H (q) = - \sum_{a : q (a) > 0} q (a) \ln q (a)$ with $0 \ln 0 = 0$ .

Proof

1.1F1chooseconstruct

Let $ρ > 0$ be any desired relative accuracy for a constructed joint type. For each positive-mass $x$ , let $n_{x}$ be its count in $x^{n}$ . Choose $δ < 1 / 2$ ; then $n_{x} / n$ is within relative error $δ$ of $P_{X} (x)$ , so for all sufficiently large $n$ every such $n_{x}$ is positive and grows linearly in $n$ , uniformly over $x^{n} \in T_{δ}^{(n)} (P_{X})$ . For each row, take floors of $n_{x} P_{U ∣ X} (u ∣ x)$ on its positive conditional support and distribute the fewer than $∣ U ∣$ remaining counts among those entries; set zero-conditional-probability counts to zero. Every resulting count differs from its target by at most $∣ U ∣$ . As there are finitely many positive joint atoms, first choose $δ$ small and then $n$ large so that the joint type $q_{X U} (x, u) = (n_{x} / n) q_{U ∣ X} (u ∣ x)$ has relative error at most $ρ$ on every positive atom of $P_{X U}$ . Zero joint atoms receive zero counts. Thus the associated conditional type class is nonempty and its joint type lies in $T_{ρ}^{(n)} (P_{X U})$ .

2.1F2F3F4F5step 1.1algebra

The conditional type class from step 1.1 has at least $\prod_{x : P_{X} (x) > 0} (n_{x} + 1)^{- ∣ U ∣} \exp (n_{x} H (q_{U ∣ x}))$ words by [F2]. Every word in it has the same $P_{U}^{\otimes n}$ probability. Its marginal type $q_{U}$ is supported on $supp (P_{U})$ , and this probability is $\exp ⁣ (n \sum_{u : P_{U} (u) > 0} q_{U} (u) \ln P_{U} (u)) = \exp [- n (H (q_{U}) + D (q_{U} ∥ P_{U}))] .$ For any finite probability vector, each entropy summand $- t \ln t$ is continuous at zero because $t \ln t \to 0$ . The finite conditional-entropy sum expands as $H_{q} (U ∣ X) = - \sum_{x, u : q (x, u) > 0} q (x, u) \ln \frac{q (x, u)}{q_{X} (x)} = H (q_{X U}) - H (q_{X}) .$ On $supp (P_{U})$ , $D (r ∥ P_{U}) = \sum_{u : P_{U} (u) > 0} r (u) \ln r (u) - \sum_{u : P_{U} (u) > 0} r (u) \ln P_{U} (u),$ so $D (r ∥ P_{U})$ is continuous even when some $r (u) = 0$ . The displayed identity makes $H_{q} (U ∣ X)$ continuous in $q_{X U}$ . Consequently $Φ (q) : = H_{q} (U ∣ X) - H (q_{U}) - D (q_{U} ∥ P_{U})$ is continuous at $P_{X U}$ on the simplex of laws supported by $P_{X U}$ , including its boundary. Expanding the finite KL sum [F3] and the entropy formulas [F4]–[F5] gives $I (X; U) = H (U) - H (U ∣ X)$ , so $Φ (P_{X U}) = H (U ∣ X) - H (U) = - I (X; U)$ . Choose $ρ < ϵ$ small enough that $Φ (q) \geq - I (X; U) - η / 3$ whenever $q$ is within relative tolerance $ρ$ of $P_{X U}$ . The type-class bound and the product probability then give $p_{n} (x^{n}) \geq (n + 1)^{- ∣ X ∣ ∣ U ∣} \exp [- n (I (X; U) + η / 3)]$ uniformly over $x^{n} \in T_{δ}^{(n)} (P_{X})$ .

3.1givenstep 2.1algebra

By independence of the codewords, the probability that none of $M_{n}$ words lies in the conditional typical set is $(1 - p_{n} (x^{n}))^{M_{n}} \leq e^{- M_{n} p_{n} (x^{n})}$ . Choose the tolerances so that the exponent in step 2.1 leaves a positive gap below $R$ ; then $M_{n} p_{n} (x^{n}) \to \infty$ uniformly, and the no-match probability tends to zero.

4.1F1constructalgebra∎

For a fixed $x^{n}$ , let $A = T_{ϵ}^{(n)} (P_{X U} ∣ x^{n})$ . The event that index $ℓ$ is the first successful index depends on codewords before $ℓ$ failing and the $ℓ$ th codeword lying in $A$ ; those events are independent across codewords. Consequently, conditional on the first-success event at any $ℓ$ , the selected word has law $P_{U}^{\otimes n} (\cdot ∣ A)$ , and averaging over $ℓ$ gives the same conditional law given a match. On each joint type class inside $A$ , the marginal type of $U^{n}$ is fixed, so all its words have the same product probability; the conditional law is therefore uniform on that class.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

Finite joint-typicality packing bound for independent random bins

Statement

Fix $k \geq 1$ , finite alphabets $U_{1}, \dots, U_{k}, S$ , and a joint law $P_{U_{1} \dots U_{k} S}$ . Let the source-selection data $Z^{n}$ and decoder side-information block $S^{n}$ have any joint law. Independently of $(Z^{n}, S^{n})$ , generate mutually independent codebooks whose $M_{i}$ codewords each have law $P_{U_{i}}^{\otimes n}$ . Generate independent uniform bin labels from $[B_{i}]$ for every codeword, independently of the source and codebooks. Let the selected true indices $L_{i}$ be functions of $Z^{n}$ and codebooks but not the bin labels. In addition, for every nonempty proper $J \subset [k]$ , require the complementary selected codewords at indices in $J^{c}$ to be determined by $Z^{n}$ and codebooks indexed by $J^{c}$ alone; this condition is automatic when each terminal selects using its own codebook, and is vacuous for $k = 1$ . For a fixed positive typicality tolerance, a joint-typicality decoder looks for the unique tuple in the received bins whose codewords and $S^{n}$ are jointly typical for $P_{U_{1} \dots U_{k} S}$ . Suppose there is a common $η > 0$ such that for every nonempty $J \subseteq [k],$ $\sum_{i \in J} \frac{1}{n} \ln \frac{M_{i}}{B_{i}} < \sum_{i \in J} H (U_{i}) - H (U_{J} ∣ U_{J^{c}}, S) - η .$ Then there is $ϵ_{0} > 0$ such that, for every fixed typicality tolerance $0 < ϵ \leq ϵ_{0}$ , writing $E_{n}$ for the event that the selected true tuple and $S^{n}$ are jointly typical, the expected number of wrong jointly typical tuples in its received bins, multiplied by $1_{E_{n}}$ , tends to zero as $n \to \infty$ . Consequently the probability that $E_{n}$ holds and a wrong jointly typical tuple exists tends to zero. The case of no side information is represented by a singleton $S$ .

Facts & Assumptions

Given: The finite target law, a joint law of source-selection data and decoder side information independent of the codebooks, mutually independent marginal codebooks, and independent uniform bin labels.

[F1]

Finite strongly typical sets with support restriction: joint typicality is support-restricted relative empirical-frequency typicality.

[F2]

Finite type-class cardinality bounds: a type class on $m$ letters has at most $e^{n H (q)}$ elements, and the number of attainable types is at most $(n + 1)^{m}$ .

[F3]

Finite conditional entropy: $H (U_{J} ∣ U_{J^{c}}, S)$ is the weighted finite entropy of the conditional laws on positive-mass conditioning atoms.

[F4]

Finite distributions, entropy, divergence, and stochastic matrices: $H (q) = - \sum_{a : q (a) > 0} q (a) \ln q (a)$ with $0 \ln 0 = 0$ .

[F5]

Information units and logarithm-base convention: unmarked logarithms are natural and rates are measured in nats.

Proof

1.1F1F2F3F4choose

Fix a nonempty $J \subseteq [k]$ and a particular typical conditioning block $(u_{J^{c}}^{n}, s^{n})$ . For each attainable joint type of $(U_{J}, U_{J^{c}}, S)$ compatible with this block, the number of possible $u_{J}^{n}$ is a product of conditional type-class sizes, hence at most $\exp (n H_{q} (U_{J} ∣ U_{J^{c}}, S))$ by [F2]. There are at most $(n + 1)^{m}$ such types, where $m = ∣ S ∣ \prod_{i} ∣ U_{i} ∣$ . Expanding the finite conditional-entropy sum gives $H_{q} (U_{J} ∣ U_{J^{c}}, S) = - \sum_{u_{J}, u_{J^{c}}, s : q > 0} q (u_{J}, u_{J^{c}}, s) \ln \frac{q (u_{J}, u_{J^{c}}, s)}{q (u_{J^{c}}, s)} = H (q_{U_{J} U_{J^{c}} S}) - H (q_{U_{J^{c}} S}) .$ The finite entropy summands $- t \ln t$ extend continuously at zero, so this conditional entropy is continuous in the joint law. Choose the typicality tolerance small enough that every such type has $H_{q} (U_{J} ∣ U_{J^{c}}, S) \leq H (U_{J} ∣ U_{J^{c}}, S) + η / 3$ . Therefore the conditional-typical fan has at most $(n + 1)^{m} \exp (n (H (U_{J} ∣ U_{J^{c}}, S) + η / 3))$ candidates.

2.1F1F3F4F5step 1.1algebra

Every such candidate tuple has marginal types close to the target $P_{U_{i}}$ : summing the relative errors over the omitted coordinates shows that each positive marginal atom has relative error at most the joint typicality tolerance. For each $i$ , the function $q_{i} \mapsto \sum_{u_{i} : P_{U_{i}} (u_{i}) > 0} q_{i} (u_{i}) \ln P_{U_{i}} (u_{i})$ is a finite linear function, hence continuous even when some $q_{i} (u_{i}) = 0$ , and its value at $P_{U_{i}}$ is $- H (U_{i})$ . Zero-probability letters do not occur in a typical candidate by [F1]. Thus, when the tolerance is sufficiently small, the product-marginal probability of any fixed candidate tuple is at most $\exp [- n (\sum_{i \in J} H (U_{i}) - η / 3)]$ . Multiplying by the count in step 1.1 bounds the chance that a fresh independent marginal-codeword tuple is jointly typical with any fixed typical conditioning block by $(n + 1)^{m} \exp [- n (\sum_{i \in J} H (U_{i}) - H (U_{J} ∣ U_{J^{c}}, S) - 2 η / 3)]$ .

3.1F5givenstep 2.1constructalgebra

A wrong tuple differing from the true tuple on exactly $J$ uses at most $\prod_{i \in J} M_{i}$ candidate index combinations. For each combination, on the event that all changed indices differ from the selected indices, its bin labels collide with the true labels with probability $\prod_{i \in J} B_{i}^{- 1}$ : after source-selection data and codebooks fix the selected indices, the independent bin assignments give that probability. For every nonempty proper $J$ , the selection hypothesis makes the complementary selected block a function only of $Z^{n}$ and codebooks in $J^{c}$ ; because codebooks in $J$ are independent of $(Z^{n}, S^{n})$ and of the codebooks in $J^{c}$ , the pair consisting of the side-information block and complementary selected block is independent of the candidate changed codewords. If $J = [k]$ , the complement is just $S^{n}$ , which is independent of all codebooks by assumption, so the same independence holds without a selector restriction. The indicator of a typical true tuple is bounded by the indicator that its complementary block is typical; this latter block is independent of the changed codewords, so step 2.1 bounds candidate typicality. Dropping the additional indicator that candidate indices differ can only increase this probability. Thus the expected number of wrong tuples of this difference set, multiplied by the indicator of a typical true tuple, is at most $(n + 1)^{m} \exp [- n η / 3]$ under the displayed rate condition, using the natural-log rate convention [F5].

4.1givenstep 3.1algebra∎

There are finitely many nonempty subsets $J$ . Summing the bounds from step 3.1 over all of them still tends to zero because a polynomial factor is dominated by $e^{- n η / 3}$ . Markov's inequality then bounds the probability that the true tuple is typical and at least one wrong jointly typical tuple exists by the same vanishing expectation.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Markov typicality for independently selected finite codewords

Statement

Let $P_{X Y Z} (x, y, z) = P_{X Y} (x, y) P_{Z ∣ X} (z ∣ x)$ be a finite-alphabet Markov law. For every $ϵ > 0$ there are $δ > 0$ and $n_{0}$ such that the following holds for $n \geq n_{0}$ : if $(x^{n}, y^{n}) \in T_{δ}^{(n)} (P_{X Y})$ and a random $Z^{n}$ is supported on $T_{δ}^{(n)} (P_{Z ∣ X} ∣ x^{n})$ and, conditional on each joint type of $(x^{n}, Z^{n})$ , is uniform on that conditional type class, then $\Pr {(x^{n}, y^{n}, Z^{n}) \in T_{ϵ}^{(n)} (P_{X Y Z})} \geq 1 - \frac{C}{n},$ where $C < \infty$ depends only on the fixed finite law, alphabets, and $ϵ$ , not on the particular typical source block or conditional type.

Facts & Assumptions

Given: The finite Markov law, $ϵ > 0$ , a typical fixed source block $(x^{n}, y^{n})$ , and the stated conditional-type-uniform law of $Z^{n}$ .

[A1]

$P_{X Y Z} = P_{X Y} P_{Z ∣ X}$ : conditional on $X = x$ , the target law of $Z$ does not depend on $Y$ .

[F1]

Finite strongly typical sets with support restriction: relative typicality excludes every zero-probability atom and bounds each positive empirical frequency by its relative tolerance.

[F2]

Finite random-codebook covering and selected-codeword law: conditional on a successful iid marginal-codebook search, the selected codeword is supported on the conditional typical set and is uniform within each conditional type class.

Proof

1.1A1F1F2construct

Fix a conditional type $q_{Z ∣ X}$ that can occur under the stated law. For each $x$ with $n_{x} : = ∣ {t : x_{t} = x} ∣ > 0$ , there are $n_{x y}$ positions with $(x_{t}, y_{t}) = (x, y)$ and $n_{x z}$ positions with $(x_{t}, Z_{t}) = (x, z)$ . Conditional-type uniformity means that, among the $n_{x}$ positions with $X = x$ , the $z$ labels are assigned uniformly over all arrangements with these counts. Hence $N_{x y z} : = ∣ {t : (x_{t}, y_{t}, Z_{t}) = (x, y, z)} ∣$ is hypergeometric, with $E N_{x y z} = \frac{n_{x y} n_{x z}}{n_{x}}, Var (N_{x y z}) \leq n_{x} .$ When $n_{x} = 0$ , all these counts vanish.

2.1A1F1step 1.1algebra

By [F1], $n_{x y} / n$ and $n_{x z} / n$ are uniformly close to $P_{X Y} (x, y)$ and $P_{X Z} (x, z)$ , respectively. For $P_{X} (x) > 0$ , division by $n_{x} / n$ shows that $n_{x z} / n_{x}$ is close to $P_{Z ∣ X} (z ∣ x)$ . Thus, after choosing $δ$ sufficiently small, the mean frequency $E N_{x y z} / n = (n_{x y} / n) (n_{x z} / n_{x})$ is within half the required relative tolerance of $P_{X Y Z} (x, y, z)$ for every positive-probability triple. If $P_{X Y Z} (x, y, z) = 0$ , either $(x, y)$ is excluded by the source support condition or $(x, z)$ is excluded by the conditional support condition, so $N_{x y z} = 0$ .

3.1F1step 1.1step 2.1algebra∎

For a positive-probability triple, Chebyshev's inequality and step 1.1 give $\Pr {∣ N_{x y z} - E N_{x y z} ∣ > \frac{1}{2} n ϵ P_{X Y Z} (x, y, z)} \leq \frac{4 n_{x}}{n^{2} ϵ^{2} P_{X Y Z} (x, y, z)^{2}} \leq \frac{4}{n ϵ^{2} P_{X Y Z} (x, y, z)^{2}} .$ There are finitely many triples. A union bound makes the probability that any empirical triple frequency misses its required tolerance at most $C / n$ for a finite constant $C$ depending only on the law, alphabets, and $ϵ$ . This bound is uniform in every admissible conditional type, so it remains valid after mixing over the conditional-type distribution of $Z^{n}$ . The complement event is exactly strong typicality of $(x^{n}, y^{n}, Z^{n})$ , proving the claim.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite-alphabet lossy source coding with decoder-only side information

Definition

Let $(X_{t}, Y_{t})_{t \geq 1}$ be an IID pair with joint pmf $P_{X Y}$ on finite nonempty alphabets $X \times Y$ , as the $k = 2$ instance of Finite-alphabet IID multisource. Let $\hat{X}$ be finite nonempty and let $d : X \times \hat{X} \to [0, d_{\max}]$ be the finite bounded single-letter distortion from Single-letter and block distortion. For $x^{n} = (x_{1}, \dots, x_{n})$ and ${\hat{x}}^{n} = ({\hat{x}}_{1}, \dots, {\hat{x}}_{n})$ , define

$d_{n} (x^{n}, {\hat{x}}^{n}) : = \frac{1}{n} \sum_{t = 1}^{n} d (x_{t}, {\hat{x}}_{t}) .$

A length- $n$ , $M$ -message Wyner-Ziv code consists of a deterministic encoder $f_{n} : X^{n} \to [M]$ and deterministic decoder $g_{n} : [M] \times Y^{n} \to {\hat{X}}^{n}$ . The encoder observes only $X^{n}$ ; the decoder observes both the message and $Y^{n}$ . Its rate is $n^{- 1} \ln M$ nats per source symbol, and its expected distortion is $E [d_{n} (X^{n}, g_{n} (f_{n} (X^{n}), Y^{n}))]$ .

A pair $(R, D)$ is operationally achievable if there are increasing blocklengths $n_{j} \to \infty$ and such codes with ${lim sup}_{j} n_{j}^{- 1} \ln M_{j} \leq R$ and ${lim sup}_{j} E [d_{n_{j}}] \leq D$ . Define $R_{W Z}^{o p} (D)$ as the infimum of achievable rates.

For a finite auxiliary alphabet $U$ , a test channel is a stochastic kernel $P_{U ∣ X}$ together with a deterministic map $g : Y \times U \to \hat{X}$ , under the joint law $P_{X Y U} = P_{X Y} P_{U ∣ X}$ . It has $U - X - Y$ , expected distortion $E [d (X, g (Y, U))]$ , and conditional mutual information $I (X; U ∣ Y)$ from Finite conditional mutual information. Define the single-letter candidate $R_{W Z} (D) : = \inf_{\begin{array}{c} U f i n i t e, P_{U ∣ X}, g \\ E [d (X, g (Y, U))] \leq D \end{array}} I (X; U ∣ Y),$ with value $+ \infty$ if the feasible set is empty. This definition alone makes no operational equality claim; the following theorem proves it and the cardinality lemma makes the finite minimum explicit.

Remarks

Every reproduction has distortion at least $D_{\min} : = E [\min_{\hat{x} \in \hat{X}} d (X, \hat{x})]$ , and the finite alphabet allows $U = X$ with a fixed pointwise minimizer to attain it. The zero-rate distortion is $D_{\max} : = \min_{h : Y \to \hat{X}} E [d (X, h (Y))]$ ; there are finitely many maps $h$ , and a constant auxiliary with a minimizing $h$ attains it. The block code has only the encoder and decoder interfaces displayed in the statement; there is no encoder-side observation of $Y^{n}$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite-alphabet multiterminal lossy source code

Definition

Fix $k \geq 2$ and a finite IID source vector $(X_{1, t}, \dots, X_{k, t})_{t \geq 1}$ with law $P_{X_{1} \dots X_{k}}$ , as in Finite-alphabet IID multisource. For each $i$ , let ${\hat{X}}_{i}$ be a finite nonempty reproduction alphabet and let $d_{i} : X_{i} \times {\hat{X}}_{i} \to [0, d_{i, \max}]$ be finite and bounded.

A length- $n$ fixed-length multiterminal lossy code consists of separate deterministic encoders $f_{i, n} : X_{i}^{n} \to [M_{i}] (1 \leq i \leq k)$ and one deterministic common decoder $g_{n} : \prod_{i = 1}^{k} [M_{i}] \to \prod_{i = 1}^{k} {\hat{X}}_{i}^{n} .$ Write ${\hat{X}}_{i}^{n}$ for the $i$ th reconstruction and define its expected per-letter distortion by $Δ_{i, n} : = E [n^{- 1} \sum_{t = 1}^{n} d_{i} (X_{i, t}, {\hat{X}}_{i, t})]$ . Encoder $i$ has rate $n^{- 1} \ln M_{i}$ nats per source symbol. A vector $(R_{1}, \dots, R_{k})$ is achievable at distortions $(D_{1}, \dots, D_{k})$ when there is an increasing sequence of blocklengths with each rate limsup at most $R_{i}$ and each distortion limsup at most $D_{i}$ . The operational rate-distortion region is the closure of these achievable vectors.

Remarks

No encoder observes another encoder's source block. The common decoder receives all message indices and outputs one reconstruction sequence for each source.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Cardinality bound for the finite Wyner-Ziv auxiliary

Statement

Let $P_{X Y}$ be a finite joint law, let $d : X \times \hat{X} \to [0, d_{\max}]$ , and let $(U, P_{U ∣ X}, g)$ be any finite Wyner-Ziv test channel from Finite-alphabet lossy source coding with decoder-only side information with expected distortion at most $D$ . There is another finite test channel $(U^{'}, P_{U^{'} ∣ X}, g^{'})$ such that $∣ U^{'} ∣ \leq ∣ X ∣ + 1, E [d (X, g^{'} (Y, U^{'}))] = E [d (X, g (Y, U))], I (X; U^{'} ∣ Y) \leq I (X; U ∣ Y) .$ Consequently the infimum $R_{W Z} (D)$ in Finite-alphabet lossy source coding with decoder-only side information is a minimum and it suffices to optimize over $∣ U ∣ \leq ∣ X ∣ + 1$ .

Facts & Assumptions

Given: A finite law $P_{X Y}$ , a finite distortion, a finite test channel, and $D$ .

[F1]

Finite-alphabet lossy source coding with decoder-only side information: a test channel has $P_{X Y U} = P_{X Y} P_{U ∣ X}$ , a decoder map $g (Y, U)$ , and distortion $E [d (X, g (Y, U))]$ .

[F2]

Finite entropy and mutual-information chain rules: $I (X; U ∣ Y) = H (X ∣ Y) - H (X ∣ U, Y)$ for finite random variables.

[F3]

Finite distributions, entropy, divergence, and stochastic matrices: finite entropy uses $0 \ln 0 = 0$ and is continuous on each finite probability simplex because $- t \ln t$ extends continuously at $0$ .

[F4]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: a closed bounded subset of finite-dimensional Euclidean space is compact.

[F5]

A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value: a continuous real-valued function on a nonempty compact space attains its minimum.

Proof

1.1F1given

Remove all zero-probability values of $U$ . For each remaining $u$ , set $π_{u} = P_{U} (u) > 0$ , $q_{u} (x) = P (X = x ∣ U = u)$ , $a_{u} = E [d (X, g (Y, u)) ∣ U = u]$ , and $h_{u} = H (X ∣ Y, U = u)$ . Because $U - X - Y$ , the conditional law of $Y$ given $(X, U)$ is $P_{Y ∣ X}$ , so $a_{u}$ is determined by $q_{u}$ and the fixed decoder map $g (\cdot, u)$ . Also, $P_{X} (x) = \sum_{u} π_{u} q_{u} (x), E d (X, g (Y, U)) = \sum_{u} π_{u} a_{u}, H (X ∣ Y, U) = \sum_{u} π_{u} h_{u} .$ These are finite sums.

1.2F1choosealgebra

Put $m = ∣ X ∣$ . If there are more than $m + 1$ positive weights, the vectors $v_{u} = (q_{u} (x_{1}), \dots, q_{u} (x_{m}), a_{u}) \in R^{m + 1}$ are linearly dependent. Choose coefficients $c_{u}$ , not all zero, with $\sum_{u} c_{u} v_{u} = 0$ . The first $m$ coordinates imply $\sum_{u} c_{u} = 0$ , so the coefficients have both signs. Choose the sign so that $\sum_{u} c_{u} h_{u} \geq 0$ . Let $t = \min_{c_{u} < 0} π_{u} / (- c_{u}) > 0$ and put $π_{u}^{'} = π_{u} + t c_{u}$ . Then every $π_{u}^{'} \geq 0$ , at least one is zero, and the source marginal and expected distortion remain unchanged, while $\sum_{u} π_{u}^{'} h_{u} \geq \sum_{u} π_{u} h_{u}$ .

2.1F1F2step 1.2algebra

Define $U^{'}$ to have the remaining positive weights $π_{u}^{'}$ , conditional posterior $P (X = x ∣ U^{'} = u) = q_{u} (x)$ , and conditional side-information law $P_{Y ∣ X}$ . Equivalently set $P_{X Y U^{'}} (x, y, u) = P_{X Y} (x, y) P (U^{'} = u ∣ X = x)$ with $P (U^{'} = u ∣ X = x) : = π_{u}^{'} q_{u} (x) / P_{X} (x)$ for $P_{X} (x) > 0$ , and choose any row on zero-mass $x$ . The source marginal is preserved by step 1.2, and $\sum_{u} π_{u}^{'} q_{u} (x) = P_{X} (x)$ makes each conditional row sum to one. Use the same reconstruction map $g (y, u)$ . The distortion is unchanged by step 1.2, and [F2] gives $I (X; U^{'} ∣ Y) = H (X ∣ Y) - \sum_{u} π_{u}^{'} h_{u} \leq H (X ∣ Y) - \sum_{u} π_{u} h_{u} = I (X; U ∣ Y) .$ At least one positive auxiliary value was removed. Repeating finitely many times leaves at most $m + 1$ values and never increases the objective.

3.1F1F3F4F5step 1.2step 2.1∎

For fixed $∣ U ∣ = m + 1$ , the stochastic matrices $P_{U ∣ X}$ form a closed bounded subset of a finite-dimensional Euclidean space. Any smaller auxiliary can be embedded in this alphabet by adding zero-probability labels and assigning arbitrary decoder values to them. For each of the finitely many decoder maps $g : Y \times U \to \hat{X}$ , the distortion constraint is closed and $I (X; U ∣ Y)$ is continuous by the finite entropy formulas and [F3]. Thus every nonempty feasible set is compact by [F4], and its objective minimum is attained by [F5]. Every finite auxiliary can be reduced to at most $m + 1$ labels by steps 1.2–2.1 and then embedded in this fixed alphabet, so this minimum equals the original infimum.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Convexity, monotonicity, and continuity of finite Wyner-Ziv rate

Statement

Let $R_{W Z} (D)$ , $D_{\min}$ , and $D_{\max}$ be as in Finite-alphabet lossy source coding with decoder-only side information. Then $D_{\min} \leq D_{\max}$ , $R_{W Z}$ is nonincreasing and convex on $[D_{\min}, \infty)$ , $R_{W Z} (D) = 0$ for $D \geq D_{\max}$ , and $R_{W Z}$ is continuous at every feasible distortion, including $D_{\min}$ and $D_{\max}$ .

Facts & Assumptions

Given: The finite source law, bounded distortion, and the candidate single-letter function in the Definition.

[F1]

Finite-alphabet lossy source coding with decoder-only side information: $D_{\min} = E [\min_{\hat{x}} d (X, \hat{x})]$ , $D_{\max} = \min_{h : Y \to \hat{X}} E [d (X, h (Y))]$ , and $R_{W Z} (D)$ is the infimum over finite $U - X - Y$ test channels and deterministic maps $g (Y, U)$ .

[F2]

Cardinality bound for the finite Wyner-Ziv auxiliary: every feasible test channel can be replaced without increasing $I (X; U ∣ Y)$ by one with $∣ U ∣ \leq ∣ X ∣ + 1$ , and the minimum is attained.

[F3]

Finite entropy and mutual-information chain rules: for finite variables, $I (X; U ∣ Y) = H (X ∣ Y) - H (X ∣ U, Y)$ and all terms are finite.

[F4]

Finite distributions, entropy, divergence, and stochastic matrices: entropy is a finite sum of terms $- p \ln p$ , with $0 \ln 0 = 0$ .

[F5]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: the closed channel simplexes for a fixed finite auxiliary alphabet are compact subsets of a finite-dimensional Euclidean space.

Proof

1.1F1F4algebra

For any map $h : Y \to \hat{X}$ and every $(x, y)$ , $d (x, h (y)) \geq \min_{\hat{x}} d (x, \hat{x})$ ; minimizing over the finite set of maps gives $D_{\min} \leq D_{\max}$ . The feasible test-channel sets are nested as $D$ increases, so their infima are nonincreasing. For $s > 0$ , $\ln s \leq s - 1$ because $s - 1 - \ln s$ has derivative $1 - 1 / s$ and minimum $0$ at $s = 1$ . Thus, for pmfs $p, q$ , either $D (p ∥ q) = + \infty$ when $p_{i} > 0 = q_{i}$ for some $i$ , or $D (p ∥ q) \geq \sum_{i : p_{i} > 0} (p_{i} - q_{i}) = 1 - \sum_{i : p_{i} > 0} q_{i} \geq 0$ . By [F1] and [F4], each conditional mutual information is a positive weighted sum of such divergences, so every feasible objective is nonnegative. A constant auxiliary $U$ and a minimizing map $h$ at $D_{\max}$ have objective zero and distortion $D_{\max}$ , proving $R_{W Z} (D) = 0$ for $D \geq D_{\max}$ .

1.2F1F2F3chooseconstruct

Let $D_{1}, D_{2} \geq D_{\min}$ and $0 \leq λ \leq 1$ . By [F2], choose minimizing channels $(U_{1}, g_{1})$ and $(U_{2}, g_{2})$ , whose distortions $d_{1}, d_{2}$ satisfy $d_{j} \leq D_{j}$ . Let an independent finite $Q$ select branch 1 with probability $λ$ , set $U = (Q, U_{Q})$ , and use $g (Y, U) = g_{Q} (Y, U_{Q})$ . Then $U - X - Y$ , the distortion $λ d_{1} + (1 - λ) d_{2}$ is at most $λ D_{1} + (1 - λ) D_{2}$ , and the finite conditional chain rule gives $I (X; U ∣ Y) = I (X; Q ∣ Y) + I (X; U_{Q} ∣ Y, Q) = λ R_{W Z} (D_{1}) + (1 - λ) R_{W Z} (D_{2})$ because $Q$ is independent of $(X, Y)$ . Applying [F2] to reduce $U$ if necessary proves convexity.

2.1F1F2F3F4F5step 1.1algebra

On the interior of $[D_{\min}, D_{\max}]$ , write $s (a, b) = (R_{W Z} (b) - R_{W Z} (a)) / (b - a)$ . Convexity implies $s (a, b) \leq s (b, c)$ whenever $a < b < c$ , by writing $b$ as a convex combination of $a, c$ . For $D_{-} < z < D$ , this gives $s (D_{-}, z) \leq s (z, D)$ , hence $R_{W Z} (z) \leq \frac{D - z}{D - D_{-}} R_{W Z} (D_{-}) + \frac{z - D_{-}}{D - D_{-}} R_{W Z} (D)$ ; the right side tends to $R_{W Z} (D)$ as $z ↑ D$ , while monotonicity gives $R_{W Z} (z) \geq R_{W Z} (D)$ . For $D < z < D_{+}$ , the inequalities $s (D_{-}, D) \leq s (D, z) \leq s (z, D_{+})$ bound $R_{W Z} (z)$ between two linear interpolations that both tend to $R_{W Z} (D)$ as $z ↓ D$ . This proves continuity at $D$ . For right continuity at $D_{\min} < D_{\max}$ , let $r < R_{W Z} (D_{\min})$ and let $K_{j}$ be the set of channels with $∣ U ∣ = ∣ X ∣ + 1$ and decoder maps whose distortion is at most $D_{\min} + 1 / j$ and whose objective is at most $r$ . The union of the finitely many channel simplexes over decoder maps is compact by [F5]: each simplex is closed and bounded in a finite-dimensional Euclidean space, and a finite union of compact sets is compact. For $0 < t \leq 1$ , $0 \leq - t \ln t = t \ln (1 / t) = t \int_{1}^{1 / t} \frac{d u}{u} \leq t \int_{1}^{1 / t} \frac{d u}{\sqrt{u}} \leq 2 \sqrt{t}$ , so $- t \ln t$ extends continuously to $0$ ; hence each finite entropy sum is continuous in its probability coordinates. By [F3], $I (X; U ∣ Y) = H (X, Y) + H (U, Y) - H (Y) - H (X, U, Y)$ . Each joint law in this expression depends linearly on the channel entries, and its entropy is continuous by the preceding limit, so the objective is continuous; for each fixed decoder map the expected distortion is also a finite linear function of the channel entries. Therefore each $K_{j}$ is closed. If every $K_{j}$ were nonempty, they would be nested closed subsets of this compact space with the finite intersection property: if their total intersection were empty, their open complements would cover the compact space and a finite subcover would force one $K_{j}$ empty. Thus their intersection is nonempty, yielding a channel feasible at $D_{\min}$ with objective at most $r$ , contrary to $r < R_{W Z} (D_{\min})$ . It follows that $R_{W Z} (D) > r$ on some right neighborhood of $D_{\min}$ ; since $R_{W Z} (D) \leq R_{W Z} (D_{\min})$ by monotonicity, right continuity follows.

3.1F1step 1.1step 2.1algebra∎

For $D_{\min} \leq D \leq D_{\max}$ with $D_{\min} < D_{\max}$ , time-share a minimum-distortion channel at $D_{\min}$ with the zero-rate channel at $D_{\max}$ . This gives $R_{W Z} (D) \leq \frac{D_{\max} - D}{D_{\max} - D_{\min}} R_{W Z} (D_{\min})$ , so $R_{W Z} (D) \to 0$ as $D ↑ D_{\max}$ . Nonnegativity and the zero-rate branch in step 1.1 prove continuity there. If $D_{\min} = D_{\max}$ , the zero-rate channel already attains the minimum distortion, so the feasible function is identically zero. For $D < D_{\min}$ , every test channel has distortion at least $D_{\min}$ , so the feasible set is empty and $R_{W Z} (D) = + \infty$ by Definition; for $D \geq D_{\max}$ , step 1.1 gives zero.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Finite-alphabet Berger-Tung multiterminal lossy inner bound

Statement

Fix a finite IID $k$ -source with $k \geq 2$ , per-terminal finite reproduction alphabets, and bounded distortions $d_{i}$ as in Finite-alphabet multiterminal lossy source code. Choose finite auxiliary alphabets $U_{i}$ , product test channels $P_{X_{1} \dots X_{k} U_{1} \dots U_{k}} = P_{X_{1} \dots X_{k}} \prod_{i = 1}^{k} P_{U_{i} ∣ X_{i}},$ and deterministic reconstruction maps $g_{i} : \prod_{j = 1}^{k} U_{j} \to {\hat{X}}_{i}$ whose expected distortions are at most $D_{i}$ . For each nonempty $S \subseteq [k]$ , write $X_{S} = (X_{i})_{i \in S}$ , $U_{S} = (U_{i})_{i \in S}$ , and $S^{c} = [k] ∖ S$ ; when $S = [k]$ , $U_{S^{c}}$ is a constant singleton. Then every nonnegative rate vector satisfying $\sum_{i \in S} R_{i} \geq I (X_{S}; U_{S} ∣ U_{S^{c}}) for every nonempty S \subseteq [k]$ is achievable at distortions $(D_{1}, \dots, D_{k})$ . The convex hull of the union of these finite-auxiliary rate regions, over all such product test channels and reconstruction maps, is the finite-alphabet Berger-Tung inner bound and is achievable. This theorem does not assert that the inner bound is the exact general multiterminal lossy rate region.

Facts & Assumptions

Given: A finite IID $k$ -source, a finite product test channel, finite reconstruction maps, bounded per-terminal distortions, and rates satisfying the displayed subset inequalities.

[F1]

Finite-alphabet multiterminal lossy source code: encoders observe only their own source blocks, the common decoder receives all indices, and each distortion is an expected normalized additive distortion.

[F2]

Finite-alphabet IID multisource: the vector source block law is $P_{X_{1} \dots X_{k}}^{\otimes n}$ .

[F3]

Jointly typical blocks for a finite IID multisource and Joint typicality probability tends to one for a finite IID multisource: with probability tending to one, the empirical type of the source block is within any fixed positive tolerance of its finite joint law and excludes zero-probability letters.

[F4]

Finite mutual information: finite mutual information is joint-law KL, equivalently $I (X_{i}; U_{i}) = H (U_{i}) - H (U_{i} ∣ X_{i})$ by the finite entropy chain rule.

[F5]

Finite conditional mutual information: $I (X_{S}; U_{S} ∣ U_{S^{c}})$ is the finite conditional-product KL.

[F6]

Finite conditional mutual information identities and equality: $I (A; B ∣ C) = H (B ∣ C) - H (B ∣ A, C)$ for finite variables.

[F7]

Finite entropy and mutual-information chain rules: finite entropy chain rules hold and all quantities are finite.

[F8]

Finite random-codebook covering and selected-codeword law: for each target joint-typicality tolerance, encoder $i$ 's marginal codebook at rate above $I (X_{i}; U_{i})$ contains a codeword in the corresponding conditional typical set, uniformly over source blocks at a sufficiently small source-typicality tolerance; conditional on success, its law is uniform within each conditional type class.

[F9]

Markov typicality for independently selected finite codewords: conditional on successful separate selections, sequentially adjoining auxiliaries through their product test channels preserves joint typicality.

[F10]

Finite joint-typicality packing bound for independent random bins: for mutually independent marginal codebooks generated independently of the source, separately selected true indices, and bin labels independent of both, the expected number of false jointly typical tuples on the event that the true tuple is typical vanishes when every changed-subset codebook-to-bin ratio is below its conditional-entropy exponent; the decoder-only auxiliary test is the singleton-side-information case.

Proof

1.1F1F2F8construct

First fix one product test channel and reconstruction tuple. For each encoder $i$ , choose ${\tilde{R}}_{i} = I (X_{i}; U_{i}) + α / 4$ with $α > 0$ , generate $M_{i} = ⌈ e^{n {\tilde{R}}_{i}} ⌉$ 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} = ⌈ e^{n (R_{i} + α)} ⌉$ bins. If no typical codeword exists, it selects index 1.

1.2F1F2F3F8F9chooseconstruct

Fix a final relative typicality tolerance $τ_{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 $τ_{i}$ to obtain an input tolerance $δ_{i} > 0$ , then apply [F8] with target conditional tolerance $δ_{i}$ to obtain a source tolerance $σ_{i} > 0$ , and choose $0 < τ_{i - 1} \leq \min (δ_{i}, σ_{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_{τ_{0}}^{(n)} (P_{X_{1} \dots 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_{τ_{i - 1}}$ for its target law, projection shows that $(X_{i}^{n}, all other source blocks and U_{1}^{n}, \dots, U_{i - 1}^{n})$ is $δ_{i}$ -typical and that $X_{i}^{n}$ is $σ_{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} - (the other sources and previous auxiliaries)$ , so [F9] puts the enlarged tuple in $T_{τ_{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.

2.1F4F5F6F7F10step 1.2algebra

The decoder searches for a unique tuple of codewords in the received bins whose auxiliary sequences are jointly typical according to $P_{U_{1} \dots 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} - α) < \sum_{i \in S} H (U_{i}) - H (U_{S} ∣ U_{S^{c}}) - η$ for some $η > 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} ∣ U_{S^{c}}) = H (U_{S} ∣ U_{S^{c}}) - \sum_{i \in S} H (U_{i} ∣ 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} ∣ U_{S^{c}}) = \sum_{i \in S} H (U_{i}) - H (U_{S} ∣ U_{S^{c}}) .$ The ceiling inequalities $M_{i} \leq 2 e^{n {\tilde{R}}_{i}}$ and $B_{i} \geq e^{n (R_{i} + α)}$ give $n^{- 1} \ln (M_{i} / B_{i}) \leq I (X_{i}; U_{i}) - R_{i} - 3 α / 4 + n^{- 1} \ln 2$ . For all sufficiently large $n$ , this is at most $I (X_{i}; U_{i}) - R_{i} - α / 2$ . The assumed subset inequality and the preceding entropy identity then leave at least $∣ S ∣ α / 2$ of margin for every nonempty $S$ ; taking the packing slack $η = α / 3$ makes the strict hypothesis of [F10] hold for every subset.

3.1F1step 1.2step 2.1F10choosealgebra

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} ∣ \hat{P} (a) - P (a) ∣ \leq τ_{k} \sum_{a : P (a) > 0} P (a) = τ_{k}$ ; hence every empirical distortion differs from its test-channel expectation by at most $d_{i, \max} τ_{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} τ_{k} + d_{i, \max} p_{n}$ . Let $α, τ_{k} ↓ 0$ along increasing blocklengths to attain the closed subset inequalities.

4.1F1step 3.1constructalgebra∎

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 / 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.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Finite-alphabet memoryless Wyner-Ziv theorem

Statement

Let $(X_{t}, Y_{t})_{t \geq 1}$ be IID on finite alphabets $X \times Y$ , let $\hat{X}$ be finite, and let $d : X \times \hat{X} \to [0, d_{\max}]$ be a bounded distortion independent of $Y$ . With decoder-only side information and the operational convention of Finite-alphabet lossy source coding with decoder-only side information, $R_{W Z}^{o p} (D) = R_{W Z} (D) = \min_{\begin{array}{c} ∣ U ∣ \leq ∣ X ∣ + 1, P_{U ∣ X}, g : Y \times U \to \hat{X} \\ U - X - Y, E d (X, g (Y, U)) \leq D \end{array}} I (X; U ∣ Y)$ for every $D \geq D_{\min}$ . For $D < D_{\min}$ no code can attain the distortion. The stated single-encoder formula is exact; the multiterminal lossy statement proved separately on this page is only an inner bound.

Facts & Assumptions

Given: The finite IID pair source, bounded finite distortion, decoder-only side information, and a feasible distortion level $D$ .

[F1]

Finite-alphabet lossy source coding with decoder-only side information: the encoder is $f_{n} (X^{n})$ , the decoder is $g_{n} (f_{n} (X^{n}), Y^{n})$ , block distortion is normalized additive, and $R_{W Z} (D)$ is the infimum of $I (X; U ∣ Y)$ over finite $U - X - Y$ with $\hat{X} = g (Y, U)$ .

[F2]

Finite-alphabet IID multisource: the pair $(X_{t}, Y_{t})$ is IID, so its block law is $P_{X Y}^{\otimes n}$ and different coordinate pairs are independent.

[F3]

Finite conditional mutual information: $I (A; B ∣ C)$ is the finite weighted sum of conditional KL divergences; it is finite.

[F4]

Finite entropy and mutual-information chain rules: finite entropy and information chain rules hold, including $I (A; B, C) = I (A; C) + I (A; B ∣ C)$ .

[F5]

Finite conditional mutual information identities and equality: $I (A; B ∣ C) = H (A ∣ C) - H (A ∣ B, C)$ and is nonnegative.

[F6]

Cardinality bound for the finite Wyner-Ziv auxiliary: every feasible finite test channel reduces to $∣ U ∣ \leq ∣ X ∣ + 1$ without changing distortion or increasing conditional mutual information; the minimum is attained.

[F7]

Convexity, monotonicity, and continuity of finite Wyner-Ziv rate: $R_{W Z}$ is nonincreasing and continuous on the feasible distortion interval.

[F8]

Finite random-codebook covering and selected-codeword law: for any target conditional typicality tolerance, if $\tilde{R} > I (X; U)$ then a finite iid $P_{U}$ codebook contains a word in the corresponding conditional typical set with probability tending to one uniformly over $X^{n}$ blocks at a sufficiently small source-typicality tolerance; conditioned on success, selection is conditional-type uniform.

[F9]

Markov typicality for independently selected finite codewords: for $U - X - Y$ , a selected codeword of the law in [F8] is jointly typical with $(X^{n}, Y^{n})$ whenever the source pair is typical, with probability tending to one.

[F10]

Finite joint-typicality packing bound for independent random bins: with one codebook independent of the source pair, selection data $(X^{n}, Y^{n})$ and decoder side information $Y^{n}$ , wrong typical codewords in the selected bin vanish when $\tilde{R} - R < I (U; Y)$ ; the complementary-selection restriction is vacuous for one codebook.

[F11]

Jointly typical blocks for a finite IID multisource and Joint typicality probability tends to one for a finite IID multisource: for every positive tolerance, the IID pair block is in the supplier's support-restricted jointly typical set with probability tending to one; choosing its empirical tolerance below $δ \min_{P_{X Y} (x, y) > 0} P_{X Y} (x, y)$ implies membership in $T_{δ}^{(n)} (P_{X Y})$ .

[F12]

Finite distributions, entropy, divergence, and stochastic matrices: finite entropy uses $0 \ln 0 = 0$ and finite conditional entropy sums omit zero-mass conditioning values.

[F13]

Finite KL divergence is nonnegative with equality exactly at equal laws: for finite probability vectors $p, q$ , $D (p ∥ q) \geq 0$ .

Proof

1.1F1F5F12F13algebra

Fix a length- $n$ code, put $W = f_{n} (X^{n})$ , and write ${\hat{X}}_{i}$ for the $i$ th decoder output. Let $u_{M}$ be uniform on $[M]$ . By [F13], $0 \leq D (P_{W} ∥ u_{M}) = \sum_{w : P_{W} (w) > 0} P_{W} (w) \ln \frac{P_{W} (w)}{1 / M} = \ln M - H (W),$ so $\ln M \geq H (W)$ . The conditional-mutual-information identity and nonnegativity in [F5] give $H (W) - H (W ∣ Y^{n}) = I (W; Y^{n}) \geq 0$ and $I (X^{n}; W ∣ Y^{n}) = H (W ∣ Y^{n}) - H (W ∣ X^{n}, Y^{n}) \leq H (W ∣ Y^{n}),$ because conditional entropy is nonnegative by its finite-sum definition [F12]. Combining these inequalities gives $\ln M \geq H (W) \geq H (W ∣ Y^{n}) \geq I (X^{n}; W ∣ Y^{n})$ .

1.2F1F3F4F5F6choose

By [F6], choose a minimizing finite test channel $(U, P_{U ∣ X}, g)$ with $∣ U ∣ \leq ∣ X ∣ + 1$ and expected distortion at most $D$ . Choose a codebook rate $\tilde{R} > I (X; U)$ and a bin rate $R > I (X; U ∣ Y)$ so that $s : = I (U; Y) - (\tilde{R} - R) > 0$ ; this is possible because the test-channel factorization in [F1] gives $I (U; Y ∣ X) = 0$ by [F3], and the chain rule [F4]–[F5] yields $I (X; U ∣ Y) = I (X; U) - I (U; Y)$ . Put $η = s / 2$ and fix a final joint-typicality tolerance $ϵ > 0$ small enough for [F10] with slack $η$ and for the bounded-distortion estimate, with error $ω (ϵ) \to 0$ as $ϵ ↓ 0$ .

1.3F1F8constructF9

Generate $M_{n} = ⌈ e^{n \tilde{R}} ⌉$ independent codewords with law $P_{U}^{\otimes n}$ and assign each codeword an independent uniform bin label in $[B_{n}]$ , where $B_{n} = ⌈ e^{n R} ⌉$ . On a source block $x^{n}$ , the encoder chooses the first codeword in the conditional typical set with the source/conditional tolerances chosen below from [F8]–[F9] and sends its bin; if none exists, it sends the first bin. Given $(m, y^{n})$ , the decoder finds the unique codeword in bin $m$ jointly typical with $y^{n}$ at tolerance $ϵ$ and applies $g$ coordinatewise, defaulting to a fixed reproduction block if uniqueness fails. These are finite code ensembles and deterministic maps once a realization is fixed.

2.1F2F3F4step 1.1algebra

Let $Y^{- i}$ denote all side-information coordinates except $Y_{i}$ and define $U_{i} = (W, Y^{- i})$ . Memorylessness gives $H (X^{n} ∣ Y^{n}) = \sum_{i} H (X_{i} ∣ Y_{i})$ , while the conditional entropy chain rule gives $H (X^{n} ∣ W, Y^{n}) = \sum_{i} H (X_{i} ∣ X^{i - 1}, W, Y^{n}) \leq \sum_{i} H (X_{i} ∣ W, Y^{n})$ . Subtracting yields $I (X^{n}; W ∣ Y^{n}) \geq \sum_{i = 1}^{n} I (X_{i}; W, Y^{- i} ∣ Y_{i}) = \sum_{i = 1}^{n} I (X_{i}; U_{i} ∣ Y_{i}) .$ Each $U_{i} - X_{i} - Y_{i}$ : conditional on $X_{i}$ , the independent pair $(X_{i}, Y_{i})$ is independent of all other source pairs, and $W, Y^{- i}$ are functions of $X^{n}, Y^{- i}$ .

2.2F8F9F11step 1.3

Apply [F9] with output tolerance $ϵ$ from step 1.2 to obtain its input tolerance $δ_{M}$ . Apply [F8] with target conditional tolerance $δ_{M}$ ; it supplies a source tolerance $δ_{X} > 0$ . Choose a relative source-pair tolerance $δ_{X Y} \leq \min (δ_{M}, δ_{X})$ . In [F11], take the empirical tolerance below $δ_{X Y} \min_{P_{X Y} (x, y) > 0} P_{X Y} (x, y)$ ; then the pair block belongs to $T_{δ_{X Y}}^{(n)} (P_{X Y})$ with probability tending to one. Summing relative typicality errors over the $Y$ -coordinates shows that its $X^{n}$ marginal is in $T_{δ_{X}}^{(n)} (P_{X})$ , so [F8] makes covering failure tend to zero uniformly. Conditional on successful selection, its law is uniform within each conditional type class, and [F9] makes $(X^{n}, Y^{n}, U^{n})$ jointly typical at tolerance $ϵ$ with probability tending to one. Therefore the selected true codeword is jointly typical with $Y^{n}$ , except on an event whose probability tends to zero.

3.1F1F2F3F4F5F7step 1.1step 2.1algebra

Let $T$ be uniform on $[n]$ and independent of the source, and put $(X, Y, U, \hat{X}) = (X_{T}, Y_{T}, (U_{T}, T), {\hat{X}}_{T})$ . The just-proved Markov property gives $U - X - Y$ , the reconstruction is a deterministic function of $(Y, U)$ , and its expected distortion is ${\overline{D}}_{n} : = n^{- 1} \sum_{i} E d (X_{i}, {\hat{X}}_{i})$ . Since $T$ is independent of $(X_{T}, Y_{T})$ , $I (X; U ∣ Y) = n^{- 1} \sum_{i} I (X_{i}; U_{i} ∣ Y_{i})$ . Thus step 1.1 gives $n^{- 1} \ln M \geq I (X; U ∣ Y) \geq R_{W Z} ({\overline{D}}_{n})$ . For any operationally achievable sequence with distortion limsup at most $D$ , for every $ε_{D} > 0$ we eventually have ${\overline{D}}_{n} \leq D + ε_{D}$ ; monotonicity and continuity in [F7], followed by $ε_{D} ↓ 0$ , prove $R_{W Z}^{o p} (D) \geq R_{W Z} (D)$ . If $D < D_{\min}$ , every reproduction has pointwise distortion at least $\min_{\hat{x}} d (X, \hat{x})$ , so no code can meet the target.

3.2F10F12step 1.2step 2.2algebra

The codebook is independent of the source pair, and its bin labels are independent of source and codebook. Apply [F10] with selection data $Z^{n} = (X^{n}, Y^{n})$ , decoder side information $S^{n} = Y^{n}$ , and $k = 1$ . The complementary-selection restriction is vacuous, and the changed candidate codeword is independent of $(X^{n}, Y^{n})$ ; the codebook-to-bin exponent is at most $\tilde{R} - R + n^{- 1} \ln 2 < I (U; Y) - η$ for all sufficiently large $n$ by the choice of $s$ and $η$ in step 1.2. Thus the probability of a false jointly typical codeword together with a typical true codeword tends to zero. Together with step 2.2, this makes the ensemble probability ${\overset{ˉ}{q}}_{n}$ of the exceptional event (covering failure, an atypical true $(X^{n}, Y^{n}, U^{n})$ tuple, or decoding failure) tend to zero. On the complementary event, the joint empirical type is within tolerance $ϵ$ , so the bounded per-letter distortion of $g (Y, U)$ is at most $D + ω (ϵ)$ for a deterministic $ω (ϵ) \to 0$ ; on the exceptional event it is at most $d_{\max}$ . Hence the ensemble mean distortion is at most $D + ω (ϵ) + d_{\max} {\overset{ˉ}{q}}_{n}$ .

4.1F1step 3.1step 1.3step 2.2step 3.2choosealgebra∎

For each fixed codebook and bin realization $C$ , let $q_{n} (C)$ be the source probability of the exceptional event from step 3.2; its ensemble mean is ${\overset{ˉ}{q}}_{n}$ . The finite-ensemble mean of expected distortion plus $d_{\max} q_{n} (C)$ is at most $D + ω (ϵ) + 2 d_{\max} {\overset{ˉ}{q}}_{n}$ . Some deterministic realization has this sum no larger than its ensemble mean; choose the first such realization in a fixed finite ordering. Its distortion is therefore at most $D + ω (ϵ) + 2 d_{\max} {\overset{ˉ}{q}}_{n}$ . Letting $ϵ$ and the rate slack decrease along an increasing sequence of blocklengths proves $R_{W Z}^{o p} (D) \leq R_{W Z} (D)$ . Together with step 3.1 this proves equality.

5 · Examples, counterexamples and false statements

None yet.

Lossy Source Coding with Side Information

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Finite strongly typical sets with support restriction

Definition

Remarks

Finite type-class cardinality bounds

Statement

Facts & Assumptions

Proof

Finite random-codebook covering and selected-codeword law

Statement

Facts & Assumptions

Proof

Finite joint-typicality packing bound for independent random bins

Statement

Facts & Assumptions

Proof

Markov typicality for independently selected finite codewords

Statement

Facts & Assumptions

Proof

Finite-alphabet lossy source coding with decoder-only side information

Definition

Remarks

Finite-alphabet multiterminal lossy source code

Definition

Remarks

Cardinality bound for the finite Wyner-Ziv auxiliary

Statement

Facts & Assumptions

Proof

Convexity, monotonicity, and continuity of finite Wyner-Ziv rate

Statement

Facts & Assumptions

Proof

Finite-alphabet Berger-Tung multiterminal lossy inner bound

Statement

Facts & Assumptions

Proof

Finite-alphabet memoryless Wyner-Ziv theorem

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources