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.

✓ 12 results · all verified · 1 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 11 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Rate Distortion and Lossy Source Coding

1 · Prerequisites

2 · Summary

The page distinguishes joint-law mutual information from operational code rates, and expected distortion from excess-distortion probability. Finite-alphabet quantities are in bits; general mutual information is first defined in nats and converted by $\ln 2$ . The Gaussian results use standard-Borel KL and explicitly retain their Axiom of Choice assumptions. The finite memoryless theorem covers deterministic fixed-length codes for expected distortion and every positive excess-distortion slack. The stationary-ergodic theorem uses bounded finite-alphabet distortion and does not claim exact-threshold excess convergence at minimum distortion. The Blahut–Arimoto carrier gives an exact-real recurrence and a log- $γ$ gap certificate; its certified interval procedure requires rational $p_{i}, d_{i j}, β, q_{0} (j)$ and a positive rational tolerance, and makes no bit-complexity claim.

The vector Gaussian result uses a relative-entropy reference-kernel proof so the converse applies to reconstructions without densities. Reverse water-filling includes zero modes and both total-distortion endpoints.

Source trail

MIT OpenCourseWare 6.441, Chapters 23, 24, and 25 (Chapter 23, Chapter 24, Chapter 25), §§23.2–23.3, 24.1–24.3, 25.1–25.2: finite rate-distortion, random coding, stationary sources, and Gaussian formulas.
Robert M. Gray, Source Coding Theory, first edition (full text), Ch. 2 §2.6; Ch. 3 §§3.2–3.4; Ch. 4 §§4.1, 4.4–4.7: general mutual information; finite and stationary coding; Blahut–Arimoto iteration; Gaussian lower bounds. Gray §4.3 is a discrete Shannon lower bound, not the vector Gaussian result.
Robert M. Gray, Entropy and Information Theory, corrected first edition (full text), Ch. 5 §§5.3, 5.5 and Ch. 10 §10.6: standard-Borel KL chain rule, general mutual information, and the stationary block rate-distortion argument.
Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed. (full text), §10.3.3, Theorem 10.3.3, printed pp. 312–314: vector Gaussian reverse water-filling. The local vector converse is proved with KL to cover singular reconstruction laws.
Gray, Source Coding Theory §4.4, printed pp. 96–97, gives the finite Blahut iteration and explicitly leaves convergence unproved; the local certificate and termination argument is proved on this page.
MIT OpenCourseWare 6.441, Chapter 25 §25.2, PDF pp. 4–5 / printed pp. 258–259, gives the parametric optimization framing and notes iterative algorithms. The local proof supplies all convergence and certified-gap steps.

3 · Logical flowchart

4 · Definitions, theorems and proofs

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

Mutual information for standard-Borel random elements

Definition

Assume AC. Let $X, Y$ be random elements with standard-Borel value spaces $(X, X)$ and $(Y, Y)$ , and let $P_{X Y}$ , $P_{X}$ , and $P_{Y}$ be their joint and marginal probability laws. The product law $P_{X} \otimes P_{Y}$ exists by For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique. Define the mutual information in nats by

$I_{n a t} (X; Y) : = D (P_{X Y} ∥ P_{X} \otimes P_{Y}) \in [0, + \infty],$

where $D$ is the directional Kullback–Leibler divergence of Kullback–Leibler divergence. This definition remains meaningful when one or both laws have no Lebesgue density and does not subtract differential entropies that may be infinite.

Remarks

The underlying spaces are standard Borel, as defined in Standard Borel spaces. AC is part of the definition's dependency contract through the Radon–Nikodym construction in the KL supplier.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Single-letter and block distortion

Definition

Let $(X, A)$ and $(\hat{X}, \hat{A})$ be measurable spaces, and let $d : X \times \hat{X} \to [0, + \infty]$ be a measurable single-letter distortion. For a positive integer $n$ and ordered blocks $x^{n} = (x_{1}, \dots, x_{n}) \in X^{n}$ and ${\hat{x}}^{n} = ({\hat{x}}_{1}, \dots, {\hat{x}}_{n}) \in {\hat{X}}^{n}$ , define the normalized additive block distortion by

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

If the same ordered blocks are labeled $x_{a}^{a + n - 1} : = (x_{a}, \dots, x_{a + n - 1})$ and ${\hat{x}}_{a}^{a + n - 1} : = ({\hat{x}}_{a}, \dots, {\hat{x}}_{a + n - 1})$ , for any integer $a$ , the equivalent formula is

$d_{n} (x_{a}^{a + n - 1}, {\hat{x}}_{a}^{a + n - 1}) = \frac{1}{n} \sum_{i = a}^{a + n - 1} d (x_{i}, {\hat{x}}_{i}) .$

The substitution $i = a + t - 1$ gives the defining sum, so changing the coordinate labels changes neither the block distortion nor its normalization. In particular, blocks $X_{0}^{n - 1}$ use the indices $0, \dots, n - 1$ , while blocks $X^{n} = (X_{1}, \dots, X_{n})$ use $1, \dots, n$ .

When the alphabets are finite and nonempty and $d$ is finite-valued, define $d_{\max} : = \max_{x, \hat{x}} d (x, \hat{x})$ . Expected distortion is $E d_{n} (X^{n}, {\hat{X}}^{n})$ ; the excess-distortion probability at threshold $D$ is $P (d_{n} (X^{n}, {\hat{X}}^{n}) > D)$ . These are distinct criteria: one is an expectation and the other is a tail probability.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck pendingOpen item page →

Finite Gaussian water-level allocation

Statement

Let $m \geq 1$ , let $λ_{1}, \dots, λ_{m} \geq 0$ , and for $0 \leq δ_{i} \leq λ_{i}$ put

$ϕ_{i} (δ_{i}) : = {\begin{cases} \frac{1}{2} \log_{2} (λ_{i} / δ_{i}), & λ_{i} > 0, 0 < δ_{i} \leq λ_{i}, \\ + \infty, & λ_{i} > 0, δ_{i} = 0, \\ 0, & λ_{i} = 0, δ_{i} = 0. \end{cases}$

For a total distortion budget $D \geq 0$ , minimize $\sum_{i} ϕ_{i} (δ_{i})$ subject to $\sum_{i} δ_{i} \leq D$ and $0 \leq δ_{i} \leq λ_{i}$ . If $0 < D < \sum_{i} λ_{i}$ , there is a unique $θ \in (0, \max_{i} λ_{i})$ satisfying

$\sum_{i} \min (λ_{i}, θ) = D,$

and the minimum is

$\frac{1}{2} \sum_{i} \log_{2}^{+} (λ_{i} / θ), δ_{i}^{*} = \min (λ_{i}, θ),$

where $\log_{2}^{+} (u) : = \max (0, \log_{2} u)$ for $u > 0$ , and $\log_{2}^{+} (0) : = 0$ . If $D = 0$ , the minimum is $+ \infty$ when some $λ_{i} > 0$ and is $0$ when all $λ_{i} = 0$ . If $D \geq \sum_{i} λ_{i}$ , the minimum is $0$ .

Facts & Assumptions

Given: A nonempty finite list of nonnegative numbers $λ_{i}$ and $D \geq 0$ .

Proof

1.1givenalgebra

Define $S (θ) = \sum_{i} \min (λ_{i}, θ)$ for $0 \leq θ \leq \max_{i} λ_{i}$ . It is continuous, $S (0) = 0$ , and $S (\max_{i} λ_{i}) = \sum_{i} λ_{i}$ . If $0 \leq θ_{1} < θ_{2} < \max_{i} λ_{i}$ , some $λ_{j} > θ_{2}$ , so the $j$ -th summand increases strictly and the others do not decrease. Thus for $0 < D < \sum_{i} λ_{i}$ , the intermediate-value theorem gives a unique $θ$ with $S (θ) = D$ .

1.2givenalgebra

For $t > 0$ , $\ln t \leq t - 1$ : if $t \geq 1$ , integrate $1 / u \leq 1$ on $[1, t]$ ; if $0 < t < 1$ , use $\ln t = - \int_{t}^{1} d u / u$ and $1 / u \geq 1$ on $[t, 1]$ . Hence $- \ln t + t - 1 \geq 0$ .

2.1givenstep 1.2algebra

Fix $0 < D < \sum_{i} λ_{i}$ , its $θ$ , and $c = (2 θ \ln 2)^{- 1}$ . If $λ_{i} > θ$ , then for $0 < δ_{i} \leq λ_{i}$ , $ϕ_{i} (δ_{i}) - ϕ_{i} (θ) + c (δ_{i} - θ) = \frac{- \ln (δ_{i} / θ) + δ_{i} / θ - 1}{2 \ln 2} \geq 0$ by step 1.2; the inequality also holds at $δ_{i} = 0$ because $ϕ_{i} (0) = + \infty$ . If $0 < λ_{i} \leq θ$ , then $ϕ_{i} (λ_{i}) = 0$ , and for $0 < δ_{i} \leq λ_{i}$ , step 1.2 gives $ϕ_{i} (δ_{i}) \geq \frac{1 - δ_{i} / λ_{i}}{2 \ln 2} \geq \frac{λ_{i} - δ_{i}}{2 θ \ln 2} = - c (δ_{i} - λ_{i}) .$ It holds at $δ_{i} = 0$ by the infinite-value convention. A zero eigenvalue has only $δ_{i} = 0$ and contributes zero. Thus for every feasible coordinate, $ϕ_{i} (δ_{i}) \geq ϕ_{i} (δ_{i}^{*}) - c (δ_{i} - δ_{i}^{*})$ , with $δ_{i}^{*} = \min (λ_{i}, θ)$ .

3.1givenstep 2.1algebra

Summing the supporting inequalities in step 2.1 and using $\sum_{i} δ_{i} \leq D = \sum_{i} δ_{i}^{*}$ proves $\sum_{i} ϕ_{i} (δ_{i}) \geq \sum_{i} ϕ_{i} (δ_{i}^{*})$ . The latter sum is exactly $\frac{1}{2} \sum_{i} \log_{2}^{+} (λ_{i} / θ)$ ; the allocation is feasible, so it attains the minimum.

4.1givenstep 3.1algebra∎

If $D = 0$ , nonnegativity forces every $δ_{i} = 0$ , giving the two stated cases. If $D \geq \sum_{i} λ_{i}$ , choose $δ_{i} = λ_{i}$ for every i; all rates are zero, and no feasible objective can be negative. These cases complete the endpoint and degenerate branches.

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

General single-letter information rate-distortion function

Definition

Assume AC. Let $X, \hat{X}$ be standard-Borel spaces, let $P_{X}$ be a probability law on $X$ , and let $d : X \times \hat{X} \to [0, + \infty]$ be measurable. A feasible joint law, or coupling, is a probability measure $π$ on $X \times \hat{X}$ whose $X$ -marginal is $P_{X}$ . For each distortion budget $D \geq 0$ , define

$R_{s t d} (D) : = \inf_{\begin{array}{c} π_{X} = P_{X} \\ \int d d π \leq D \end{array}} \frac{D (π ∥ P_{X} \otimes π_{\hat{X}})}{\ln 2} = \inf_{\begin{array}{c} π_{X} = P_{X} \\ \int d d π \leq D \end{array}} \frac{I_{n a t} (X; \hat{X})}{\ln 2} .$

The infimum of an empty feasible set is $+ \infty$ . Values are in bits. This definition makes no general existence or attainment claim and supplies no operational coding theorem for arbitrary standard-Borel alphabets.

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

Fixed-length operational rate-distortion functions

Definition

Let $X_{0}, X_{1}, \dots$ be a source over a finite nonempty alphabet $X$ , let $\hat{X}$ be finite nonempty, and let $d : X \times \hat{X} \to [0, \infty)$ be finite-valued. For positive integers $n$ and $M_{n}$ , write $[M_{n}] = {1, \dots, M_{n}}$ . An $n$ -block fixed-length code with $M_{n}$ messages is a deterministic encoder $f_{n} : X^{n} \to [M_{n}]$ and decoder $g_{n} : [M_{n}] \to {\hat{X}}^{n}$ ; its reconstruction is ${\hat{X}}^{n} = g_{n} (f_{n} (X^{n}))$ , its block distortion is Single-letter and block distortion, and its rate is $n^{- 1} \log_{2} M_{n}$ bits per source symbol.

For each $D \geq 0$ , define the expected-distortion operational rate $R_{o p}^{a v g} (D)$ as the infimum of ${lim sup}_{n} n^{- 1} \log_{2} M_{n}$ over code sequences satisfying ${lim sup}_{n} E d_{n} (X^{n}, {\hat{X}}^{n}) \leq D$ . Define the positive-slack excess-distortion operational rate $R_{o p}^{s l a c k} (D)$ by the same rate infimum over code sequences satisfying

$for every ε > 0, P ⁣ (d_{n} (X^{n}, {\hat{X}}^{n}) > D + ε) ⟶ 0.$

The infimum of an empty set of admissible code sequences is $+ \infty$ . The expected and positive-slack excess criteria are separate definitions. An exact-threshold condition $P (d_{n} > D) \to 0$ is not part of either definition.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck pendingjudge pass (gpt-6-luna)Open item page →

Attainment of finite-alphabet rate-distortion minima

Statement

Let $X, \hat{X}$ be nonempty finite sets, let $p$ be a probability mass function on $X$ , and let $d : X \times \hat{X} \to [0, \infty)$ be finite-valued. Put

D_{\min} : = \sum_{x \in X} p (x) \min_{\hat{x} \in \hat{X}} d (x, \hat{x}) .

For every $D \geq 0$ , the feasible stochastic channels $W (\hat{x} ∣ x)$ satisfying $\sum_{x, \hat{x}} p (x) W (\hat{x} ∣ x) d (x, \hat{x}) \leq D$ form a nonempty set exactly when $D \geq D_{\min}$ . Whenever nonempty, mutual information in bits attains its minimum over this set.

Facts & Assumptions

Given: Nonempty finite alphabets $X, \hat{X}$ , a source pmf $p$ , and finite nonnegative distortion $d$ .

[F1]

Finite mutual information: for a finite joint pmf, mutual information in nats is its finite joint-law KL sum.

[F2]

Finite information quantities convert by the logarithm base: mutual information in bits is the finite nats value divided by $\ln 2$ .

[F3]

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: closed bounded subsets of finite-dimensional Euclidean space are compact.

[F4]

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 metric space attains a minimum.

Proof

1.1givenalgebra

For each $x$ , choose a minimizing ${\hat{x}}_{x}$ from the nonempty finite set $\hat{X}$ ; finite choice is available by successive selection from finitely many nonempty sets. The deterministic channel $W (\hat{x} ∣ x) = 1_{{\hat{x} = {\hat{x}}_{x}}}$ has expected distortion $D_{\min}$ . Conversely, each channel row is a probability vector, so its conditional mean distortion is at least $\min_{\hat{x}} d (x, \hat{x})$ ; averaging against $p$ shows every channel has distortion at least $D_{\min}$ . Thus feasibility is equivalent to $D \geq D_{\min}$ .

1.2F1givenalgebra

For a probability vector $q$ , set $H (q) = - \sum_{i} q_{i} \ln q_{i}$ , with $0 \ln 0 : = 0$ . The scalar function $- t \ln t$ on $(0, 1]$ extends continuously to zero because $\lim_{t ↓ 0} t \ln t = 0$ ; hence entropy is continuous on every finite simplex. Expanding the finite KL sum in [F1] gives $I (X; \hat{X}) = H (p) + H (q) - H (p_{X \hat{X}})$ , where $q (\hat{x}) = \sum_{x} p (x) W (\hat{x} ∣ x)$ ; all terms are continuous functions of the channel coordinates.

2.1F3step 1.1givenalgebra

Identify all channels with a point in $[0, 1]^{∣ X ∣ ∣ \hat{X} ∣}$ . The row-sum equalities, nonnegativity inequalities and expected-distortion inequality define a closed set; the cube makes it bounded. When feasible it is nonempty, so [F3] makes it compact.

3.1F2F4step 2.1step 1.2algebra∎

By [F2], division by the positive constant $\ln 2$ preserves continuity. Thus the bit mutual-information objective is continuous on the nonempty compact feasible set in step 2.1; [F4] gives a point where it attains its minimum. This proves attainment.

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

Finite-alphabet information rate-distortion function

Definition

Let $X, \hat{X}$ be nonempty finite alphabets, let $p$ be a pmf on $X$ , and let $d : X \times \hat{X} \to [0, \infty)$ be finite-valued. A test channel is a stochastic matrix $W (\hat{x} ∣ x)$ , and its expected single-letter distortion is $\sum_{x, \hat{x}} p (x) W (\hat{x} ∣ x) d (x, \hat{x})$ , with block distortion as in Single-letter and block distortion. Put $D_{\min} = \sum_{x} p (x) \min_{\hat{x}} d (x, \hat{x})$ . Define, in bits,

R_{p, d} (D) : = {\begin{cases} \min_{W : E d (X, \hat{X}) \leq D} \frac{I (X; \hat{X})}{\ln 2}, & D \geq D_{\min}, \\ + \infty, & D < D_{\min} . \end{cases}

The minimum exists by Attainment of finite-alphabet rate-distortion minima. Values are not operational code rates; the finite memoryless coding theorem is a separate claim.

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

Stationary finite-block information rate-distortion function

Definition

Let $(X_{t})_{t \in Z}$ be a stationary source on a finite nonempty alphabet $X$ , let $\hat{X}$ be finite nonempty, and let $d : X \times \hat{X} \to [0, d_{\max}]$ be a bounded finite-valued distortion. For $n \geq 1$ and $D \geq 0$ , define

R_{n} (D) : = \frac{1}{n \ln 2} \min_{W_{n} : E d_{n} (X_{0}^{n - 1}, {\hat{X}}_{0}^{n - 1}) \leq D} I (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1}) bits/symbol,

with value $+ \infty$ when the constraint is infeasible. The minimum is attained whenever feasible by Attainment of finite-alphabet rate-distortion minima applied to the block alphabets. Put

D_{\min} : = E \min_{\hat{x} \in \hat{X}} d (X_{0}, \hat{x}), D_{c} : = \min_{\hat{x} \in \hat{X}} E d (X_{0}, \hat{x}), R_{b l o c k} (D) : = \inf_{n \geq 1} R_{n} (D) .

The stationary-ergodic process information rate-distortion quantity is

R_{e r g} (D) : = \inf \underset{n \to \infty}{lim sup} \frac{1}{n \ln 2} I (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1}),

