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 — Examples

1 · Prerequisites

2 · Summary

The first example compares decoder-only side information with the no-side-information rate-distortion limit. At the model level, decoder-only access uses an encoder $f_{n} : X^{n} \to [M]$ and decoder $g_{n} : [M] \times Y^{n} \to {\hat{X}}^{n}$ , whereas side information available at both terminals permits an encoder $f_{n} : X^{n} \times Y^{n} \to [M]$ and the same decoder inputs $(m, y^{n})$ . The Wyner-Ziv theorem on the A page covers only the $X^{n}$ -only encoder model; this page makes no claim that encoder access to $Y^{n}$ leaves the rate unchanged. The examples also compute the lossless conditional-entropy endpoint and verify the Slepian-Wolf special case inside the Berger-Tung inner bound. All logarithms and rates are in nats. The multiterminal examples state exactness only for the lossless specialization proved by the Slepian-Wolf theorem.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-adaptedOpen item page →

No side information reduces Wyner-Ziv to ordinary rate distortion

Example

Let $Y$ be a constant random variable, let $X$ have any finite law, and let $d : X \times \hat{X} \to [0, d_{\max}]$ be finite. Define the ordinary finite single-letter information rate in nats by $R_{X, d}^{n a t} (D) : = \inf_{P_{\hat{X} ∣ X} : E d (X, \hat{X}) \leq D} I (X; \hat{X})$ . Then decoder-only side information is absent and $R_{W Z} (D) = R_{X, d}^{n a t} (D)$ .

Facts & Assumptions

Given: A finite source law $P_{X}$ , a constant $Y$ , finite reproduction alphabet, finite bounded distortion, and feasible $D$ .

[F1]

Finite-alphabet memoryless Wyner-Ziv theorem: $R_{W Z} (D)$ minimizes $I (X; U ∣ Y)$ over finite $U - X - Y$ and $\hat{X} = g (Y, U)$ subject to the expected distortion constraint.

[F2]

Finite mutual information: $I (X; \hat{X})$ is the finite joint-law KL in nats, so the displayed ordinary single-letter infimum uses the same units as $R_{W Z}$ .

[F3]

Finite-alphabet lossy source coding with decoder-only side information: a finite auxiliary $U$ and decoder map $g (Y, U)$ define a stochastic reproduction channel from $X$ ; when $Y$ is constant and $U = \hat{X}$ , the decoder returns that reproduction letter.

[F4]

Data processing for a finite Markov chain, with equality condition: for a finite Markov chain $X \to U \to \hat{X}$ , $I (X; \hat{X}) \leq I (X; U)$ .

Verification

1.1F1F2F4algebra

Because $Y$ is constant, any Wyner-Ziv test channel and reconstruction induce a finite channel $P_{\hat{X} ∣ X}$ with $\hat{X} = g (U)$ . Its distortion is unchanged and $X - U - \hat{X}$ is a Markov chain. By [F2] and [F4], $R_{X, d}^{n a t} (D) \leq I (X; \hat{X}) \leq I (X; U ∣ Y) = I (X; U)$ . Taking the infimum over WZ test channels gives $R_{X, d}^{n a t} (D) \leq R_{W Z} (D)$ .

2.1F1F2F3step 1.1algebra∎

Conversely, every finite channel $P_{\hat{X} ∣ X}$ feasible for the ordinary infimum in [F2] gives the WZ test channel $U = \hat{X}$ and decoder $g (y, u) = u$ . This is feasible with the same mutual information and distortion, by [F3]. Taking infima gives $R_{W Z} (D) \leq R_{X, d}^{n a t} (D)$ . Together with step 1.1 this proves equality.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedOpen item page →

Lossless Wyner-Ziv endpoint is the Slepian-Wolf rate

Example

Let $(X, Y)$ be any finite IID source pair, let $\hat{X} = X$ , and use Hamming distortion $d (x, \hat{x}) = 1_{{x \neq \hat{x}}}$ . At $D = 0$ , the Wyner-Ziv rate equals $H (X ∣ Y)$ , the same conditional rate as one-encoder lossless compression with decoder side information $Y$ .

Facts & Assumptions

Given: A finite IID pair $(X, Y)$ , Hamming distortion, and target $D = 0$ .

[F1]

Finite-alphabet memoryless Wyner-Ziv theorem: the operational rate equals the minimum finite $I (X; U ∣ Y)$ for $\hat{X} = g (Y, U)$ with expected distortion at most zero.

[F2]

Finite conditional mutual information identities and equality: $I (X; U ∣ Y) = H (X ∣ Y) - H (X ∣ U, Y)$ .

[F3]

Finite-IID k-source Slepian–Wolf rate region: for two finite IID sources, achievable lossless rates satisfy $R_{X} \geq H (X ∣ Y)$ , $R_{Y} \geq H (Y ∣ X)$ , and $R_{X} + R_{Y} \geq H (X, Y)$ , and these inequalities are sufficient.

[F4]

Finite conditional entropy: conditional entropy is the finite weighted entropy of the conditional laws on positive-mass conditioning values.

[F5]

Finite KL divergence is nonnegative with equality exactly at equal laws: $I (X; Y) = D (P_{X Y} ∥ P_{X} P_{Y}) \geq 0$ .

[F6]

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

[F7]

Finite distributions, entropy, divergence, and stochastic matrices: a point-mass probability vector has entropy zero under $0 \ln 0 = 0$ .

[F8]

Finite fixed-length multiterminal lossless code: separate finite-length encoders send indices to a common decoder, and achievable rates allow vanishing block-error probability.

Verification

1.1F1F2F4F7givenalgebra

Any feasible test channel has nonnegative Hamming distortion with expectation zero, so $X = \hat{X} = g (Y, U)$ almost surely. Every positive-mass conditional law of $X$ given $(U, Y)$ is therefore a point mass; [F4] and [F7] give $H (X ∣ U, Y) = 0$ , and [F2] gives $I (X; U ∣ Y) = H (X ∣ Y)$ . The admissible choice $U = X$ , $g (y, u) = u$ has zero distortion and the same objective, so the Wyner-Ziv minimum is exactly $H (X ∣ Y)$ .

2.1F3F5F6F8step 1.1algebra∎

In the two-source Slepian-Wolf region of [F3], the subset ${X}$ requires $R_{X} \geq H (X ∣ Y)$ . The rate pair $(R_{X}, R_{Y}) = (H (X ∣ Y), H (Y))$ satisfies the other two inequalities because $H (Y) \geq H (Y ∣ X)$ follows from [F5] and the first identity in [F6], while $H (X ∣ Y) + H (Y) = H (X, Y)$ is the second identity in [F6]. These are the operational rates of the fixed-length code convention in [F8], so the minimum X-encoder rate with the Y-encoder sending its lossless sequence is $H (X ∣ Y)$ , matching step 1.1.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedOpen item page →

Berger-Tung inner bound contains the Slepian-Wolf region

Example

For a finite IID $k$ -source, take ${\hat{X}}_{i} = X_{i}$ and Hamming distortion at $D_{i} = 0$ . Choosing $U_{i} = X_{i}$ in the Berger-Tung test-channel construction makes its subset inequalities the Slepian-Wolf inequalities. This is a lossless special case where the inner bound matches the exact rate region; no such equality is asserted for general multiterminal lossy coding.

Facts & Assumptions

Given: A finite IID $k$ -source, identity auxiliary channels $U_{i} = X_{i}$ , and zero Hamming distortions.

[F1]

Finite-alphabet Berger-Tung multiterminal lossy inner bound: the finite test-channel subset constraints are $\sum_{i \in S} R_{i} \geq I (X_{S}; U_{S} ∣ U_{S^{c}})$ for every nonempty $S$ .

[F2]

Finite-IID k-source Slepian–Wolf rate region: the exact finite-IID lossless rate region is $\sum_{i \in S} R_{i} \geq H (X_{S} ∣ X_{S^{c}})$ for every nonempty $S$ .

[F3]

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

[F4]

Finite conditional entropy: conditional entropy averages the entropies of the conditional laws over positive-mass conditioning values.

[F5]

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

[F6]

Finite fixed-length multiterminal lossless code: separate finite-length encoders send indices to a common decoder, and achievable rates allow vanishing block-error probability.

Verification

1.1F1givenconstruct

With $U_{i} = X_{i}$ , every $U_{i} - X_{i}$ test channel is the identity and the product factorization is satisfied. The decoder sets ${\hat{X}}_{i} = U_{i}$ , so all Hamming distortions vanish. The subset right-hand side in [F1] becomes $I (X_{S}; X_{S} ∣ X_{S^{c}})$ .

2.1F1F2F3F4F5F6step 1.1algebra∎

For each positive-mass value $c$ of $X_{S^{c}}$ , the conditional law of $(X_{S}, X_{S})$ has mass $p_{X_{S} ∣ c} (x)$ at $(x, x)$ and zero off the diagonal. Its entropy therefore equals that of $X_{S}$ given $c$ by [F5]. Averaging over $c$ using [F4] gives $H (X_{S}, X_{S} ∣ X_{S^{c}}) = H (X_{S} ∣ X_{S^{c}})$ , so [F3] yields $I (X_{S}; X_{S} ∣ X_{S^{c}}) = 2 H (X_{S} ∣ X_{S^{c}}) - H (X_{S}, X_{S} ∣ X_{S^{c}}) = H (X_{S} ∣ X_{S^{c}})$ . This also covers $S = [k]$ , whose complement is a singleton. These are exactly the inequalities in [F2], under the lossless fixed-length common-decoder convention [F6]; lossless block-error achievability is supplied by [F2]. Therefore the Berger-Tung inner bound contains the exact Slepian-Wolf region for this zero-distortion special case, while its statement remains only an inner bound for general distortions.

Lossy Source Coding with Side Information — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

No side information reduces Wyner-Ziv to ordinary rate distortion

Example

Facts & Assumptions

Verification

Lossless Wyner-Ziv endpoint is the Slepian-Wolf rate

Example

Facts & Assumptions

Verification

Berger-Tung inner bound contains the Slepian-Wolf region

Example

Facts & Assumptions

Verification

Sources