where the infimum ranges over jointly stationary ergodic pairs of finite-alphabet processes with the given source marginal and $E d (X_{0}, {\hat{X}}_{0}) \leq D$ ; an empty infimum is $+ \infty$ .

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Gaussian reference-kernel mutual-information lower bound

Statement

Assume AC. Let $X \sim N (0, σ^{2})$ with $σ^{2} > 0$ , let $Y$ be any real-valued reconstruction jointly distributed with $X$ , and suppose $0 < D < σ^{2}$ and $δ : = E (X - Y)^{2} \leq D$ . Then

$I_{n a t} (X; Y) \geq \frac{1}{2} \ln \frac{σ^{2}}{D} .$

No density for $Y$ , conditional differential entropy, or subtraction of potentially infinite entropies is assumed.

Facts & Assumptions

Given: AC, $X \sim N (0, σ^{2})$ , $Y \in R$ , $0 < D < σ^{2}$ , and $δ = E (X - Y)^{2} \leq D$ .

[A1]

The Axiom of Choice: AC is required by the KL and normal-law suppliers below.

[F1]

Mutual information for standard-Borel random elements: $I_{n a t} (X; Y) = D (P_{X Y} ∥ P_{X} \otimes P_{Y})$ .

[F2]

Standard normal and normal laws: $N (m, s)$ , for $s > 0$ , is the affine image of the standard normal with density $(2 π)^{- 1 / 2} e^{- z^{2} / 2}$ .

[F3]

A C^1 diffeomorphism satisfies the change-of-variables formula for nonnegative Lebesgue measurable functions: under Countable Choice, a positive affine change of variable transforms a density by its Jacobian. The assumed AC in [A1] implies Countable Choice by restricting its choice function to a countable family.

[F4]

Kullback–Leibler divergence: for $P ≪ Q$ , $D (P ∥ Q) = \int \ln (d P / d Q) d P$ ; if absolute continuity fails, the divergence is $+ \infty$ .

[F5]

KL chain rule for standard-Borel disintegrations: when two joint laws have the same standard-Borel marginal, their joint KL is the integral of the conditional KL divergences.

[F6]

Kullback–Leibler divergence is nonnegative: under AC, KL divergence between probability laws is nonnegative.

[F7]

Disintegration of a joint law on standard borel spaces: under AC, a joint law of standard-Borel random elements admits a regular conditional kernel for X given Y.

[F8]

Measurability of integration against a kernel and A prior and model kernel define a joint law: a jointly measurable integrand has measurable kernel integrals, and a probability base with a probability kernel defines a joint law with the iterated-integral formula.

[F9]

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique and Tonelli's theorem for nonnegative measurable functions on a sigma-finite product: the product $P_{Y} \otimes λ$ exists and nonnegative product integrals equal their iterated integrals; a strictly positive density gives an equivalent measure by A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere.

[F10]

KL is invariant under a measurable bijection: a measurable coordinate swap preserves KL, so $I_{n a t} (X; Y) = D (P_{Y X} ∥ P_{Y} \otimes P_{X})$ .

[F11]

The real line with its Borel sigma-algebra is standard Borel: the real line with its Borel sigma-algebra is standard Borel.

Proof

Given: The hypotheses and suppliers [A1], [F1]–[F6].

1.1A1F1F2F3F8F9F10givenconstruct

By [F2]–[F3], $X \sim N (0, σ^{2})$ has the everywhere-positive density $p_{X} (x) = (2 π σ^{2})^{- 1 / 2} e^{- x^{2} / (2 σ^{2})}$ , and $N (y, D)$ has density $q_{y} (x) = (2 π D)^{- 1 / 2} e^{- (x - y)^{2} / (2 D)}$ . Let $γ = N (0, 1)$ and set $L (y, A) = \int 1_{A} (y + \sqrt{D} z) γ (d z)$ for Borel $A$ . The integrand is product-measurable, so [F8] makes $y \mapsto L (y, A)$ measurable; each $L (y, \cdot) = N (y, D)$ is a probability. Thus [F8] gives a joint law $Q$ on the coordinate order $(Y, X)$ with base $P_{Y}$ and conditional kernel $L$ . By [F9], $Q$ and $P_{Y} \otimes P_{X}$ have respective densities $q_{y} (x)$ and $p_{X} (x)$ relative to $P_{Y} \otimes λ$ , so they are equivalent. If $P_{Y X} ≪̸ P_{Y} \otimes P_{X}$ , [F1] and [F10] give $I_{n a t} (X; Y) = + \infty$ , so the result holds. Otherwise equivalence gives $P_{Y X} ≪ Q$ as well.

2.1A1F1F4F10step 1.1algebra

On the remaining case, the logarithm of the reference-density ratio is $\ln \frac{q_{Y} (X)}{p_{X} (X)} = \frac{1}{2} \ln \frac{σ^{2}}{D} - \frac{(X - Y)^{2}}{2 D} + \frac{X^{2}}{2 σ^{2}} .$ It is integrable because $E (X - Y)^{2} = δ < \infty$ and $E X^{2} = σ^{2}$ . The Radon–Nikodym chain identity $d P_{Y X} / d (P_{Y} \otimes P_{X}) = (d P_{Y X} / d Q) (d Q / d (P_{Y} \otimes P_{X}))$ , integrated using [F4] and [F10], gives $I_{n a t} (X; Y) = D (P_{Y X} ∥ Q) + \frac{1}{2} \ln \frac{σ^{2}}{D} + \frac{1}{2} - \frac{δ}{2 D} .$ The finite cross term prevents an $\infty - \infty$ ambiguity if the first divergence is infinite.

3.1A1F5F6F7F11step 2.1algebra∎

By [F11] the real source and reconstruction spaces are standard Borel, so [F7] supplies a conditional kernel for $X$ given $Y$ under $P_{Y X}$ . The law $Q$ has the same $Y$ -marginal and conditional kernel $N (y, D)$ . Thus [F5] expresses $D (P_{Y X} ∥ Q)$ as an integral of conditional KL divergences, which is nonnegative by [F6], including the value $+ \infty$ . Also $δ \leq D$ , so $1 / 2 - δ / (2 D) \geq 0$ . The identity in step 2.1 gives the claimed lower bound.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Convexity, monotonicity, and continuity of finite rate-distortion

Statement

Let the source and reproduction alphabets be finite nonempty sets and let the distortion be finite-valued and nonnegative. The finite-alphabet information rate-distortion function $R (D)$ of Finite-alphabet information rate-distortion function is finite and nonincreasing on $[D_{\min}, \infty)$ , convex there, zero for $D \geq D_{c} : = \min_{\hat{x}} E d (X, \hat{x})$ , and right-continuous at every feasible distortion, including $D_{\min}$ .

Facts & Assumptions

Given: A finite source pmf, finite nonempty reproduction alphabet, and finite nonnegative distortion.

[F1]

Finite-alphabet information rate-distortion function: $R (D)$ minimizes finite mutual information over channels meeting the mean-distortion constraint and is $+ \infty$ when infeasible.

[F2]

Attainment of finite-alphabet rate-distortion minima: feasibility is equivalent to $D \geq D_{\min}$ , and every feasible minimum is attained on a finite channel simplex.

[F3]

Finite log-sum inequality with support and equality cases: the finite log-sum inequality applies to nonnegative finite arrays, with zero terms interpreted by continuity.

[F4]

Finite mutual information: mutual information is the finite joint-KL sum; it is finite for finite alphabets.

[F5]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite KL divergence is nonnegative.

[F6]

Proof

1.1F1F2F5given

Feasibility at every $D \geq D_{\min}$ and attainment are given by [F2], so $R (D)$ is finite there; [F5] gives $R (D) \geq 0$ . If $D_{2} \geq D_{1}$ , every channel feasible at $D_{1}$ is feasible at $D_{2}$ , so the infimum cannot increase.

1.2F1F3F4givenalgebra

Fix $D_{0}, D_{1} \geq D_{\min}$ , $t \in [0, 1]$ , and channels $W_{0}, W_{1}$ feasible at those budgets. Set $W = t W_{0} + (1 - t) W_{1}$ ; its distortion is at most $t D_{0} + (1 - t) D_{1}$ . For each $(x, \hat{x})$ , apply [F3] to the two joint-mass terms $t p (x) W_{0} (\hat{x} ∣ x), (1 - t) p (x) W_{1} (\hat{x} ∣ x)$ and corresponding product-marginal terms $t p (x) q_{0} (\hat{x}), (1 - t) p (x) q_{1} (\hat{x})$ , then sum over $(x, \hat{x})$ . The resulting inequality is $I_{W} (X; \hat{X}) \leq t I_{W_{0}} (X; \hat{X}) + (1 - t) I_{W_{1}} (X; \hat{X})$ , in nats and therefore also in bits.

2.1F1F5step 1.1given

The constant channel outputting a minimizer of $E d (X, \hat{x})$ has distortion $D_{c}$ and zero mutual information. For $D \geq D_{c}$ , this channel is feasible, so [F5] gives $R (D) = 0$ .

2.2F1F2step 1.2algebra

Choose minimizing channels at $D_{0}, D_{1}$ by [F2] and use their mixture from step 1.2. The mixture is feasible at $t D_{0} + (1 - t) D_{1}$ and has rate at most $t R (D_{0}) + (1 - t) R (D_{1})$ ; taking the infimum proves convexity.

2.3F1F2F6step 1.1givenalgebra

Fix feasible $D$ and put $D_{k} = D + 1 / (k + 1)$ for $k \geq 0$ . By step 1.1, $R (D_{k})$ increases to a finite limit $L \leq R (D)$ . The finite channel simplex $S$ is closed and bounded, hence compact by [F6]. Distortion $δ (W)$ is linear and bit mutual information $I_{2} (W)$ is continuous on $S$ , by its finite entropy formula and continuity of $- u \ln u$ at zero. Thus $K_{k} : = {W \in S : δ (W) \leq D_{k}, I_{2} (W) \leq L}$ is closed in $S$ and nonempty by [F2], since $R (D_{k}) \leq L$ . These sets are nested. Their intersection is nonempty: otherwise their open complements would cover $S$ , and a finite subcover would force one $K_{k}$ to be empty, a contradiction. A single $W$ in the intersection satisfies $δ (W) \leq D$ and $I_{2} (W) \leq L$ , so $R (D) \leq L$ by [F1]. Hence $R (D_{k}) \to R (D)$ ; monotonicity then gives right-continuity by squeezing $R (D + h)$ between $R (D_{k})$ and $R (D)$ whenever $0 \leq h \leq 1 / (k + 1)$ . No sequence of minimizers is selected.

3.1step 1.1step 2.1step 2.2step 2.3∎

Steps 1.1, 2.1, 2.2, and 2.3 prove every assertion, including the degenerate case $D_{c} = D_{\min}$ , where the constant channel already gives zero on the entire feasible interval.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Binary Hamming rate-distortion function

Statement

Let $X \sim Bernoulli (p)$ , $0 \leq p \leq 1$ , and let the reproduction alphabet be ${0, 1}$ with Hamming distortion $d (x, \hat{x}) = 1_{{x \neq \hat{x}}}$ . Write $p_{0} : = \min (p, 1 - p)$ and

h_{2} (u) : = - u \log_{2} u - (1 - u) \log_{2} (1 - u), 0 \log_{2} 0 : = 0.

For every $D \geq 0$ , the finite-alphabet information rate-distortion function is

R (D) = {\begin{cases} h_{2} (p) - h_{2} (D), & 0 \leq D \leq p_{0}, \\ 0, & D \geq p_{0} . \end{cases}

Facts & Assumptions

Given: A Bernoulli source parameter $p \in [0, 1]$ , binary reproduction, and Hamming distortion.

[F1]

Finite-alphabet information rate-distortion function: $R (D)$ is the minimum finite mutual information in bits over test channels of expected distortion at most $D$ .

[F2]

Finite mutual information: finite mutual information is the finite joint-law KL sum; its base- $2$ version is obtained by replacing $\ln$ with $\log_{2}$ . All entropies and mutual informations in this proof use that bit convention.

[F3]

Finite conditional mutual information identities and equality: conditional mutual information is a finite conditional KL sum and is nonnegative.

[F4]

Finite entropy and mutual-information chain rules: finite conditional entropy obeys the chain rule, here with every finite entropy scaled from nats to bits by $1 / \ln 2$ .

[F5]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite mutual information and conditional mutual information are nonnegative.

Proof

Given: The objects in the statement and suppliers [F1]–[F5].

1.1F2F3F4F5givenalgebra

Let $Y$ be any test-channel output and put $E = X \oplus Y$ , where $\oplus$ is addition modulo two; write $e = P (E = 1) = E d (X, Y)$ . Since $X = Y \oplus E$ , the map $(Y, E) \mapsto X$ is deterministic and bijective in E for each Y, so $H (X ∣ Y) = H (E ∣ Y)$ . By [F4], $H (E) - H (E ∣ Y) = I (E; Y)$ , and this mutual information is nonnegative by [F3] and [F5]; hence $H (E ∣ Y) \leq H (E) = h_{2} (e)$ . If $0 \leq D \leq p_{0} \leq 1 / 2$ and $e \leq D$ , then $h_{2} (e) \leq h_{2} (D)$ : on $(0, 1 / 2)$ , $h_{2}^{'} (u) = \log_{2} ((1 - u) / u) \geq 0$ , and continuity supplies the endpoints. The entropy identity in [F4] therefore gives $I (X; Y) \geq h_{2} (p) - h_{2} (D)$ .

1.2givenconstructalgebra

Suppose $0 \leq D \leq p_{0}$ and $(p, D) \neq (1 / 2, 1 / 2)$ . Then $1 - 2 D > 0$ and $q : = (p - D) / (1 - 2 D) \in [0, 1]$ : nonnegativity follows from $D \leq p$ (since $D \leq p_{0}$ ), while $q \leq 1$ is equivalent to $p + D \leq 1$ , which follows from $D \leq 1 - p$ . Let $Y \sim Bernoulli (q)$ , independently let $E \sim Bernoulli (D)$ , and set $X = Y \oplus E$ . Then $P (X = 1) = q (1 - D) + (1 - q) D = D + q (1 - 2 D) = p$ , and the Hamming distortion is exactly $D$ .

2.1F1F5step 1.1given

If $D \geq p_{0}$ , reconstructing constantly by the more probable source symbol has expected Hamming distortion $p_{0}$ and zero mutual information; [F5] makes zero the minimum. This proves the formula on that branch, including deterministic sources.

3.1F2F4step 1.1step 2.1step 1.2givenalgebra∎

Since E is independent of Y and determines X given Y, $H (X ∣ Y) = H (E ∣ Y) = H (E) = h_{2} (D)$ . Thus $I (X; Y) = h_{2} (p) - h_{2} (D)$ , attaining the converse in step 1.1. The excluded corner $p = 1 / 2, D = 1 / 2$ is covered by step 2.1. This proves the formula for all parameters.

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Finite-alphabet Blahut–Arimoto rate-distortion algorithm

Definition

For the exact-real recurrence, write $[m] = {1, \dots, m}$ and $[n] = {1, \dots, n}$ for positive integers $m, n$ . Let $p_{1}, \dots, p_{m} > 0$ be source probabilities summing to one, let $d_{i j} \geq 0$ be finite distortions for $(i, j) \in [m] \times [n]$ , let $β \geq 0$ be finite, and let $q_{0}$ be any full-support reproduction pmf. For $t = 0, 1, \dots$ set

Z_{i} (q_{t}) = \sum_{j = 1}^{n} q_{t} (j) e^{- β d_{i j}}, W_{t} (j ∣ i) = \frac{q_{t} (j) e^{- β d_{i j}}}{Z_{i} (q_{t})}, q_{t + 1} (j) = \sum_{i = 1}^{m} p_{i} W_{t} (j ∣ i) .

All denominators are positive, every row of $W_{t}$ sums to one, and $q_{t + 1}$ has full support. Define the nats objective $L_{β} (W) = I_{n a t} (X; \hat{X}) + β E d (X, \hat{X})$ , the current channel value $L_{t} = L_{β} (W_{t})$ , and the a-posteriori factor

γ_{t} : = \max_{1 \leq j \leq n} \sum_{i = 1}^{m} p_{i} \frac{e^{- β d_{i j}}}{Z_{i} (q_{t})} \geq 1.

For $τ > 0$ , the output is the first processed iteration index $t$ for which a rigorous upper interval endpoint $u_{t} \geq \ln γ_{t}$ satisfies $u_{t} \leq τ$ , together with $W_{t}$ , $q_{t + 1}$ , $L_{t}$ , and interval enclosures of these values and $\ln γ_{t}$ . Compute the objective by $L_{t} = \sum_{i = 1}^{m} \sum_{j = 1}^{n} p_{i} W_{t} (j ∣ i) \ln \frac{W_{t} (j ∣ i)}{q_{t + 1} (j)} + β \sum_{i = 1}^{m} \sum_{j = 1}^{n} p_{i} W_{t} (j ∣ i) d_{i j} .$ The exact-real recurrence defines all values being enclosed.

The certified interval procedure is defined only when every $p_{i}, d_{i j}, β, q_{0} (j)$ and $τ$ is rational, with the positivity, normalization, finiteness and full-support conditions above and $τ > 0$ . Execute the following loops. For $t = 0, 1, 2, \dots$ , try precisions $r = 2, 3, 4, \dots$ in order. At precision $r$ , use the dyadic format $(p, e_{\min}, e_{\max}) = (r^{2}, - r, r)$ and truncation index $N = r$ in Certified range evaluation for elementary real and complex functions. Round each rational input outward to an interval in this format. Build a finite typed expression DAG for the recurrence from $q_{0}$ through $q_{t}$ , and request enclosures for every $W_{t} (j ∣ i)$ , $q_{t + 1} (j)$ , $L_{t}$ , and $s_{j, t} : = \sum_{i} p_{i} e^{- β d_{i j}} / Z_{i} (q_{t})$ . If rounding any input overflows or the evaluator returns a non-finite status, increase $r$ and repeat this precision loop. Otherwise form the interval $G_{t} = [\max_{j} {\underline{s}}_{j, t}, \max_{j} {\overline{s}}_{j, t}]$ from the rational endpoints of the $s_{j, t}$ enclosures, and evaluate $\ln G_{t}$ with the same format and truncation index. If this evaluation is non-finite, increase $r$ and repeat. Continue increasing $r$ until all requested output enclosures, including that of $\ln γ_{t}$ , have width less than $1 / (t + 1)$ . Let $u_{t}$ be the upper endpoint of the resulting $\ln G_{t}$ enclosure. If $u_{t} \leq τ$ , return the stated output and enclosures; otherwise end the precision loop and proceed to $t + 1$ . For arbitrary exact-real inputs the recurrence remains mathematically defined, but this interval implementation is specified only under the rational representability conditions. No bit-complexity bound is asserted.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Stationary block rate-distortion limit and endpoint continuity

Statement

For a stationary finite-alphabet source and bounded additive distortion as in Stationary finite-block information rate-distortion function, the sequence $R_{n} (D)$ has a limit for every feasible $D$ , and

\lim_{n \to \infty} R_{n} (D) = \inf_{n \geq 1} R_{n} (D) = R_{b l o c k} (D) .

The function $R_{b l o c k}$ is nonincreasing and convex on $[D_{\min}, \infty)$ , is zero for $D \geq D_{c}$ , and is right-continuous at $D_{\min}$ . It is infinite for $0 \leq D < D_{\min}$ .

Facts & Assumptions

Given: A stationary process on a finite nonempty source alphabet, a finite nonempty reproduction alphabet, and bounded finite nonnegative distortion.

[F1]

Stationary finite-block information rate-distortion function: $n R_{n} (D)$ is the minimum block mutual information in bits subject to normalized additive distortion; $D_{\min}$ is the pointwise minimum mean distortion and $D_{c}$ is the best constant-reproduction distortion.

[F2]

Finite mutual information and Finite information quantities convert by the logarithm base: finite mutual information is a finite KL sum and bits equal nats divided by $\ln 2$ .

[F3]

Finite entropy chain rule and monotonicity under conditioning and Finite entropy and mutual-information chain rules: finite entropy is subadditive and the chain rule holds.

[F4]

Finite log-sum inequality with support and equality cases: finite log-sum gives convexity of mutual information in a channel for fixed input law.

[F5]

Attainment of finite-alphabet rate-distortion minima: every feasible finite block channel minimum is attained.

[F6]

Data processing for a finite Markov chain, with equality condition: finite information cannot increase under deterministic postprocessing.

Proof

1.1F1F5givenconstruct

Write $a_{n} (D) = n R_{n} (D)$ , and choose minimizing channels for blocks of lengths $m$ and $n$ , available by [F5]. Use their conditional product as a channel on the concatenated block. Stationarity gives the same marginal laws for the second block as for a block of length $n$ ; each part has mean distortion at most $D$ , so the concatenated normalized distortion is at most $D$ .

1.2F1F2F4givenalgebra

A best constant reconstruction has normalized expected distortion $D_{c}$ and zero mutual information for every block. Applying the finite log-sum inequality [F4] to the joint pmf and the product of its marginals, both of total mass one, gives nonnegative mutual information; hence $R_{n} (D) = 0$ for $D \geq D_{c}$ . If $D < D_{\min}$ , every coordinate distortion is at least its pointwise minimum, so no block channel is feasible and each $R_{n} (D) = + \infty$ .

1.3F1F5givenalgebra

Suppose $D_{c} > D_{\min}$ , and let $γ$ be the smallest positive value among the finite gaps $d (x, \hat{x}) - \min_{z} d (x, z)$ ; thus $γ > 0$ . Fix $0 < ϵ < γ / 2$ . Since $D_{\min} + ϵ$ is feasible, [F5] supplies a minimizing length- $n$ channel at that distortion budget. Let $S_{i} = 1$ when its chosen reproduction has positive gap from the pointwise minimum, and let $α = n^{- 1} \sum_{i} P (S_{i} = 1)$ . The excess above the block minimum is at least $γ \sum_{i} S_{i} / n$ , so $α \leq ϵ / γ$ .

2.1F2F3step 1.1algebra

Let $(X_{1}, Y_{1})$ and $(X_{2}, Y_{2})$ denote the two source/output block pairs under that channel. Conditional independence of the two channel outputs given the full source block gives $H (Y_{1}, Y_{2} ∣ X_{1}, X_{2}) = H (Y_{1} ∣ X_{1}) + H (Y_{2} ∣ X_{2})$ . Entropy subadditivity gives $H (Y_{1}, Y_{2}) \leq H (Y_{1}) + H (Y_{2})$ . Subtracting these finite quantities and using [F3] yields $I (X_{1}, X_{2}; Y_{1}, Y_{2}) \leq I (X_{1}; Y_{1}) + I (X_{2}; Y_{2})$ , so $a_{m + n} (D) \leq a_{m} (D) + a_{n} (D)$ . The source blocks need not be independent.

2.2F1F3F6step 1.3algebraconstruct

Fix a pointwise minimizer ${\hat{x}}_{*} (x)$ for each source letter and a dummy symbol ${\hat{x}}_{d} \in \hat{X}$ . Keep the original output where $S_{i} = 0$ and replace it by ${\hat{x}}_{*} (X_{i})$ where $S_{i} = 1$ , obtaining ${\hat{X}}^{' n}$ ; then $d (X_{i}, {\hat{X}}_{i}^{'}) = \min_{\hat{x}} d (X_{i}, \hat{x})$ for every $i$ , so stationarity gives $E d_{n} (X^{n}, {\hat{X}}^{' n}) = D_{\min}$ . Let $C_{i} = {\hat{x}}_{*} (X_{i})$ when $S_{i} = 1$ and ${\hat{x}}_{d}$ otherwise. Since ${\hat{X}}^{' n}$ is a function of $({\hat{X}}^{n}, S^{n}, C^{n})$ , data processing and the entropy chain rule give $I (X^{n}; {\hat{X}}^{' n}) \leq I (X^{n}; {\hat{X}}^{n}, S^{n}, C^{n}) \leq I (X^{n}; {\hat{X}}^{n}) + H (S^{n}) + H (C^{n} ∣ S^{n}) .$ Each $C_{i}$ is fixed when $S_{i} = 0$ and has at most $∣ \hat{X} ∣$ values when $S_{i} = 1$ , so $H (C^{n} ∣ S^{n}) \leq \sum_{i} P (S_{i} = 1) \log_{2} ∣ \hat{X} ∣$ . Entropy subadditivity and concavity of binary entropy give $H (S^{n}) \leq n h_{2} (α)$ . Thus $R_{n} (D_{\min}) \leq R_{n} (D_{\min} + ϵ) + h_{2} (ϵ / γ) + (ϵ / γ) \log_{2} ∣ \hat{X} ∣$ , since $h_{2}$ is increasing on $[0, 1 / 2]$ .

3.1step 2.1algebra

Fix $k \geq 1$ , write $n = q k + r$ with $0 \leq r < k$ , and put $a_{0} = 0$ . Repeated subadditivity gives $a_{n} \leq q a_{k} + a_{r}$ . The finite set ${a_{r} : 0 \leq r < k}$ is bounded, so ${lim sup}_{n} a_{n} / n \leq a_{k} / k$ . Taking the infimum over $k$ , while $\inf_{k} a_{k} / k \leq {lim inf}_{n} a_{n} / n$ , proves $a_{n} / n \to \inf_{k} a_{k} / k$ .

4.1F1F4step 3.1

For each fixed $n$ , the feasible block-channel sets are nested as $D$ increases, so $R_{n} (D)$ is nonincreasing. Mixing two block channels and applying [F4] shows $R_{n}$ is convex. Passing to the pointwise limit from step 3.1 preserves both monotonicity and the convexity inequality.

5.1step 4.1step 1.2step 2.2algebra∎

Taking infima over $n$ in step 2.2 gives the same inequality for $R_{b l o c k}$ . The two error terms tend to zero as $ϵ ↓ 0$ ; monotonicity from step 4.1 gives the reverse bound $R_{b l o c k} (D_{\min} + ϵ) \leq R_{b l o c k} (D_{\min})$ , proving right-continuity. If $D_{c} = D_{\min}$ , step 1.2 already gives zero on the entire feasible interval.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Finite-alphabet memoryless rate-distortion coding theorem

Statement

Let $(X_{i})_{i \geq 0}$ be iid with a pmf on a finite nonempty alphabet $X$ , let $\hat{X}$ be finite nonempty, and let $d : X \times \hat{X} \to [0, d_{\max}]$ be finite nonnegative distortion. For every $D \geq 0$ , the expected-distortion and positive-slack excess-distortion operational rates of Fixed-length operational rate-distortion functions both equal the finite information rate-distortion function of Finite-alphabet information rate-distortion function, with value $+ \infty$ when $D < D_{\min}$ .

Facts & Assumptions

Given: An iid finite-alphabet source, finite reproduction alphabet, bounded finite nonnegative distortion, and budget $D \geq 0$ .

[F1]

Finite-alphabet information rate-distortion function: $R (D)$ is the minimum test-channel mutual information in bits, with infeasible value $+ \infty$ .

[F2]

Fixed-length operational rate-distortion functions: operational rates use deterministic fixed-length codes; the expected criterion has limiting expected distortion at most $D$ , and the excess criterion requires every positive slack.

[F3]

Attainment of finite-alphabet rate-distortion minima: feasible finite test-channel minima are attained exactly for $D \geq D_{\min}$ .

[F4]

Convexity, monotonicity, and continuity of finite rate-distortion: $R$ is nonincreasing and right-continuous throughout its feasible domain.

[F5]

Finite mutual information and Finite entropy and mutual-information chain rules: finite mutual information equals $H (X) - H (X ∣ Y)$ , and conditional entropy obeys the chain rule. The source identities are stated with natural logarithms; all entropy and information terms in this proof use bits, obtained by dividing those identities by $\ln 2$ .

[F6]

Data processing for a finite Markov chain, with equality condition: finite mutual information cannot increase along a Markov chain.

[F7]

Finite conditional mutual information identities and equality: finite conditional mutual information is nonnegative, so conditioning cannot increase entropy.

[F8]

IID finite-variance weak law: averages of iid square-integrable real variables converge in probability to their common mean.

Proof

Given: The source, alphabets, distortion and budget, together with suppliers [F1]–[F8].

1.1F1F5F6F7givenalgebra

Let a deterministic length- $n$ code have $M_{n}$ messages and reconstruction ${\hat{X}}^{n}$ . Data processing [F6] gives $I (X^{n}; {\hat{X}}^{n}) \leq H (f_{n} (X^{n})) \leq \log_{2} M_{n}$ . Put $D_{n} = E d_{n} (X^{n}, {\hat{X}}^{n})$ , and let $T$ be uniform on ${0, \dots, n - 1}$ , independent of all variables; set $(X, Y) = (X_{T}, {\hat{X}}_{T})$ . Since the source symbols are iid, $H (X^{n}) = \sum_{i} H (X_{i})$ . By [F5], the chain rule, and conditioning reducing entropy from [F7], $I (X^{n}; {\hat{X}}^{n}) = \sum_{i} [H (X_{i}) - H (X_{i} ∣ X^{i - 1}, {\hat{X}}^{n})] \geq \sum_{i} I (X_{i}; {\hat{X}}_{i}) .$ Also $I (X; Y ∣ T) = n^{- 1} \sum_{i} I (X_{i}; {\hat{X}}_{i})$ , while $I (X; T) = 0$ ; the chain rule and nonnegative conditional information [F7] imply $I (X; Y) \leq I (X; Y, T) = I (X; Y ∣ T)$ . Thus $R (D_{n}) \leq I (X; Y) \leq n^{- 1} I (X^{n}; {\hat{X}}^{n}) \leq n^{- 1} \log_{2} M_{n}$ , since $E d (X, Y) = D_{n}$ .

1.2F1F3F8givenalgebra

Assume $D \geq D_{\min}$ , and choose a minimizing test channel $W (\hat{x} ∣ x)$ by [F3]. Let $Y$ have its induced output pmf, and let $(X_{i}, Y_{i})$ be iid copies of the test-channel pair. Its information density $ı (X; Y) = \log_{2} [W (Y ∣ X) / P_{Y} (Y)]$ , on positive joint support, is finite-valued because the alphabets are finite; it has mean $I : = R (D)$ . The block distortion is bounded with mean at most $D$ . The iid law of large numbers therefore gives, for every $η, δ > 0$ , $P {d_{n} (X^{n}, Y^{n}) \leq D + η, \sum_{i < n} ı (X_{i}; Y_{i}) \leq n (I + δ)} ⟶ 1.$ The distortion and information-density summands are bounded on finite alphabets, hence square-integrable; [F8] applied to each iid sequence proves both convergences in probability and the displayed joint event.

2.1F1F2F3F4step 1.1givenalgebra

For an expected-distortion code sequence with ${lim sup}_{n} D_{n} \leq D$ , eventually $D_{n} \leq D + ϵ$ , so step 1.1 and monotonicity give $R (D + ϵ) \leq n^{- 1} \log_{2} M_{n}$ . For an excess-distortion sequence and any $ϵ > 0$ , boundedness gives $D_{n} \leq D + ϵ + d_{\max} P (d_{n} > D + ϵ)$ , hence eventually $D_{n} \leq D + 2 ϵ$ ; then $R (D + 2 ϵ) \leq n^{- 1} \log_{2} M_{n}$ . Taking limsups and using [F4] as $ϵ ↓ 0$ proves both operational rates are at least $R (D)$ whenever feasible. If $D < D_{\min}$ , every reconstruction has block distortion at least $n^{- 1} \sum_{i} \min_{\hat{x}} d (X_{i}, \hat{x})$ ; its mean is $D_{\min}$ , and the iid law of large numbers makes it converge in probability to $D_{\min}$ . Thus neither operational criterion is feasible below $D_{\min}$ .

2.2F1step 1.2givenalgebra

For each source word $x^{n}$ , let $G_{n} (x^{n})$ be the reproduction words satisfying both inequalities in step 1.2. The joint probability of this event tends to one, so the source probability of the set where $P (Y^{n} \in G_{n} (X^{n}) ∣ X^{n}) < 1 / 2$ is at most twice the probability of the complement and tends to zero. On the other source words, every $y^{n} \in G_{n} (x^{n})$ satisfies $P (y^{n} ∣ x^{n}) / P_{Y}^{n} (y^{n}) \leq 2^{n (I + δ)}$ ; summing this likelihood-ratio inequality over the good set yields $P_{Y}^{n} (G_{n} (x^{n})) \geq \frac{1}{2} 2^{- n (I + δ)}$ .

3.1step 2.2givenconstructalgebra

Draw $M_{n} = ⌈ 2^{n (I + 2 δ)} ⌉$ reproduction words independently from $P_{Y}^{n}$ . For each source word in the high-probability set of step 2.2, the chance that no codeword belongs to $G_{n} (x^{n})$ is at most $(1 - q)^{M_{n}} \leq e^{- M_{n} q} \leq e^{- 2^{n δ} / 2}$ . Source words outside that set have probability tending to zero, so the expected failure probability of the random codebook tends to zero. Since the codebook alphabet is finite, for each n there is a deterministic realization whose failure probability is at most twice this expectation (and if the expectation is zero, a realization with zero failure exists).

4.1F2step 1.2step 3.1givenconstruct

Encode each source word by the first codebook word in its good set; if there is none, use a fixed default reproduction word. Decode the selected codeword. This is a deterministic fixed-length code; its rate is at most $I + 2 δ + o (1)$ . Its distortion is at most $D + η$ on success and at most $d_{\max}$ on failure. Choose $η_{j} ↓ 0$ ; for each j the failure probability is at most $1 / j$ for all sufficiently large n by step 3.1. Use increasing thresholds and at length n the largest available j=j(n). Then $j (n) \to \infty$ , expected distortion has limsup at most $D$ , and for every fixed $ϵ > 0$ , eventually $η_{j (n)} < ϵ$ , so $P (d_{n} > D + ϵ) \leq 1 / j (n) \to 0$ .

5.1F1F2step 2.1step 1.2step 2.2step 3.1step 4.1givenalgebra∎

For any target rate $R (D) + ϵ$ , choose $δ > 0$ with $2 δ < ϵ$ . Steps 1.2, 2.2, 3.1, and 4.1 give codes with both operational criteria and limiting rate at most $R (D) + 2 δ < R (D) + ϵ$ . Taking the infimum proves both operational rates are at most $R (D)$ . Together with step 2.1 this proves the theorem.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Gaussian squared-error rate-distortion function

Statement

Assume AC. Let $X \sim N (0, σ^{2})$ , where $σ^{2} \geq 0$ , and let squared error $d (x, y) = (x - y)^{2}$ be used in the standard-Borel information rate-distortion function General single-letter information rate-distortion function. For $D \geq 0$ , if $σ^{2} > 0$ , then

R (D) = {\begin{cases} + \infty, & D = 0, \\ \frac{1}{2} \log_{2}^{+} (σ^{2} / D), & D > 0, \end{cases}

where $\log_{2}^{+} (u) = \max (0, \log_{2} u)$ . If $σ^{2} = 0$ , then $R (D) = 0$ for every $D \geq 0$ .

Facts & Assumptions

Given: AC, $X \sim N (0, σ^{2})$ , $σ^{2} \geq 0$ , and $D \geq 0$ .

[A1]

The Axiom of Choice: AC is assumed by the KL and orthogonal-normal suppliers.

[F1]

General single-letter information rate-distortion function: $R (D)$ is the infimum of $I_{n a t} (X; Y) / \ln 2$ over joint laws with $X$ -marginal fixed and $E (X - Y)^{2} \leq D$ ; an empty infimum is $+ \infty$ .

[F2]

Gaussian reference-kernel mutual-information lower bound: if $X \sim N (0, σ^{2})$ , $0 < D < σ^{2}$ , and $E (X - Y)^{2} \leq D$ , then $I_{n a t} (X; Y) \geq \frac{1}{2} \ln (σ^{2} / D)$ , without a density assumption on $Y$ .

[F3]

Orthogonal transformations preserve the standard normal product law: an orthogonal transform of independent standard normals again has independent standard-normal coordinates, under AC.

[F4]

A C^1 diffeomorphism satisfies the change-of-variables formula for nonnegative Lebesgue measurable functions: under Countable Choice, an invertible linear change of variables transforms a density by the absolute determinant of its inverse. The assumed AC in [A1] implies Countable Choice by restricting its choice function to a countable family.

[F5]

Kullback–Leibler divergence is nonnegative: KL divergence between probability laws is nonnegative.

[F6]

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique: the product of the probability laws used below exists and has the rectangle/product-density formula.

[F7]

Standard normal and normal laws: a nondegenerate normal law has its everywhere-positive affine Gaussian density, which is bounded.

[F8]

Continuity from above when one set has finite measure: a finite measure is continuous along a decreasing sequence of measurable sets.

Proof

Given: The hypotheses and suppliers [A1], [F1]–[F8].

1.1A1F1F2givenalgebra

Suppose $σ^{2} > 0$ and $0 < D < σ^{2}$ . By [F2], every feasible joint law has mutual information in nats at least $\frac{1}{2} \ln (σ^{2} / D)$ ; division by $\ln 2 > 0$ and taking the infimum in [F1] gives $R (D) \geq \frac{1}{2} \log_{2} (σ^{2} / D)$ .

1.2A1F1F5given

If $σ^{2} > 0$ and $D \geq σ^{2}$ , the constant reconstruction $Y = 0$ has distortion $σ^{2}$ and mutual information zero; [F5] makes zero the minimum, so $R (D) = 0$ .

1.3A1F1F6F7F8givenalgebra

Suppose $σ^{2} > 0$ and $D = 0$ . Every feasible coupling satisfies $X = Y$ almost surely because the nonnegative random variable $(X - Y)^{2}$ has expectation zero. The diagonal ${(x, y) : x = y}$ has joint probability one. By [F7] the normal density is bounded by $(2 π σ^{2})^{- 1 / 2}$ , so under the product law, for every $h > 0$ , the event $∣ X - Y ∣ \leq h$ has probability at most $2 h (2 π σ^{2})^{- 1 / 2}$ . For $h = 1 / (n + 1)$ , $n \geq 0$ , these measurable events decrease to the diagonal; [F8] therefore makes its product probability zero. Thus the joint law is not absolutely continuous with respect to the product of its marginals and its KL, hence its mutual information, is infinite. Every feasible coupling has this value, proving $R (0) = + \infty$ .

2.1A1F1F3F4F6F7step 1.1givenconstructalgebra

Put $a = \sqrt{σ^{2} - D} > 0$ , $b = \sqrt{D} > 0$ , and let $U, V$ be independent standard normals. Set $Y = a U$ , $X = a U + b V$ . The orthogonal matrix $σ^{- 1} (\begin{array}{cc} a & b \\ - b & a \end{array})$ and [F3] show $X \sim N (0, σ^{2})$ ; also $E (X - Y)^{2} = b^{2} = D$ . By [F7], $U, V$ have product density; the invertible map $(u, v) \mapsto (x, y) = (a u + b v, a u)$ has determinant $- a b$ , so [F4] gives joint density $(2 π a b)^{- 1} \exp [- y^{2} / (2 a^{2}) - (x - y)^{2} / (2 b^{2})]$ . The product of the $N (0, σ^{2})$ and $N (0, a^{2})$ marginals has density $(2 π σ a)^{- 1} \exp [- x^{2} / (2 σ^{2}) - y^{2} / (2 a^{2})]$ . Their log-density ratio has expectation $\ln (σ / b) - \frac{1}{2} + \frac{1}{2} = \frac{1}{2} \ln (σ^{2} / D)$ ; [F1] therefore gives a feasible joint law attaining the lower bound in step 1.1.

3.1A1F1F5given∎

If $σ^{2} = 0$ , then $X = 0$ almost surely. The constant reconstruction $Y = 0$ has zero distortion and zero mutual information, while [F5] gives a nonnegative lower bound for every feasible coupling. Therefore $R (D) = 0$ for every $D \geq 0$ . These branches prove the statement.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck pendingOpen item page →

Finite-dimensional Gaussian vector squared-error rate-distortion function

Statement

Assume AC. Let $m \geq 1$ , let $X = (X_{1}, \dots, X_{m})$ have independent coordinates $X_{i} \sim N (0, λ_{i})$ with $λ_{i} \geq 0$ , and let $Y \in R^{m}$ be any jointly distributed reconstruction. Use squared Euclidean distortion $E ∥ X - Y ∥_{2}^{2}$ . For $D \geq 0$ , the standard-Borel information rate-distortion function of General single-letter information rate-distortion function in bits is

R (D) = {\begin{cases} + \infty, & D = 0 < \sum_{i} λ_{i}, \\ \frac{1}{2} \sum_{i = 1}^{m} \log_{2}^{+} (λ_{i} / θ), & 0 < D < \sum_{i} λ_{i}, \\ 0, & D \geq \sum_{i} λ_{i}, \end{cases}

where $\log_{2}^{+} (0) : = 0$ (and $\log_{2}^{+} (u) = \max (0, \log_{2} u)$ for $u > 0$ ), and in the middle case $θ$ is the unique positive solution of $\sum_{i} \min (λ_{i}, θ) = D$ . If all $λ_{i} = 0$ , then $R (D) = 0$ for every $D \geq 0$ .

Facts & Assumptions

Given: AC, finite $m \geq 1$ , nonnegative $λ_{i}$ , a Gaussian vector $X$ with independent coordinates of those variances, and distortion budget $D \geq 0$ .

[A1]

The Axiom of Choice: AC is assumed by the standard-Borel KL, conditional-law, and Gaussian suppliers.

[F1]

General single-letter information rate-distortion function and Mutual information for standard-Borel random elements: the rate is the infimum over couplings with the fixed source marginal and expected distortion at most $D$ ; in nats, mutual information is the joint-law KL from the product of its marginals.

[F2]

Measure-theoretic mutual information and Mutual-information chain rule without subtracting infinities give $I ((Z, V); U) = I (Z; U) + I (V; U ∣ Z)$ as an extended nonnegative sum. By KL is invariant under a measurable bijection, swapping the two unconditioned coordinates sends the joint law and its product reference to the corresponding reversed laws; fixing a conditioning coordinate sends its same-marginal conditional-product reference to the reversed reference as well. Thus $I (U; V) = I (V; U)$ and $I (U; V ∣ W) = I (V; U ∣ W)$ . Combining these symmetries with the stated first-argument rule proves $I (U; (Z, V)) = I (U; Z) + I (U; V ∣ Z) .$ For an additional standard-Borel W, apply this identity to the conditional law given $W = w$ for almost every w and integrate. KL chain rule for standard-Borel disintegrations, applied with the common W marginal, identifies the three integrals as $I (U; (Z, V) ∣ W) = I (U; Z ∣ W) + I (U; V ∣ Z, W) .$ All integrations and rearrangements here concern nonnegative KL values; no possibly infinite term is subtracted.

[F3]

Conditional mutual information by a same-marginal product law: conditional mutual information is a KL divergence and hence is nonnegative by Kullback–Leibler divergence is nonnegative.

[F4]

Gaussian reference-kernel mutual-information lower bound: if $X_{i} \sim N (0, λ_{i})$ , $0 < δ < λ_{i}$ , and $E (X_{i} - Y_{i})^{2} \leq δ$ , then $I_{n a t} (X_{i}; Y_{i}) \geq \frac{1}{2} \ln (λ_{i} / δ)$ .

[F5]

Finite Gaussian water-level allocation: under a total distortion constraint, the minimum of the coordinate rates $\frac{1}{2} \log_{2}^{+} (λ_{i} / δ_{i})$ is given by the unique water level and endpoint branches stated there.

[F6]

Standard normal and normal laws: standard-normal laws have density $(2 π)^{- 1 / 2} e^{- z^{2} / 2}$ , and $N (0, s)$ is its scaling by $\sqrt{s}$ .

[F7]

[F8]

Continuity from above when one set has finite measure: a finite measure is continuous along a decreasing sequence of measurable sets.

[F9]

Orthogonal transformations preserve the standard normal product law: under AC, an orthogonal transform of independent standard normals again has independent standard-normal coordinates.

[F10]

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique: the finite product laws of independent standard normals exist and have the product-density formula.

[F11]

Finite-dimensional Euclidean space with its Borel sigma-algebra is standard Borel: for every finite $m \geq 1$ , $R^{m}$ with its Borel sigma-algebra is standard Borel.

Proof

Given: The hypotheses and suppliers [A1], [F1]–[F11].

1.1A1F1F2F3F11given

Write $δ_{i} = E (X_{i} - Y_{i})^{2}$ , so $\sum_{i} δ_{i} \leq D$ . Repeated use of [F2] expands $I_{n a t} (X^{m}; Y^{m})$ as $\sum_{i} I_{n a t} (X_{i}; Y^{m} ∣ X_{1}^{i - 1})$ . Put $W_{i} = X_{1}^{i - 1}$ ; for $i = 1$ this is a constant empty tuple and the conditional identities reduce to their unconditioned forms, while for $i > 1$ its Euclidean value space is standard Borel by [F11]. Reorder $Y^{m}$ as $(Y_{i}, Y_{[m] ∖ {i}})$ by the coordinate-bijection invariance in [F2]. Its derived second-argument conditional rule gives $I_{n a t} (X_{i}; Y^{m} ∣ W_{i}) = I_{n a t} (X_{i}; Y_{i} ∣ W_{i}) + I_{n a t} (X_{i}; Y_{[m] ∖ {i}} ∣ W_{i}, Y_{i}) \geq I_{n a t} (X_{i}; Y_{i} ∣ W_{i}),$ by nonnegativity [F3]; the empty tuple has zero information.

1.2A1F1F3F4F6F8givenalgebra

If $λ_{i} > 0$ and $0 < δ_{i} < λ_{i}$ , [F4] gives $I_{n a t} (X_{i}; Y_{i}) \geq \frac{1}{2} \ln (λ_{i} / δ_{i})$ . If $δ_{i} \geq λ_{i}$ , nonnegativity gives $I_{n a t} (X_{i}; Y_{i}) \geq 0 = \frac{1}{2} \ln^{+} (λ_{i} / δ_{i})$ ; if $λ_{i} = 0$ , the same zero lower bound holds. If $λ_{i} > 0 = δ_{i}$ , then $X_{i} = Y_{i}$ almost surely. Writing $f_{i}$ for its bounded normal density, the product law assigns probability at most $2 h ∥ f_{i} ∥_{\infty}$ to $∣ x_{i} - y_{i} ∣ \leq h$ , for each $h > 0$ ; taking $h = 1 / n$ and applying [F8] to these decreasing neighborhoods gives product probability zero on the diagonal. The joint law gives the diagonal probability one, so the KL is infinite.

2.1A1F2F3F11step 1.1algebra

Independence gives $P_{X_{i} W_{i}} = P_{X_{i}} \otimes P_{W_{i}}$ , so $I_{n a t} (X_{i}; W_{i}) = 0$ from the KL definition. The derived second-argument rule in [F2] gives $I_{n a t} (X_{i}; (W_{i}, Y_{i})) = 0 + I_{n a t} (X_{i}; Y_{i} ∣ W_{i}) = I_{n a t} (X_{i}; Y_{i} ∣ W_{i}) .$ A coordinate swap and the other expansion give $I_{n a t} (X_{i}; (W_{i}, Y_{i})) = I_{n a t} (X_{i}; (Y_{i}, W_{i})) = I_{n a t} (X_{i}; Y_{i}) + I_{n a t} (X_{i}; W_{i} ∣ Y_{i}) \geq I_{n a t} (X_{i}; Y_{i}) .$ These identities remain valid when an information value is infinite, since only the explicitly zero term is removed and all other terms are nonnegative. Thus $I_{n a t} (X^{m}; Y^{m}) \geq \sum_{i} I_{n a t} (X_{i}; Y_{i})$ .

3.1step 2.1step 1.2givenalgebra

For each coordinate put ${\overset{ˉ}{δ}}_{i} = \min (δ_{i}, λ_{i})$ when $λ_{i} > 0$ , and ${\overset{ˉ}{δ}}_{i} = 0$ when $λ_{i} = 0$ . Then $\sum_{i} {\overset{ˉ}{δ}}_{i} \leq D$ . step 1.2 and step 2.1 give the lower bound $I_{n a t} (X^{m}; Y^{m}) \geq \frac{1}{2} \sum_{i : λ_{i} > 0} \max {0, \ln (λ_{i} / {\overset{ˉ}{δ}}_{i})}$ nats, with the sum interpreted as $+ \infty$ if any positive-variance coordinate has ${\overset{ˉ}{δ}}_{i} = 0$ . Dividing by $\ln 2$ converts this to the corresponding coordinate-rate sum in bits.

4.1F1F3F5step 1.2step 3.1givencases

If $0 < D < \sum_{i} λ_{i}$ , applying [F5] to $({\overset{ˉ}{δ}}_{i})$ minimizes the bit-valued coordinate-rate sum under $\sum_{i} {\overset{ˉ}{δ}}_{i} \leq D$ and gives the stated water-level lower bound for $I_{n a t} (X^{m}; Y^{m}) / \ln 2$ , hence for the rate in [F1]. If $D = 0 < \sum_{i} λ_{i}$ , some positive-variance coordinate has zero error, so step 1.2 makes the information infinite. If $D \geq \sum_{i} λ_{i}$ , nonnegativity is the lower bound zero; the all-zero variance case has the same lower bound for every $D$ .

5.1A1F1F3F5F6F7F9F10step 4.1givenconstructalgebra

In the middle case let $δ_{i}^{*} = \min (λ_{i}, θ)$ . For $λ_{i} \leq θ$ , choose the constant reconstruction $Y_{i} = 0$ . For $λ_{i} > θ$ , put $a_{i} = \sqrt{λ_{i} - θ}$ , $b = \sqrt{θ}$ , and take independent standard normals $U_{i}, V_{i}$ using the finite product law in [F10]; set $Y_{i} = a_{i} U_{i}$ , $X_{i} = a_{i} U_{i} + b V_{i}$ . The orthogonal rotation with first row $(a_{i}, b) / \sqrt{λ_{i}}$ and [F9] gives the required $N (0, λ_{i})$ source; the squared error has mean $b^{2} = θ$ . By [F6], [F7] and the product normal density, the joint density of $(X_{i}, Y_{i})$ is $(2 π a_{i} b)^{- 1} \exp [- y_{i}^{2} / (2 a_{i}^{2}) - (x_{i} - y_{i})^{2} / (2 b^{2})]$ ; dividing by the product of the source and reconstruction densities gives expected log ratio $\frac{1}{2} \ln (λ_{i} / θ)$ . Choose all coordinate pairs independently. Their joint and product-marginal laws factor, and the log density ratio is the sum of the coordinate log ratios, each integrable; [F1] therefore makes the vector mutual information the sum $\frac{1}{2} \sum_{i : λ_{i} > 0} \ln^{+} (λ_{i} / θ)$ nats. By [F1], the rate is this value divided by $\ln 2$ , so the construction attains the bit-valued lower bound.

6.1F1step 4.1givencases∎

If $D \geq \sum_{i} λ_{i}$ , choose $Y = 0$ ; the error is the total variance and mutual information is zero. If every $λ_{i} = 0$ , the same constant reconstruction has zero error and zero mutual information for all $D \geq 0$ . These constructions attain the remaining lower bounds and complete the proof.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passOpen item page →

Random-cut stationary ergodic block-channel approximation

Statement

Assume AC. Let $(X_{t})_{t \in Z}$ be a stationary ergodic source on a finite alphabet $X$ , let $\hat{X}$ be finite nonempty, and let $d : X \times \hat{X} \to [0, d_{\max}]$ be bounded. For any feasible $D \geq D_{\min}$ and any $r > R_{b l o c k} (D)$ , there is a jointly stationary ergodic pair $(X_{t}, {\hat{X}}_{t})_{t \in Z}$ with the given source marginal, $E d (X_{0}, {\hat{X}}_{0}) \leq D$ , and

\underset{n \to \infty}{lim sup} \frac{1}{n} I_{2} (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1}) < r bits per symbol,

where $I_{2} : = I_{n a t} / \ln 2$ for the measure-theoretic mutual information of Measure-theoretic mutual information.

Facts & Assumptions

Given: AC; a two-sided stationary ergodic finite-alphabet source; bounded finite distortion; feasible $D$ ; and $r > R_{b l o c k} (D)$ .

[A1]

The Axiom of Choice: the product and conditional-law suppliers below assume AC.

[F1]

Finite-alphabet stationary source: source stationarity and ergodicity refer to the two-sided left shift.

[F2]

Stationary finite-block information rate-distortion function: $R_{k} (D)$ is the minimum length- $k$ mutual information per symbol at expected block distortion at most $D$ , and $R_{b l o c k} (D) = \inf_{k} R_{k} (D)$ .

[F3]

Stationary block rate-distortion limit and endpoint continuity: the finite block minima are attained whenever feasible and their normalized limit equals $R_{b l o c k} (D)$ .

[F4]

By Assuming countable choice, $L (R^{n})$ is a sigma-algebra containing every elementary set and $λ_{n}$ is a complete measure extending elementary volume, countable choice makes Lebesgue measure countably additive, so its restriction to Borel subsets of $[0, 1]$ is a measure. The unit-uniform law on $[0, 1]$ is this restricted measure; [A1] gives countable choice and A box in $R^{n}$ with parameters $a_{i} \leq b_{i}$ is Lebesgue measurable of measure $\prod_{i < n} (b_{i} - a_{i})$ , whichever of its faces are included gives $λ ([0, 1]) = 1$ , so Probability measures and probability spaces makes it a probability. The unit interval with its Borel structure is standard Borel, A countable discrete measurable space is standard Borel, and Finite products of standard Borel spaces are standard Borel make ${0, 1} \times [0, 1]$ a standard-Borel coordinate space. AC supplies countable choice by The Axiom of Choice implies countable choice, so Under the Axiom of Countable Choice, countable products and $G_{δ}$ subspaces of Polish spaces are Polish makes its countable product Polish; Assuming countable choice, a countable product of second countable spaces is second countable gives a countable cylinder basis, showing its Borel sigma-algebra equals the product sigma-algebra. Finite product laws exist by For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique, and Assuming the Axiom of Choice, Kolmogorov extension for arbitrary families of standard Borel coordinate spaces extends their consistent independent marginals to the two-sided marker-seed process.

[F5]

Measure-theoretic mutual information, Mutual-information chain rule without subtracting infinities, and Conditional mutual information by a same-marginal product law: standard-Borel mutual information is the joint-law KL in nats, obeys the extended chain rule, and conditional information is nonnegative. In this proof write $I_{2} : = I_{n a t} / \ln 2$ and scale conditional information by the same positive factor, so all information bounds are in bits. A measurable coordinate swap preserves the joint law and its product reference, and, with a conditioning coordinate fixed, its same-marginal conditional-product reference. Hence mutual information and conditional mutual information are symmetric in their two unconditioned variables; the same holds after the common conversion to bits. KL is invariant under a measurable bijection

[F6]

Data processing for a finite Markov chain, with equality condition: for finite variables, adding or discarding a stochastic postprocessing cannot increase mutual information.

[F7]

Birkhoff pointwise ergodic theorem: time averages of an integrable function converge almost surely to a finite invariant function. In the bounded ergodic case used here, step 1.3 identifies that limit with the mean.

[F8]

The countable product marker space ${0, 1}^{Z}$ with its product sigma-algebra is standard Borel by the countable-product Polish and countable-cylinder-basis argument in [F4], using the product-topology, product-sigma-algebra and standard-Borel conventions The product set $\prod_{i \in I} X_{i}$ of functions choosing a point in each factor, the projections, the box topology, and the product topology as the initial topology of the projections; the empty product is a one-point space, The product sigma-algebra and its finite iterates, The Borel sigma-algebra of a topological space, and Standard Borel spaces.

Proof

Given: The hypotheses and suppliers [A1], [F1]–[F7].

1.1F2F3givenchoose

By [F2]–[F3], choose $k \geq 1$ and a length- $k$ test channel $W_{k}$ whose expected normalized distortion is at most $D$ . Write $I_{k} : = I_{2} (X_{0}^{k - 1}; {\hat{X}}_{0}^{k - 1})$ bits for this channel and $r_{k} : = I_{k} / k$ . The choice can be made with $r_{k} < r$ because $R_{b l o c k} (D) = \inf_{k} R_{k} (D) < r$ and the finite-block minimum is attained.

1.2A1F4F5givenconstruct

Fix $p \in (0, 1)$ . By [F4], the consistent finite-dimensional product laws of a mutually independent family $(B_{t}, U_{t})_{t \in Z}$ , with each $B_{t} \sim B e r n o u l l i (p)$ and each $U_{t}$ uniform on $[0, 1]$ , extend to a probability law $P_{M}$ on $Ω_{M} = ({0, 1} \times [0, 1])^{Z}$ with its product sigma-algebra; the marker and seed processes are independent. Let $(Ω_{X}, P_{X}, T)$ be the source shift system and form the independent product extension $(Ω_{X} \times Ω_{M}, P_{X} \otimes P_{M}, T \times S)$ , where $S$ is the marker-seed shift. The product measure exists by [F4], and its rectangle formula makes the source independent of both marker and seed processes. Almost surely there are marker times $B_{t} = 1$ arbitrarily far in both directions: for each fixed starting index, the probability of no marker in the next $N$ sites is $(1 - p)^{N} \to 0$ , and a countable union handles all starting indices. Thus the marker set partitions $Z$ into finite segments between consecutive markers.

1.3F1F4F7givenalgebra

The product of the source system and the iid marker-seed shift is ergodic. To verify this, take two bounded real-valued rectangle cylinder functions $f_{1} (X) g_{1} (B, U)$ and $f_{2} (X) g_{2} (B, U)$ . For all sufficiently large shifts $n$ , the iid-coordinate windows of $g_{1}$ and $g_{2} \circ S^{n}$ are disjoint, so their expectation factors as $E g_{1} E g_{2}$ . For the source factor, [F7] gives almost-sure convergence of $N^{- 1} \sum_{n = 0}^{N - 1} f_{2} (T^{n} X)$ to a finite invariant function $f_{2}^{*}$ . Ergodicity makes $f_{2}^{*}$ constant almost surely: for each rational $a$ , the limsup orbit set ${lim sup}_{n \to \infty} T^{- n} {f_{2}^{*} > a}$ is strictly invariant and differs from ${f_{2}^{*} > a}$ by a null set, so it has probability zero or one; the rational level sets then force a constant value. Since $f_{2}$ is bounded, dominated convergence and preservation of the source law show this constant is $E f_{2}$ . Thus the time averages of $f_{2}$ converge almost surely to $E f_{2}$ , and bounded convergence gives $\frac{1}{N} \sum_{n = 0}^{N - 1} E [f_{1} (X) f_{2} (T^{n} X)] ⟶ E f_{1} E f_{2} .$ The Cesàro correlations of the rectangle functions therefore converge to the product of their means. Their finite linear combinations are dense in real product $L^{2}$ : indicators of measurable rectangles form a generating $π$ -system, and the class of sets whose indicators lie in the $L^{2}$ -closure of their span is a Dynkin class, since increasing unions converge in $L^{2}$ on a probability space. The $π$ - $λ$ theorem and density of simple functions give the claim. Cauchy–Schwarz and shift invariance extend the correlation limit to every real $L^{2}$ function. If $A$ is invariant, its indicator has correlation $P (A)$ at every shift, while the limit is $P (A)^{2}$ ; hence $P (A) \in {0, 1}$ .

2.1F1step 1.2givenconstruct

Fix a pointwise minimizer ${\hat{x}}_{*} (x)$ for each source letter. For a segment beginning at marker $s$ and ending just before the next marker $s + L$ , divide its first $k ⌊ L / k ⌋$ sites into consecutive length- $k$ blocks. At each such block start use its seed $U_{t}$ and the finite inverse-cumulative rule to sample an output block from $W_{k} (\cdot ∣ X_{t}^{t + k - 1})$ ; on the remaining $L m o d k < k$ sites, output ${\hat{x}}_{*} (X_{t})$ . On the shift-invariant null set where markers do not occur arbitrarily far in both directions, define ${\hat{X}}_{t} = {\hat{x}}_{*} (X_{t})$ for every $t$ . The resulting map is measurable because each good-segment event is determined by finitely many marker coordinates and each seed selects among finitely many outputs by measurable intervals; it is shift-equivariant because all rules translate with the markers.

3.1F1step 2.1step 1.3

The pair $(X, \hat{X})$ is a shift-commuting factor of the ergodic product system from step 1.3, so it is stationary and ergodic: the preimage of a shift-invariant event in the factor is shift-invariant in the product and therefore has probability zero or one. Its source marginal is unchanged because the construction leaves X fixed.

3.2step 1.2step 2.1algebra

Let $α$ be the probability that coordinate zero lies in a leftover suffix. A segment of length $ℓ$ has $ℓ m o d k$ leftover sites. Summing over its possible start and length gives $α = p^{2} \sum_{ℓ = 1}^{\infty} (ℓ m o d k) (1 - p)^{ℓ - 1} \leq (k - 1) p^{2} \sum_{ℓ = 1}^{\infty} (1 - p)^{ℓ - 1} = (k - 1) p .$ Marker events in this sum specify a cut at the segment start, no intervening marker, and a cut at the end; the leftover site is one of the final $ℓ m o d k$ positions.

4.1F1F2step 2.1step 3.2givenalgebra

The marker process is independent of X. For any length- $n$ window, condition on the markers and sum distortion over all test-channel blocks fully contained in the window; each such block has the stationary length- $k$ source law, so its expected total distortion is at most $k D$ . At most two blocks intersect the window without being contained, and their total distortion is bounded by $2 k d_{\max}$ . Leftover sites have expected distortion $D_{\min}$ each. Divide by $n$ , take expectations, and let $n \to \infty$ ; the boundary contribution vanishes, while stationarity makes the expected mean distortion equal to $E d (X_{0}, {\hat{X}}_{0})$ for every n. Since the expected leftover fraction is $α$ , this yields $E d (X_{0}, {\hat{X}}_{0}) \leq (1 - α) D + α D_{\min} \leq D$ .

4.2A1F1F4F5F6F8step 1.2step 2.1step 3.2givenalgebra

Let E be the independent marker process B, leaving the independent uniform seeds unconditioned. Its value space ${0, 1}^{Z}$ is standard Borel by [F4] and [F8]. Put $U = X_{0}^{n - 1}$ and $V = {\hat{X}}_{0}^{n - 1}$ . Independence in step 1.2 gives $P_{U E} = P_{U} \otimes P_{E}$ , so $I_{2} (U; E) = D (P_{U} \otimes P_{E} ∥ P_{U} \otimes P_{E}) / \ln 2 = 0$ . Coordinate-swap invariance and the first-argument chain rule in [F5] now give $I_{2} (U; (V, E)) = I_{2} ((E, V); U) = I_{2} (E; U) + I_{2} (V; U ∣ E) = 0 + I_{2} (U; V ∣ E) .$ Expanding instead in the order $(V, E)$ gives $I_{2} (U; (V, E)) = I_{2} (U; V) + I_{2} (U; E ∣ V) \geq I_{2} (U; V)$ . Thus $I_{2} (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1}) \leq I_{2} (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1} ∣ E)$ , using only nonnegative extended sums and the explicitly zero independent term. Conditional on E, outputs from distinct test-channel blocks are sampled independently according to $W_{k}$ , and leftover outputs are deterministic. Enlarge the source window to include every source coordinate in a full length- $k$ block intersecting $[0, n - 1]$ , and enlarge the output to include each such full test-channel block output plus the leftover reconstructions inside the window. The original source and output windows are coordinate projections of these enlarged finite vectors, so [F6], applied conditionally on each marker realization, bounds the original information by the enlarged information. Conditional output entropy is subadditive across block outputs and leftover symbols. Given the enlarged source and E, the block outputs are independent and the leftover symbols are deterministic, so conditional output entropy is the sum of the block conditional entropies. Each length- $k$ block has the stationary source law followed by $W_{k}$ , and hence contributes $I_{k}$ bits; each leftover symbol contributes at most $\log_{2} ∣ \hat{X} ∣$ bits. There are at most $n / k + 2$ intersecting channel blocks, and stationarity makes the expected number of leftover sites in the window $n α$ . Therefore $\frac{1}{n} I_{2} (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1}) \leq (\frac{1}{k} + \frac{2}{n}) I_{k} + α \log_{2} ∣ \hat{X} ∣ .$

5.1F1step 1.1step 3.1step 3.2step 4.1step 4.2givenalgebra∎

Since $r_{k} < r$ , choose $p > 0$ small enough that $(k - 1) p \log_{2} ∣ \hat{X} ∣ < r - r_{k}$ (if the logarithm is zero, any $p \in (0, 1)$ works). Taking $n \to \infty$ in step 4.2 and using step 3.2 yields a limiting upper information rate at most $r_{k} + (k - 1) p \log_{2} ∣ \hat{X} ∣ < r$ . step 3.1 and step 4.1 give the required stationary ergodic pair and distortion bound.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passOpen item page →

Blahut–Arimoto certified gap and termination

Statement

For the exact-real iteration of Finite-alphabet Blahut–Arimoto rate-distortion algorithm, let $L_{β}^{*}$ be the minimum of $I_{n a t} (X; \hat{X}) + β E d$ over all finite test channels. For every minimizer's output law $q^{*}$ , every integer $t \geq 0$ , and full-support initialization $q_{0}$ ,

0 \leq L_{t} - L_{β}^{*} \leq \frac{D (q^{*} ∥ q_{0})}{t + 1} .

For uniform $q_{0}$ , this is at most $\ln n / (t + 1)$ . At every iteration the a-posteriori bound $L_{t} - L_{β}^{*} \leq \ln γ_{t}$ holds; moreover $γ_{t} \to 1$ , including when all minimizers lie on the boundary of the reproduction simplex. Thus exact arithmetic eventually meets every positive tolerance, and under the algorithm's rational representability conditions its specified interval procedure eventually returns a certified iterate.

Facts & Assumptions

Given: Positive finite source probabilities, finite nonnegative distortion and $β$ , and a full-support initial reproduction law as in the algorithm.

[F1]

Finite-alphabet Blahut–Arimoto rate-distortion algorithm: $W_{t} (j ∣ i) = q_{t} (j) e^{- β d_{i j}} / Z_{i} (q_{t})$ , $q_{t + 1} = p W_{t}$ , and $γ_{t} = \max_{j} \sum_{i} p_{i} e^{- β d_{i j}} / Z_{i} (q_{t})$ . Its exact-real recurrence accepts arbitrary full-support $q_{0}$ ; its interval procedure additionally requires rational $p_{i}, d_{i j}, β, q_{0} (j)$ and positive rational $τ$ .

[F2]

Finite mutual information: finite mutual information is the finite joint-KL sum.

[F3]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite KL divergence is nonnegative and vanishes only for equal laws.

[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 subset of a finite-dimensional compact simplex 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 function on a nonempty compact metric space attains its minimum.

[F6]

Certified range evaluation for elementary real and complex functions and Certified real elementary-function evaluations enclose their ranges: each finite interval returned for an expression DAG encloses all exact node values.

[F7]

Directed dyadic rounding encloses with explicit underflow and overflow bounds and Range-reduced exponential, logarithm and arctangent series have certified tails: directed endpoint error and the exp/log series tails tend to zero as precision and truncation increase on bounded inputs.

Proof

Given: The algorithm's data and suppliers [F1]–[F7].

1.1F1F2F3givenalgebra

For every reproduction pmf $q$ , including boundary points of the simplex, define $G (W, q) : = \sum_{i} p_{i} D (W (\cdot ∣ i) ∥ q) + β E d$ , where a row divergence is $+ \infty$ if that row puts positive mass outside the support of $q$ . Since each $p_{i} > 0$ , $G (W, q)$ is finite only when every row is supported on ${j : q (j) > 0}$ . Also $Z_{i} (q) > 0$ for every pmf $q$ , because $e^{- β d_{i j}} > 0$ and $q$ has total mass one. Define $W_{q} (j ∣ i) = q (j) e^{- β d_{i j}} / Z_{i} (q)$ , which is zero off that support. For every supported row, expansion of finite KL sums gives $D (W (\cdot ∣ i) ∥ q) + β \sum_{j} W (j ∣ i) d_{i j} = D (W (\cdot ∣ i) ∥ W_{q} (\cdot ∣ i)) - \ln Z_{i} (q) .$ Nonnegativity [F3] shows that $W_{q}$ minimizes each row; unsupported rows have infinite objective and cannot improve it. Therefore $F (q) : = \min_{W} G (W, q) = - \sum_{i} p_{i} \ln Z_{i} (q)$ on the closed simplex. If $q_{W}$ is the output law of $W$ , expansion on the common support gives $G (W, q) = L_{β} (W) + D (q_{W} ∥ q)$ when $q_{W}$ is supported on $q$ ; otherwise both sides are $+ \infty$ .

1.2F1F6F7givenalgebra

Fix an integer $t$ . The recurrence through $t$ is a finite expression DAG with positive exact divisors and logarithm arguments, since every iterate has full support. The algorithm uses mantissa precision $r^{2}$ , exponent bounds $- r, r$ , and truncation $N = r$ . Uniformly for each endpoint $x$ in a fixed bounded input interval, the evaluator in [F6] uses $s = r + 2$ squarings after reducing to $u = x / 2^{s}$ . On a fixed bounded neighborhood of $x$ , [F7] bounds the initial series error by $C^{r + 1} 2^{- s (r + 1)} / (r + 1)!$ for some fixed $C \geq 1$ , and the endpoint rounding error by $O (2^{- r^{2}})$ . The exact intermediate exponentials are uniformly bounded; on a fixed larger bounded interval, squaring is Lipschitz with some fixed constant $A > 1$ . Thus the total endpoint error after $s$ rounded squarings is at most $A^{r + 2}$ times the initial error plus $O (A^{r + 2} 2^{- r^{2}})$ , which tends to zero. The exact exponential is Lipschitz on that interval, so a shrinking input interval has a shrinking output enclosure. This bound also ensures the rounded intermediates remain in that larger interval for all sufficiently large $r$ . Logarithm range reduction on a fixed positive compact interval uses only finitely many bins; its series tails tend to zero, and its endpoint operations are continuous there. Rational input rounding likewise converges by [F7]. Applying these bounds successively to the finite recurrence DAG shows every requested enclosure width tends to zero. All exact positive divisors and logarithm arguments are eventually separated from zero, and the expanding exponent range eventually avoids overflow. The finite maximum forming $G_{t}$ preserves convergence, so its logarithm enclosure also shrinks to $\ln γ_{t}$ . Soundness follows from [F6]. Hence each fixed- $t$ precision loop terminates with the required width.

2.1F2F3F4F5step 1.1givenalgebra

The channel simplex is closed and bounded in finite-dimensional Euclidean space, hence compact by [F4]. The finite mutual-information objective is continuous by its entropy expression and continuity of $- u \ln u$ at zero; distortion is linear. Thus [F5] gives a minimizer $W^{*}$ . Put $q^{*} = q_{W^{*}}$ , $P^{*} (i, j) = p_{i} W^{*} (j ∣ i)$ . Step 1.1 gives $G (W, q) \geq L_{β} (W) \geq L_{β}^{*}$ for every $W, q$ , while $G (W^{*}, q^{*}) = L_{β}^{*}$ because $q^{*}$ is the output marginal of $W^{*}$ . Therefore $F (q^{*}) = L_{β}^{*}$ and $q^{*}$ minimizes the boundary-extended $F$ .

2.2F1F2F3step 1.1algebra

For each iterate set $P_{t} (i, j) = p_{i} W_{t} (j ∣ i)$ . The identities in step 1.1 give $F (q_{t}) = L_{t} + D (q_{t + 1} ∥ q_{t}), F (q_{t + 1}) \leq G (W_{t}, q_{t + 1}) = L_{t} .$ Consequently $L_{t + 1} \leq F (q_{t + 1}) \leq L_{t}$ : the objective sequence is nonincreasing.

3.1F2F3step 2.1step 2.2algebra

Expand the finite joint divergence using the update formula for $W_{t}$ : $D (P^{*} ∥ P_{t}) = L_{β}^{*} + D (q^{*} ∥ q_{t}) - F (q_{t}) .$ Indeed $\ln W_{t} (j ∣ i) = \ln q_{t} (j) - β d_{i j} - \ln Z_{i} (q_{t})$ ; multiplying $\ln (W^{*} / W_{t})$ by $p_{i} W_{i j}^{*}$ and summing gives the displayed identity. Marginalizing the joint laws over the reproduction coordinate and expanding the finite conditional sums gives $D (P^{*} ∥ P_{t}) = D (q^{*} ∥ q_{t + 1}) + \sum_{j : q_{j}^{*} > 0} q_{j}^{*} D (P^{*} (X \in \cdot ∣ j) ∥ P_{t} (X \in \cdot ∣ j)) \geq D (q^{*} ∥ q_{t + 1}),$ where [F3] supplies nonnegativity. Thus $F (q_{t}) - L_{β}^{*} \leq D (q^{*} ∥ q_{t}) - D (q^{*} ∥ q_{t + 1})$ . Since $L_{t} \leq F (q_{t})$ , the same upper bound holds for $L_{t} - L_{β}^{*}$ .

3.2F1step 2.1step 2.2algebra

Define $s_{j} (q_{t}) = \sum_{i} p_{i} e^{- β d_{i j}} / Z_{i} (q_{t}) = q_{t + 1, j} / q_{t, j}$ . For $a_{i j} = e^{- β d_{i j}} / Z_{i} (q_{t})$ , concavity of $\ln$ and $F (q^{*}) = L_{β}^{*}$ give $F (q_{t}) - L_{β}^{*} = \sum_{i} p_{i} \ln (\sum_{j} q_{j}^{*} a_{i j}) \leq \ln (\sum_{j} q_{j}^{*} s_{j} (q_{t})) \leq \ln \max_{j} s_{j} (q_{t}) = \ln γ_{t} .$ Since $L_{t} \leq F (q_{t})$ , this proves the stated a-posteriori certificate. Also $\sum_{j} q_{t, j} s_{j} (q_{t}) = 1$ , so $γ_{t} \geq 1$ .

4.1F3step 2.2step 3.1algebra

Summing step 3.1 for $s = 0, \dots, t$ telescopes to $\sum_{s = 0}^{t} (L_{s} - L_{β}^{*}) \leq D (q^{*} ∥ q_{0})$ , since KL is nonnegative. By step 2.2 the gaps are nonincreasing, so $(t + 1) (L_{t} - L_{β}^{*}) \leq D (q^{*} ∥ q_{0})$ . If $q_{0}$ is uniform, $D (q^{*} ∥ q_{0}) = \ln n - H (q^{*}) \leq \ln n$ .

5.1F1F5step 2.1step 2.2step 4.1algebra

The sequence $F (q_{t})$ is nonincreasing by step 2.2 and bounded below by $L_{β}^{*}$ . Moreover, $F (q_{t}) - F (q_{t + 1}) \geq D (q_{t + 1} ∥ q_{t})$ , so this successive KL divergence tends to zero. Step 4.1 gives $L_{t} \to L_{β}^{*}$ ; the first identity in step 2.2 then gives $F (q_{t}) \to L_{β}^{*}$ . The simplex is compact, and $F$ , each $s_{j}$ , and $γ$ are continuous there because every $Z_{i} (q) \geq \min_{j} e^{- β d_{i j}} > 0$ . Every cluster point of $q_{t}$ is therefore a minimizer of $F$ .

6.1F1step 5.1step 1.2algebra∎

At any minimizer $q$ of differentiable $F (q) = - \sum_{i} p_{i} \ln Z_{i} (q)$ , the coordinate derivative is $- s_{j} (q)$ . Moving mass between a positive coordinate and any other coordinate shows $s_{j} (q) = 1$ on the support and $s_{j} (q) \leq 1$ off the support; the active value equals one because $\sum_{j} q_{j} s_{j} (q) = 1$ . Hence $γ (q) = 1$ at every minimizer. Compactness and continuity from step 5.1 imply $γ_{t} \to 1$ : otherwise a subsequence bounded away from one would have a cluster point with the same property. By step 1.2, the enclosure upper endpoints satisfy $u_{t} \leq \ln γ_{t} + 1 / (t + 1)$ , so $u_{t} \to 0$ and every positive tolerance is eventually met. The argument permits zero coordinates in $q^{*}$ , so boundary minimizers are included.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Stationary-ergodic bounded-distortion rate-distortion theorem

Statement

Assume AC. Let $(X_{t})_{t \in Z}$ be a stationary ergodic finite-alphabet source, let $\hat{X}$ be finite nonempty, and let $d : X \times \hat{X} \to [0, d_{\max}]$ be bounded. With the positive-slack operational definitions of Fixed-length operational rate-distortion functions and the stationary quantities of Stationary finite-block information rate-distortion function, for every $D \geq D_{\min}$ ,

R_{o p}^{a v g} (D) = R_{o p}^{s l a c k} (D) = R_{b l o c k} (D) = R_{e r g} (D) .

All four quantities are $+ \infty$ for $0 \leq D < D_{\min}$ . At $D = D_{\min}$ , no assertion is made for the stricter exact-threshold requirement $P (d_{n} > D) \to 0$ .

Facts & Assumptions

Given: AC; a stationary ergodic finite-alphabet source; finite reproduction alphabet; bounded finite nonnegative distortion; and a distortion budget $D \geq 0$ .

[A1]

The Axiom of Choice: AC is required by the random-cut product construction and standard-Borel information suppliers.

[F1]

Fixed-length operational rate-distortion functions: the two operational rates use deterministic fixed-length codes, normalized log codebook size, expected distortion, and every positive slack in the excess-distortion condition.

[F2]

Stationary finite-block information rate-distortion function: $R_{n} (D)$ , $R_{b l o c k} (D)$ , $R_{e r g} (D)$ , and $D_{\min}$ have the stated finite-block and stationary-process meanings.

[F3]

Stationary block rate-distortion limit and endpoint continuity: $R_{n} (D) \to R_{b l o c k} (D)$ , which is right-continuous at $D_{\min}$ .

[F4]

Random-cut stationary ergodic block-channel approximation: every bit rate strictly above $R_{b l o c k} (D)$ is achieved by a jointly stationary ergodic pair with mean distortion at most $D$ and limsup bit mutual-information rate strictly below that target.

[F5]

Ergodic Shannon–McMillan–Breiman theorem: for a stationary ergodic finite-alphabet process, normalized block self-information converges almost surely to its entropy rate.

[F6]

Birkhoff pointwise ergodic theorem: time averages of an integrable function converge almost surely to a finite invariant function. In the bounded ergodic systems here, the local rational-level-set argument below identifies that limit with the mean.

[F7]

Data processing for a finite Markov chain, with equality condition and Finite entropy and mutual-information chain rules: finite mutual information obeys data processing, and conditional entropy obeys the chain rule.

[F8]

Entropy-rate limit for a stationary finite-alphabet source: for each stationary finite-alphabet process, normalized block entropies converge to its entropy rate.

[F9]

Finite mutual information and Finite entropy and mutual-information chain rules: finite-block mutual information is the finite KL sum and, by the chain rule, equals the sum of the source and reproduction entropies minus the joint entropy. These rates and entropies are in bits; the nats identity from the suppliers is divided by $\ln 2$ .

Proof

Given: The hypotheses and suppliers [A1], [F1]–[F9].

1.1F1F2F3F6givenalgebra

For any source word $x_{0}^{n - 1}$ , every reconstruction word satisfies $d_{n} (x_{0}^{n - 1}, {\hat{x}}_{0}^{n - 1}) \geq \frac{1}{n} \sum_{i = 0}^{n - 1} \min_{\hat{x}} d (x_{i}, \hat{x}) .$ The right side has expectation $D_{\min}$ by stationarity, so every code has expected distortion at least $D_{\min}$ . If $D < D_{\min}$ , choose $ϵ > 0$ with $D + ϵ < D_{\min}$ and put $g (X) = \min_{\hat{x}} d (X, \hat{x})$ . Birkhoff [F6] gives almost-sure convergence of the averages of this bounded function to a finite invariant function $g^{*}$ . For every rational $a$ , the limsup orbit set ${lim sup}_{n \to \infty} T^{- n} {g^{*} > a}$ is strictly invariant and differs from ${g^{*} > a}$ by a null set. Ergodicity makes each such level set have probability zero or one, so $g^{*}$ is constant almost surely. Dominated convergence and stationarity identify the constant as $E g = D_{\min}$ . Hence the pointwise-minimum block average converges almost surely to $D_{\min}$ , and the probability that any code's distortion exceeds $D + ϵ$ tends to one. Both operational criteria are therefore infeasible below $D_{\min}$ . By [F2], no stationary coupling with mean distortion below $D_{\min}$ exists either, so $R_{e r g} (D) = + \infty$ ; [F3] gives $R_{b l o c k} (D) = + \infty$ .

1.2F1F2F7givenalgebra

Let a deterministic length- $n$ code have $M_{n}$ messages and reconstruction ${\hat{X}}^{n}$ . Since $X^{n} \to f_{n} (X^{n}) \to {\hat{X}}^{n}$ is a Markov chain, [F7] gives $I (X^{n}; {\hat{X}}^{n}) \leq H (f_{n} (X^{n})) \leq \log_{2} M_{n}$ . Its induced joint law is feasible in the definition of $R_{n} (D_{n})$ , where $D_{n} = E d_{n} (X^{n}, {\hat{X}}^{n})$ , so $R_{n} (D_{n}) \leq n^{- 1} \log_{2} M_{n}$ .

1.3F2F3given

For every jointly stationary ergodic pair feasible at $D$ , the finite-block law is feasible in $R_{n} (D)$ , so $R_{n} (D) \leq n^{- 1} I_{2} (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1})$ . Taking limits and then the infimum over such pairs gives $R_{b l o c k} (D) \leq R_{e r g} (D)$ .

2.1F1F2F3step 1.2givenalgebra

For expected-distortion codes with $lim sup D_{n} \leq D$ , eventually $D_{n} \leq D + ϵ$ , giving $R_{n} (D + ϵ) \leq n^{- 1} \log_{2} M_{n}$ . For a positive-slack excess code, boundedness gives $D_{n} \leq D + ϵ + d_{\max} P (d_{n} > D + ϵ)$ , so eventually $D_{n} \leq D + 2 ϵ$ ; then $R_{n} (D + 2 ϵ) \leq n^{- 1} \log_{2} M_{n}$ . Taking limits and using [F3], followed by right-continuity as $ϵ ↓ 0$ , proves $R_{b l o c k} (D) \leq R_{o p}^{a v g} (D)$ and $R_{b l o c k} (D) \leq R_{o p}^{s l a c k} (D)$ .

2.2A1F2F4step 1.3givenalgebra

Conversely, for any bit rate $r > R_{b l o c k} (D)$ , [F4] supplies a jointly stationary ergodic pair with mean distortion at most $D$ and limsup bit mutual-information rate less than $r$ . Thus $R_{e r g} (D) \leq r$ ; letting $r ↓ R_{b l o c k} (D)$ proves $R_{e r g} (D) = R_{b l o c k} (D)$ .

3.1F2F5F8F9step 2.2givenalgebra

Fix a jointly stationary ergodic pair $(X, \hat{X})$ supplied by step 2.2. By [F8], each of the source, reproduction, and joint-pair normalized block entropies has a limit; [F9] therefore gives convergence of $n^{- 1} I_{2} (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1})$ to a finite bit rate $\overset{ˉ}{I} \leq lim sup n^{- 1} I_{2} (X_{0}^{n - 1}; {\hat{X}}_{0}^{n - 1}) < r$ . By [F5] applied to those three stationary ergodic processes, their normalized negative log probabilities in bits converge almost surely to their entropy rates. Subtracting the three limits shows that the information density $i_{n} (x^{n}; {\hat{x}}^{n}) : = \log_{2} \frac{P_{{\hat{X}}^{n} ∣ X^{n}} ({\hat{x}}^{n} ∣ x^{n})}{P_{{\hat{X}}^{n}} ({\hat{x}}^{n})}$ divided by $n$ converges almost surely to $h (X) + h (\hat{X}) - h (X, \hat{X}) = \overset{ˉ}{I}$ , with each entropy rate in bits.

4.1F1F6step 1.1step 3.1givenalgebra

On the ergodic pair shift let $g = d (X_{0}, {\hat{X}}_{0})$ . By [F6], its time averages converge almost surely to a finite invariant function $g^{*}$ . Apply the rational-level-set argument from step 1.1 to this bounded function on the ergodic pair system; its limit is constant, and dominated convergence with stationarity identifies that constant as $\overset{ˉ}{d} : = E d (X_{0}, {\hat{X}}_{0}) \leq D$ . Thus $d_{n} (X^{n}, {\hat{X}}^{n}) \to \overset{ˉ}{d}$ almost surely. Fix $η > 0$ and $δ > 0$ . The event $G_{n} : = {d_{n} (X^{n}, {\hat{X}}^{n}) \leq D + η, i_{n} (X^{n}; {\hat{X}}^{n}) \leq n (\overset{ˉ}{I} + δ)}$ has probability tending to one by step 3.1 and this distortion convergence. Hence the set of source words whose conditional probability of this event is at least $1 / 2$ has source probability tending to one: its complement probability is at most twice $P (G_{n}^{c})$ .

5.1F1F2step 4.1givenalgebra

For any such source word $x^{n}$ , on its good reproduction set the likelihood ratio $P_{{\hat{X}}^{n} ∣ x^{n}} / P_{{\hat{X}}^{n}}$ is at most $2^{n (\overset{ˉ}{I} + δ)}$ . Therefore an independent reproduction word sampled from $P_{{\hat{X}}^{n}}$ lands in that set with probability at least $\frac{1}{2} 2^{- n (\overset{ˉ}{I} + δ)}$ . Draw $M_{n} = ⌈ 2^{n (\overset{ˉ}{I} + 2 δ)} ⌉$ independent reproduction words. The probability that none works for this source word is at most $(1 - q)^{M_{n}} \leq e^{- M_{n} q} \leq e^{- 2^{n δ} / 2}$ . Averaging over source words shows the expected failure probability of the random codebook tends to zero.

6.1F1step 5.1givenconstruct

Some deterministic realization of each random codebook has failure probability at most twice its ensemble mean (if the mean is zero, choose a realization with zero failure). Encode a source word by the first codeword satisfying the good conditions, and use a fixed default reproduction if none does. The decoder outputs the selected codeword, so the code is deterministic and has $M_{n}$ messages. On success its distortion is at most $D + η$ ; on failure it is at most $d_{\max}$ .

7.1F1step 6.1givenalgebra

To obtain expected distortion at most $D$ in the limit and positive-slack excess distortion, choose a decreasing sequence $η_{j} ↓ 0$ . For each $j$ , the failure probability in step 6.1 is at most $1 / j$ for all sufficiently large $n$ ; choose increasing thresholds and at each length use the largest such $j = j (n)$ available. Then $j (n) \to \infty$ , expected distortion is at most $D + η_{j (n)} + d_{\max} / j (n)$ , and for every fixed slack $ϵ > 0$ , eventually $η_{j (n)} < ϵ$ , so $P (d_{n} > D + ϵ) \leq 1 / j (n) \to 0$ . The code rate has limsup at most $\overset{ˉ}{I} + 2 δ$ .

8.1F1F2step 2.1step 2.2step 5.1step 6.1step 7.1givenalgebra∎

Given any target rate $R_{b l o c k} (D) + ϵ$ , choose $r = R_{b l o c k} (D) + ϵ / 3$ . Step 2.2 gives $\overset{ˉ}{I} < r$ , so choose $δ > 0$ with $\overset{ˉ}{I} + 2 δ < R_{b l o c k} (D) + ϵ$ . Steps 5.1, 6.1 and 7.1 give both operational criteria at rate below the target. Thus $R_{o p}^{a v g} (D) \leq R_{b l o c k} (D)$ and $R_{o p}^{s l a c k} (D) \leq R_{b l o c k} (D)$ . Together with steps 2.1 and 2.2 this proves all equalities. The excess criterion used positive slack throughout; it does not imply the unclaimed exact-threshold assertion at $D_{\min}$ .

5 · Examples, counterexamples and false statements

None yet.

Rate Distortion and Lossy Source Coding

1 · Prerequisites

2 · Summary

Source trail

3 · Logical flowchart

4 · Definitions, theorems and proofs

Mutual information for standard-Borel random elements

Definition

Remarks

Single-letter and block distortion

Definition

Finite Gaussian water-level allocation

Statement

Facts & Assumptions

Proof

General single-letter information rate-distortion function

Definition

Fixed-length operational rate-distortion functions

Definition

Attainment of finite-alphabet rate-distortion minima

Statement

Facts & Assumptions

Proof

Finite-alphabet information rate-distortion function

Definition

Stationary finite-block information rate-distortion function

Definition

Gaussian reference-kernel mutual-information lower bound

Statement

Facts & Assumptions

Proof

Convexity, monotonicity, and continuity of finite rate-distortion

Statement

Facts & Assumptions

Proof

Binary Hamming rate-distortion function

Statement

Facts & Assumptions

Proof

Finite-alphabet Blahut–Arimoto rate-distortion algorithm

Definition

Stationary block rate-distortion limit and endpoint continuity

Statement

Facts & Assumptions

Proof

Finite-alphabet memoryless rate-distortion coding theorem

Statement

Facts & Assumptions

Proof

Gaussian squared-error rate-distortion function

Statement

Facts & Assumptions

Proof

Finite-dimensional Gaussian vector squared-error rate-distortion function

Statement

Facts & Assumptions

Proof

Random-cut stationary ergodic block-channel approximation

Statement

Facts & Assumptions

Proof

Blahut–Arimoto certified gap and termination

Statement

Facts & Assumptions

Proof

Stationary-ergodic bounded-distortion rate-distortion theorem

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources