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.

Cost-Constrained, Gaussian, and Feedback Channels

1 · Prerequisites

2 · Summary

This page develops finite-DMC capacity under a nonnegative letter cost, including the boundary budget equal to the minimum letter cost. It then treats finite-dimensional additive Gaussian channels under expected average squared power, diagonalizes correlated Gaussian noise by an orthogonal change of coordinates, and proves the water-filling formula for both ordinary and causal-feedback codes. All logarithms and rates are in natural nats; the Gaussian law and its orthogonal invariance are used under AC. The random-coding arguments use threshold decoding and explicitly prune codewords that violate the per-codeword cost. A separate countable-input, finite-output, zero-cost DMC definition supports the companion example about nonattainment; it does not alter the finite-alphabet capacity theorem.

The diagram records the causal interface at a single use. The encoder receives the finite message and the history of outputs from earlier uses; the channel kernel then produces the current output. In the Gaussian case the kernel is translation by fresh independent noise, while in a finite DMC it is the row $W (\cdot ∣ X_{t})$ . The feedback arrow represents that past history, not the current output, and the proofs establish the capacity bounds without relying on the diagram.

M \arrow[r, "f_t(M,Y^{t-1})"] & X_t \arrow[r, "\text{channel kernel}"] & Y_t \\
\mathcal Y^{t-1} \arrow[ur, "\text{past-output history}"'] &&

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite-dimensional additive Gaussian channel with average power

Definition

Assume the Axiom of Choice The Axiom of Choice. Fix an integer $d \geq 1$ and a real symmetric positive-definite matrix $K \in R^{d \times d}$ . The $d$ -dimensional additive Gaussian channel with power budget $P \geq 0$ has input and output spaces $R^{d}$ and single-use law $Y = X + Z, Z \sim N_{d} (0, K), Z ⊥ X .$ At each use a fresh independent copy of $Z$ is added, so the channel is memoryless. The input cost is $c (x) = ∥ x ∥_{2}^{2}$ . A length- $n$ deterministic code with $M$ equiprobable messages meets the average block power constraint $P$ when $\frac{1}{n M} \sum_{m = 1}^{M} \sum_{t = 1}^{n} ∥ x_{t} (m) ∥_{2}^{2} \leq P .$ Rates are measured in nats per vector use. The noise law is Multivariate normal law, including singular covariance; positive definiteness of $K$ gives the Lebesgue density stated in A positive-definite multivariate normal law has its Gaussian density. The scalar case $d = 1$ is the real AWGN channel. Rates use the natural logarithm The natural logarithm as the inverse of the exponential function.

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

A low-error random code can be pruned to satisfy a strict average cost constraint

Statement

Fix a blocklength $n$ , a message count $M \geq 2$ , a codebook ensemble with exchangeable message codewords, and a decoder for each sampled codebook. Let $B_{n}$ be the random fraction of codewords whose normalized cost exceeds $Γ$ , and let ${\overset{ˉ}{ε}}_{n}$ be the ensemble codebook's average error. If $q_{n} : = E B_{n}$ and $a_{n} : = E {\overset{ˉ}{ε}}_{n}$ satisfy $q_{n} + a_{n} < 1$ , then some deterministic subcode has every retained codeword of normalized cost at most $Γ$ , average error at most $\sqrt{q_{n} + a_{n}} / (1 - \sqrt{q_{n} + a_{n}})$ , and at least $M (1 - \sqrt{q_{n} + a_{n}})$ messages.

If this construction is available for each sufficiently large $n$ , with $q_{n} + a_{n} \to 0$ , then the retained code's rate differs from $n^{- 1} \ln M_{n}$ by a quantity tending to zero.

Facts & Assumptions

Given: A random length- $n$ codebook with $M \geq 2$ exchangeable message codewords, nonnegative normalized codeword cost, and a decoder whose per-message errors define ${\overset{ˉ}{ε}}_{n}$ .

[F1]

Chebyshev-Markov inequality for the integral: for a nonnegative measurable random variable $V$ and $a > 0$ , $\Pr [V \geq a] \leq E [V] / a$ .

[F2]

The finite union bound: the probability of a union of two events is at most the sum of their probabilities.

[F3]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the natural logarithm is continuous and increasing on $(0, \infty)$ , with $\ln 1 = 0$ and $\ln (a b) = \ln a + \ln b$ for $a, b > 0$ .

[F4]

A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere: a nonnegative measurable random variable with expectation zero vanishes almost surely.

Proof

1.1F1F2F4givencasesalgebra

Put $s_{n} = \sqrt{q_{n} + a_{n}} < 1$ , including $s_{n} = 0$ when $q_{n} + a_{n} = 0$ . If $q_{n} + a_{n} = 0$ , both nonnegative variables $B_{n}$ and ${\overset{ˉ}{ε}}_{n}$ have expectation zero, so [F4] makes each zero almost surely. Their zero events intersect by [F2], giving a realization with both variables zero. If $q_{n} + a_{n} > 0$ , then $s_{n} > 0$ . By [F1], $\Pr [B_{n} > s_{n}] \leq q_{n} / s_{n}$ and $\Pr [{\overset{ˉ}{ε}}_{n} > s_{n}] \leq a_{n} / s_{n}$ . The union bound [F2] makes the probability of either failure at most $s_{n} < 1$ , so a realization exists with both quantities at most $s_{n}$ .

2.1step 1.1algebracases

Retain exactly the codewords in that realization whose normalized cost is at most $Γ$ , and let $M^{'}$ be their number. Since $B_{n} \leq s_{n}$ , $M^{'} \geq M (1 - s_{n}) > 0$ . Change the decoder only by mapping decisions for removed messages to one fixed retained message. An originally correct decision for a retained message is unchanged, so its error probability cannot increase; hence the retained average error is at most $M {\overset{ˉ}{ε}}_{n} / M^{'} \leq s_{n} / (1 - s_{n})$ . Each retained word satisfies the cost constraint by construction.

3.1F3step 1.1step 2.1givenalgebra∎

If $q_{n} + a_{n} \to 0$ along blocklengths, then $s_{n} \to 0$ and $1 - s_{n} > 0$ . Since $M (1 - s_{n}) \leq M^{'} \leq M$ , the order and product laws in [F3] give $0 \leq (\ln M - \ln M^{'}) / n \leq - \ln (1 - s_{n}) / n$ . Continuity of $\ln$ at $1$ and $\ln 1 = 0$ in [F3] yield $\ln (1 - s_{n}) \to 0$ ; hence the rate loss tends to zero. The error bound in step 2.1 also tends to zero. The conclusion is per blocklength, so no sequence of witnesses is selected in this lemma.

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

Threshold decoding bound for memoryless channels with densities

Statement

Let $P_{X}$ be an input law, let $ν$ be a sigma-finite reference measure on the output space, and let $w (y ∣ x)$ be a measurable single-use channel density satisfying $\int w (y ∣ x) d ν (y) = 1$ . Let $q (y) = \int w (y ∣ x) P_{X} (d x)$ be the induced output density and assume $q > 0$ on its probability-one support. For independent uses define $ı (x^{n}; y^{n}) : = \sum_{t = 1}^{n} \ln \frac{w (y_{t} ∣ x_{t})}{q (y_{t})}$ on the joint support. For every $n \geq 1$ , $M \geq 2$ , and $τ > 0$ , the IID random-code ensemble's expected average error is at most $\Pr ⁣ [ı (X^{n}; Y^{n}) \leq \ln (M - 1) + τ] + e^{- τ},$ where $(X^{n}, Y^{n})$ has input law $P_{X}^{\otimes n}$ followed by the product channel. Consequently, some deterministic length- $n$ code with $M$ messages and the threshold decoder has average error no greater than this bound.

Facts & Assumptions

Given: The channel density, input law, induced positive output density, product channel, and blocklength/message/threshold parameters in the Statement.

[F1]

Tonelli's theorem for nonnegative measurable functions on a sigma-finite product: nonnegative measurable functions on a sigma-finite product space can be integrated in either order.

[F2]

For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique: the finite product of the input and output reference measures has the stated rectangular sections and product integrals.

[F3]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm and The natural logarithm as the inverse of the exponential function: $\ln$ is strictly increasing on $(0, \infty)$ , obeys the product law, and is inverse to the exponential, so $e^{\ln a} = a$ for $a > 0$ .

[F4]

Chebyshev-Markov inequality for the integral: if $L \geq 0$ is measurable and $a > 0$ , then $\Pr [L \geq a] \leq E L / a$ .

[F5]

The finite union bound: the probability that one of finitely many events occurs is at most the sum of their probabilities.

[F6]

The Lebesgue integral is linear on $L^{1} (μ)$ : the integral is linear on integrable real-valued functions.

[F7]

A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere: a nonnegative measurable random variable with expectation zero vanishes almost surely.

Proof

1.1F1F3givenconstruct

Draw $M$ codewords independently from $P_{X}^{\otimes n}$ . Put $S = {y : 0 < q (y) < \infty}$ ; normalization and [F1] give $P_{Y} (S) = 1$ . For $y^{n} \in S^{n}$ define $L (x^{n}; y^{n}) = \prod_{t} w (y_{t} ∣ x_{t}) / q (y_{t})$ , with a zero factor making the product zero, and define the score $ℓ = \ln L$ with $\ln 0 = - \infty$ and $\ln (+ \infty) = + \infty$ . Set $ℓ = - \infty$ outside $S^{n}$ . These are measurable extended-real scores. Under the transmitted joint law, each channel density is positive and finite almost surely by row normalization, so $ℓ = ı$ almost surely. Declare message $m$ if it is the unique codeword whose score exceeds $\ln (M - 1) + τ$ ; otherwise output a fixed default. An error is contained in the event that the transmitted score fails the threshold or that some independent competing word passes it.

1.2F1F2givenalgebra

The first event has probability exactly the miss probability in the Statement. For one competing word ${\overset{ˉ}{X}}^{n}$ independent of $Y^{n}$ , the latter has density $q^{\otimes n}$ under the ensemble. Define $L = 0$ outside $S^{n}$ . By [F1, F2] and normalization of the product channel rows, $E L = \int P_{X}^{\otimes n} (d {\overset{ˉ}{x}}^{n}) \int_{S^{n}} w^{\otimes n} (y^{n} ∣ {\overset{ˉ}{x}}^{n}) d ν^{\otimes n} (y^{n}) \leq 1.$ Thus the likelihood ratio is well-defined even for a competitor with zero channel density.

2.1F3F4F5step 1.1step 1.2givenalgebra

If a competitor passes, [F3] makes $L > (M - 1) e^{τ}$ , hence the event is contained in ${L \geq (M - 1) e^{τ}}$ . Markov's integral inequality [F4] bounds this probability by $e^{- τ} / (M - 1)$ . The finite union bound [F5] over the $M - 1$ competitors contributes at most $e^{- τ}$ . Combining this with the miss event in step 1.1 proves the asserted bound on ensemble expected average error.

3.1F6F7step 1.1step 2.1givenchoose∎

Let $E$ be the random codebook's average error and set $b = E E$ ; then $0 \leq E \leq 1$ , so both $E$ and the constant $b$ are integrable. If every sampled codebook had $E > b$ , the nonnegative variable $E - b$ would be positive everywhere, while linearity [F6] and $P (Ω) = 1$ give $E (E - b) = 0$ . By [F7], $E - b = 0$ almost surely, a contradiction. Hence some codebook has error at most $b$ , which is bounded by the result of steps 1.1 and 2.1.

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

Finite-simplex entropy is continuous and concave

Statement

For a finite nonempty alphabet of size $m$ , let $H (p) : = - \sum_{i = 1}^{m} p_{i} \ln p_{i}, 0 \ln 0 : = 0,$ on the probability simplex $Δ_{m} = {p \in [0, 1]^{m} : \sum_{i} p_{i} = 1}$ . Then $H$ is continuous and concave on $Δ_{m}$ , with $0 \leq H (p) \leq \ln m$ .

Facts & Assumptions

Given: An integer $m \geq 1$ and the finite probability simplex $Δ_{m}$ .

[F1]

The natural logarithm as the inverse of the exponential function: $\ln$ is the natural logarithm on $(0, \infty)$ .

[F2]

The logarithm grows more slowly than every positive real power: $\ln s / s \to 0$ as $s \to + \infty$ .

[F3]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : for $t > 0$ , $(\ln t)^{'} = 1 / t$ , so the second derivative of $- t \ln t$ is $- 1 / t$ .

[F4]

A twice-differentiable function on an open interval is convex if and only if its second derivative is nonnegative: a twice-differentiable function with nonpositive second derivative on an interval is concave there, by applying the nonnegative-second-derivative criterion to its negative.

Proof

1.1F1F2givenalgebra

Define $h (t) = - t \ln t$ for $0 < t \leq 1$ and $h (0) = 0$ . With $s = 1 / t$ , $∣ t \ln t ∣ = \ln (s) / s \to 0$ as $t ↓ 0$ by [F1] and [F2]; hence $h$ is continuous on $[0, 1]$ .

2.1F3F4step 1.1algebra

On $(0, 1)$ , [F3] gives $h^{''} (t) = - 1 / t < 0$ , so [F4] makes $h$ concave there. For $u, v \in [0, 1]$ and $0 < ϵ < 1$ , replace each endpoint by $u_{ϵ} = (1 - ϵ) u + ϵ / 2$ and $v_{ϵ} = (1 - ϵ) v + ϵ / 2$ . Concavity on $(0, 1)$ applies to these interior points; taking $ϵ ↓ 0$ and using step 1.1 gives the concavity inequality on the closed interval.

3.1step 1.1step 2.1givenalgebra

For $p, q \in Δ_{m}$ and $0 \leq θ \leq 1$ , apply the concavity inequality for $h$ to each coordinate $θ p_{i} + (1 - θ) q_{i}$ . Summing the $m$ inequalities gives $H (θ p + (1 - θ) q) \geq θ H (p) + (1 - θ) H (q)$ . Continuity of $H$ follows from continuity of the finite sum of the coordinate functions $h$ .

4.1F1step 3.1givenalgebracases∎

Each summand $- p_{i} \ln p_{i}$ is nonnegative because $0 \leq p_{i} \leq 1$ , so $H (p) \geq 0$ . The average of the $m!$ coordinate permutations of $p$ is the uniform vector $u = (1 / m, \dots, 1 / m)$ , and each permutation has entropy $H (p)$ . Concavity from step 3.1, iterated over this finite average, gives $H (u) \geq H (p)$ . Since $H (u) = \ln m$ , the claimed upper bound follows, including $m = 1$ .

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

A Gaussian maximizes scalar differential entropy at fixed variance

Statement

Assume AC. Let $V$ have a Lebesgue density $p$ with $\int p (x) ∣ \ln p (x) ∣ d x < \infty$ , finite mean $μ$ , and positive finite variance $v = E [(V - μ)^{2}]$ . Define $h (V) : = - \int p (x) \ln p (x) d x$ . Then $h (V) \leq \frac{1}{2} \ln (2 π e v),$ with equality exactly when $V \sim N (μ, v)$ .

Facts & Assumptions

Given: AC and a real random variable with a density whose entropy integrand is absolutely integrable, finite mean, and positive finite variance.

[A1]

The Axiom of Choice: AC is required by the stated measure-theoretic KL convention and the Gaussian-law definitions.

[F1]

Kullback–Leibler divergence: for $P ≪ Q$ , $D (P ∥ Q) = \int \ln (d P / d Q) d P$ .

[F2]

Kullback–Leibler divergence is nonnegative: for probability measures, $D (P ∥ Q) \geq 0$ , with equality exactly when $P = Q$ .

[F3]

Standard normal and normal laws and A positive-definite multivariate normal law has its Gaussian density: for $v > 0$ , $N (μ, v)$ has density $(2 π v)^{- 1 / 2} \exp (- (x - μ)^{2} / (2 v))$ .

[F4]

Moments, variance, and covariance on a probability space: $E [(V - μ)^{2}] = v$ .

[F5]

The natural logarithm as the inverse of the exponential function: $\ln$ denotes the natural logarithm.

Proof

1.1A1F1F3F4F5given

Let $q$ be the positive density in [F3]. Since $q (x) > 0$ for every $x$ , the law with density $p$ is absolutely continuous with respect to the Gaussian law. Its KL divergence is well-defined by [F1]. The absolute entropy-integrability hypothesis and finite second moment make each term in the following expansion integrable.

2.1A1F1F2F3F4F5step 1.1algebra∎

Expanding $\ln (p / q)$ and integrating gives $D (P_{V} ∥ N (μ, v)) = - h (V) + \frac{1}{2} \ln (2 π v) + \frac{E [(V - μ)^{2}]}{2 v} = - h (V) + \frac{1}{2} \ln (2 π e v)$ . By [F2] this is nonnegative, proving the bound; equality holds exactly when the two laws coincide, again by [F2].

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

Jensen's inequality for an integrable cost random variable

Statement

Let $a \in R$ , let $f : [a, \infty) \to R$ be finite and concave, and let $U$ be an integrable real random variable with $U \geq a$ almost surely and $f (U)$ integrable. Then $E f (U) \leq f (E U)$ .

Facts & Assumptions

Given: A real number $a$ , a finite concave function $f$ on $[a, \infty)$ , and an integrable random variable $U \geq a$ for which $f (U)$ is integrable.

[A1]

The domain, concavity, integrability, and lower-bound hypotheses in the Statement.

[F1]

Dedekind completeness: the least-upper-bound property: every nonempty subset of $R$ bounded above has a real supremum.

[F2]

A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere: on any measure space, a nonnegative measurable function has integral zero exactly when it is zero almost everywhere.

Proof

1.1A1F2givenalgebracases

Put $m = E U \geq a$ . If $m = a$ , let $V = (U - a)^{+}$ , a nonnegative measurable variable equal to $U - a$ almost surely by [A1]. Thus $E V = E U - a = 0$ . Applying [F2] with the probability measure gives $V = 0$ almost surely; combined with $U \geq a$ almost surely this implies $U = a$ almost surely. Consequently $E f (U) = f (a) = f (m)$ .

1.2A1F1givenalgebra

Suppose $m > a$ . For $y > m$ define $r (y) = (f (y) - f (m)) / (y - m)$ . Concavity applied to $a < m < y$ gives $r (y) \leq (f (m) - f (a)) / (m - a)$ , and the right-slope set is nonempty (take $y = m + 1$ ) and bounded above; [F1] supplies its finite supremum $s$ . For each $x$ with $a \leq x < m$ and each $y > m$ , concavity at $x < m < y$ gives $(f (m) - f (x)) / (m - x) \geq r (y)$ ; taking the supremum over $y$ yields $(f (m) - f (x)) / (m - x) \geq s$ . Therefore every $u \geq a$ satisfies $f (u) \leq f (m) + s (u - m)$ .

2.1A1step 1.1step 1.2algebracases∎

The affine upper bound in step 1.2 is integrable because $U$ is integrable. Taking expectations gives $E f (U) \leq f (m) + s (E U - m) = f (m)$ . Together with step 1.1 this proves the claim.

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

A normal variable has finite fourth moment

Statement

Assume AC and let $G \sim N (0, σ^{2})$ for $σ \geq 0$ . Then $E [G^{2}] = σ^{2}$ and $E [G^{4}] = 3 σ^{4}$ ; in particular the fourth moment is finite. For independent centered normal coordinates $G_{j} \sim N (0, σ_{j}^{2})$ , every finite linear combination of the variables $G_{j}^{2}$ has finite second moment.

Facts & Assumptions

Given: AC and a scalar centered normal variable with variance $σ^{2} \geq 0$ .

[A1]

The Axiom of Choice and Standard normal and normal laws: the standard normal law is defined under AC and has density $ϕ (x) = (2 π)^{- 1 / 2} e^{- x^{2} / 2}$ .

[F1]

The Gaussian integral $\int_{- \infty}^{\infty} e^{- x^{2}} d x = \sqrt{π}$ and Change of variable in an improper integral: $\int_{R} e^{- x^{2} / 2} d x = \sqrt{2 π}$ .

[F2]

If $u, v$ are differentiable on $[a, b]$ with $u^{'}, v^{'}$ integrable, then $\int_{a}^{b} u v^{'} = u (b) v (b) - u (a) v (a) - \int_{a}^{b} u^{'} v$ : on finite intervals, $\int u v^{'} = u v ∣_{a}^{b} - \int u^{'} v$ under its stated integrability hypotheses.

[F3]

The exponential dominates every fixed nonnegative integer power at $+ \infty$ : a fixed polynomial times $e^{- x^{2} / 2}$ tends to zero as $∣ x ∣ \to \infty$ and is integrable after comparison with a weaker Gaussian tail.

[F4]

The exponential function is smooth and $(\exp)^{'} = \exp$ gives $\exp^{'} = \exp$ ; The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ gives $(e^{u (x)})^{'} = e^{u (x)} u^{'} (x)$ for differentiable $u$ on an open interval. The product and scalar rules in Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ give $(x^{2})^{'} = 2 x$ , so $u (x) = - x^{2} / 2$ has derivative $- x$ .

[F5]

Expectations factor over finite products of independent random variables: for independent variables, integrable Borel functions of the individual variables have integrable product and factorized product expectation.

Proof

1.1F1F2F3given

Let $I_{k} : = \int_{R} x^{2 k} e^{- x^{2} / 2} d x$ for $k = 0, 1, 2$ . These integrals are finite: outside a bounded interval, $∣ x ∣^{2 k} e^{- x^{2} / 4}$ is bounded by [F3], while $e^{- x^{2} / 4}$ is integrable by [F1] after scaling. Thus integration by parts on $[- R, R]$ is valid, and its polynomial-exponential boundary terms vanish as $R \to \infty$ by [F3].

2.1A1F1F2F3F4step 1.1algebra

Since $u (x) = - x^{2} / 2$ is differentiable on $R$ and the exponential is differentiable at every $u (x)$ , the chain rule in [F4] gives $(e^{- x^{2} / 2})^{'} = - x e^{- x^{2} / 2}$ . All these functions and derivatives are continuous on $[- R, R]$ , so the hypotheses of [F2] hold. Integration by parts gives $\int_{- R}^{R} x^{2} e^{- x^{2} / 2} d x = [- x e^{- x^{2} / 2}]_{- R}^{R} + \int_{- R}^{R} e^{- x^{2} / 2} d x$ and $\int_{- R}^{R} x^{4} e^{- x^{2} / 2} d x = [- x^{3} e^{- x^{2} / 2}]_{- R}^{R} + 3 \int_{- R}^{R} x^{2} e^{- x^{2} / 2} d x$ . Letting $R \to \infty$ , [F3] makes the boundary terms vanish and [F1] gives $I_{1} = I_{0} = \sqrt{2 π}$ and $I_{2} = 3 I_{1} = 3 \sqrt{2 π}$ ; integration against the standard-normal density gives $E [G_{0}^{2}] = 1$ and $E [G_{0}^{4}] = 3$ .

3.1A1F5step 2.1givencasesalgebra∎

If $σ > 0$ , the definition of $N (0, σ^{2})$ is the law of $σ G_{0}$ , so $E [G^{2}] = σ^{2} E [G_{0}^{2}] = σ^{2}$ and $E [G^{4}] = σ^{4} E [G_{0}^{4}] = 3 σ^{4}$ . If $σ = 0$ , $G = 0$ almost surely and both formulas hold. For distinct indices $i \neq j$ , the squared coordinates are integrable by these second-moment formulas, so [F5] gives $E [G_{i}^{2} G_{j}^{2}] = σ_{i}^{2} σ_{j}^{2} < \infty$ . For $i = j$ , the fourth-moment formula instead gives $E [G_{i}^{4}] = 3 σ_{i}^{4} < \infty$ . Thus every term in the square of a finite linear combination of the $G_{j}^{2}$ is integrable, proving that combination has finite second moment; the empty combination is zero.

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

Water-filling maximizes the finite parallel Gaussian allocation objective

Statement

Let $L \geq 1$ , let $λ_{1}, \dots, λ_{L} > 0$ , and let $P \geq 0$ . For allocations $p_{j} \geq 0$ with $\sum_{j} p_{j} \leq P$ , set $F (p_{1}, \dots, p_{L}) : = \frac{1}{2} \sum_{j = 1}^{L} \ln (1 + \frac{p_{j}}{λ_{j}}) .$ If $P = 0$ , the maximum is $0$ at $p_{j} = 0$ . If $P > 0$ , there is a unique $T > \min_{j} λ_{j}$ solving $\sum_{j = 1}^{L} (T - λ_{j})^{+} = P,$ and the maximum is attained at $p_{j}^{*} = (T - λ_{j})^{+}$ . Its value is $C_{L} (P) = \frac{1}{2} \sum_{j = 1}^{L} \ln^{+} (\frac{T}{λ_{j}}),$ where $u^{+} = \max (u, 0)$ and $\ln^{+} (u) = \max (\ln u, 0)$ . The value function $C_{L}$ is nondecreasing and concave on $[0, \infty)$ .

Facts & Assumptions

Given: A finite list of positive noise variances $λ_{j}$ and total power budget $P \geq 0$ .

[F1]

The natural logarithm as the inverse of the exponential function and The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\ln^{'} (x) = 1 / x$ for $x > 0$ .

[F2]

Intermediate value theorem, by bisection with a canonical left-half rule: a continuous function on $[a, b]$ takes every value between $f (a)$ and $f (b)$ : a continuous function whose endpoint values straddle a target takes that value.

[F3]

A twice-differentiable function on an open interval is convex if and only if its second derivative is nonnegative: a twice-differentiable function on an open interval with nonnegative second derivative is convex. Applying this to $- f$ gives concavity when $f^{''} \leq 0$ . The tangent bound will be derived directly from concavity below.

[F4]

Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ gives the sum, scalar, product and quotient derivative rules; The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ supplies the derivative of a composition at points where both derivatives are defined.

Proof

1.1F2givencasesalgebra

For $P = 0$ , feasibility forces every $p_{j} = 0$ , so the maximum is $0$ . Suppose $P > 0$ , put $a = \min_{j} λ_{j}$ , and define $g (T) = \sum_{j} (T - λ_{j})^{+}$ . For real $u, v$ , considering whether each is nonnegative gives $∣ u^{+} - v^{+} ∣ \leq ∣ u - v ∣$ ; hence $∣ g (T) - g (S) ∣ \leq L ∣ T - S ∣$ , proving continuity, including at the breakpoints. We have $g (a) = 0$ and $g (a + P) \geq P$ because a branch with $λ_{j} = a$ contributes $P$ . By [F2] on $[a, a + P]$ , a solution exists; it lies above $a$ since $P > 0$ . If $a < S < T$ , that same branch grows by $T - S > 0$ and all other terms are nondecreasing, so $g (T) > g (S)$ and the solution is unique.

2.1F1F3F4step 1.1givenalgebra

Put $p_{j}^{*} = (T - λ_{j})^{+}$ . Then $\sum_{j} p_{j}^{*} = P$ . Extend $f_{j} (p) = \frac{1}{2} \ln (1 + p / λ_{j})$ to the open interval $p > - λ_{j}$ . Its affine inner function has positive value and derivative $1 / λ_{j}$ , so [F1] and the chain rule in [F4] give $f_{j}^{'} (p) = 1 / (2 (λ_{j} + p))$ ; the quotient rule gives $f_{j}^{''} (p) = - 1 / (2 (λ_{j} + p)^{2}) < 0$ . Thus [F3] applied to $- f_{j}$ proves concavity on this open interval. For any $a, b$ in it and $0 < t < 1$ , concavity gives $f_{j} (a + t (b - a)) \geq (1 - t) f_{j} (a) + t f_{j} (b)$ . Subtracting $f_{j} (a)$ , dividing by $t$ , and taking $t ↓ 0$ yields $f_{j} (b) - f_{j} (a) \leq f_{j}^{'} (a) (b - a)$ . This proves the tangent bound also when $a = 0$ , which is an interior point of the extended domain. On an active branch $f_{j}^{'} (p_{j}^{*}) = 1 / (2 T)$ ; on an inactive branch $p_{j}^{*} = 0$ and $f_{j}^{'} (0) = 1 / (2 λ_{j}) \leq 1 / (2 T)$ . Summing the tangent bounds gives, for every feasible $p$ , $\sum_{j} [f_{j} (p_{j}) - f_{j} (p_{j}^{*})] \leq (2 T)^{- 1} (\sum_{j} p_{j} - P) \leq 0$ . Thus $p^{*}$ is globally optimal.

3.1step 1.1step 2.1givenalgebra∎

Substitution of $p_{j}^{*}$ yields $F (p^{*}) = \frac{1}{2} \sum_{j} \ln^{+} (T / λ_{j})$ . The feasible sets are nested as $P$ grows, so $C_{L}$ is nondecreasing. If $P_{0}, P_{1} \geq 0$ and $p^{(0)}, p^{(1)}$ are maximizing allocations, then $θ p^{(0)} + (1 - θ) p^{(1)}$ is feasible at $θ P_{0} + (1 - θ) P_{1}$ . Concavity of each $f_{j}$ gives $C_{L} (θ P_{0} + (1 - θ) P_{1}) \geq θ C_{L} (P_{0}) + (1 - θ) C_{L} (P_{1})$ , including $P_{i} = 0$ by step 1.1.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Zero-cost information capacity of a countable-input finite-output DMC

Definition

A countable-input finite-output DMC has input alphabet $N_{> 0} = {1, 2, \dots}$ , a finite nonempty output alphabet $Y$ , and row probabilities $W (y ∣ x) \geq 0$ with $\sum_{y \in Y} W (y ∣ x) = 1$ for each $x$ . At blocklength $n$ , its channel law is $W^{n} (y^{n} ∣ x^{n}) = \prod_{t = 1}^{n} W (y_{t} ∣ x_{t})$ . An input law is a sequence $(p_{x})_{x \geq 1}$ with $p_{x} \geq 0$ and $\sum_{x} p_{x} = 1$ . Give every input symbol cost $c (x) = 0$ and budget $Γ = 0$ . Its output law is $q (y) = \sum_{x} p_{x} W (y ∣ x)$ , and define $H (q) = - \sum_{y \in Y} q (y) \ln q (y), H (Y ∣ X) = \sum_{x \geq 1} p_{x} [- \sum_{y \in Y} W (y ∣ x) \ln W (y ∣ x)],$ where finite entropy is as in Finite distributions, entropy, divergence, and stochastic matrices, $0 \ln 0 = 0$ , and logarithms are natural The natural logarithm as the inverse of the exponential function. The conditional-entropy series converges because each summand entropy lies between $0$ and $\ln ∣ Y ∣$ by Finite-simplex entropy is continuous and concave. Define $I (p; W) : = H (q) - H (Y ∣ X)$ and the zero-cost information capacity $C_{I} (0) : = \sup_{p} I (p; W)$ over all countable input laws. This definition alone makes no assertion that the supremum is attained or equals an operational coding capacity.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Causal feedback codes for a finite-dimensional Gaussian channel

Definition

Assume AC The Axiom of Choice and use the channel in Finite-dimensional additive Gaussian channel with average power with dimension $d$ and budget $P$ . A length- $n$ code with $M \geq 1$ equiprobable messages is a tuple of Borel encoders $f_{t} : [M] \times (R^{d})^{t - 1} \to R^{d}, 1 \leq t \leq n,$ and a Borel decoder $g : (R^{d})^{n} \to [M]$ . At time $t$ the input is $X_{t} = f_{t} (M, Y^{t - 1})$ and the output is $Y_{t} = X_{t} + Z_{t}$ , with the fresh independent Gaussian noise of the channel definition. The code meets the expected average-power constraint when $\frac{1}{n} E [\sum_{t = 1}^{n} ∥ X_{t} ∥_{2}^{2}] \leq P .$ Its average error is $\Pr [g (Y^{n}) \neq M]$ and its rate is $n^{- 1} \ln M$ nats per vector use. If every $f_{t}$ is independent of $Y^{t - 1}$ , the code does not use feedback. Define $C_{f b} (P)$ as the supremum of rates $R$ for which feasible feedback codes for all sufficiently large $n$ have average error tending to zero and $lim inf n^{- 1} \ln M_{n} \geq R$ . Define $C_{n f} (P)$ by restricting to codes that do not use feedback. Both capacities use natural-log nats per vector use The natural logarithm as the inverse of the exponential function.

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

Orthogonal coordinates diagonalize a finite-dimensional Gaussian noise law

Statement

Assume AC. Let $K \in R^{d \times d}$ be symmetric positive definite and let $Z \sim N_{d} (0, K)$ be the additive noise in Finite-dimensional additive Gaussian channel with average power. Then there are an orthogonal matrix $U$ and positive numbers $λ_{1}, \dots, λ_{d}$ such that $K = U^{T} diag (λ_{1}, \dots, λ_{d}) U$ and the coordinates of $U Z$ are independent with laws $N (0, λ_{j})$ . For every input $X$ , $∥ U X ∥_{2} = ∥ X ∥_{2}$ and $U (X + Z) = U X + U Z$ , so this change of coordinates preserves the power constraint and the channel law.

Facts & Assumptions

Given: AC, a positive-definite covariance matrix $K$ , and a centered Gaussian vector $Z$ with covariance $K$ .

[A1]

The Axiom of Choice: AC is assumed by the multivariate-normal construction and by the orthogonal-normal invariance supplier.

[F1]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric endomorphism has an orthonormal eigenbasis; positive definiteness makes each eigenvalue positive.

[F2]

A non-negative operator has a unique non-negative square root: a positive-semidefinite symmetric matrix has a unique positive-semidefinite square root.

[F3]

Multivariate normal law, including singular covariance and Standard normal and normal laws: $N_{d} (0, K)$ is realized as $K^{1 / 2} G$ with independent standard-normal coordinates in $G$ .

[F4]

Orthogonal transformations preserve the standard normal product law: under AC, if $G \sim N_{d} (0, I_{d})$ has independent standard-normal coordinates and $U^{T} U = I_{d}$ , then $U G$ again has independent standard-normal coordinates.

Proof

1.1F1F2givenchoose

By [F1], choose an orthogonal eigenbasis $U$ for $K$ , so $K = U^{T} Λ U$ with $Λ = diag (λ_{1}, \dots, λ_{d})$ and $λ_{j} > 0$ . The positive square root is $K^{1 / 2} = U^{T} Λ^{1 / 2} U$ : this matrix is positive semidefinite, squares to $K$ , and is therefore the unique square root in [F2].

2.1A1F3F4step 1.1algebra

By [F3], write $Z$ in law as $K^{1 / 2} G$ . Since $U U^{T} = I_{d}$ , $U Z$ therefore has the law of $Λ^{1 / 2} U G$ . By [A1] and [F4], the coordinates of $U G$ are independent standard normals; multiplication by $\sqrt{λ_{j}}$ gives independent $N (0, λ_{j})$ coordinates.

3.1step 1.1step 2.1algebra∎

Orthogonality gives $∥ U X ∥_{2}^{2} = X^{T} U^{T} U X = ∥ X ∥_{2}^{2}$ , and linearity gives $U (X + Z) = U X + U Z$ . Thus the transformed channel has parallel independent Gaussian noise and exactly the same input power and code/error correspondence.

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

Finite-input vector Gaussian mutual information is bounded by water-filling

Statement

Assume AC. Let $Z = (Z_{1}, \dots, Z_{d})$ have independent coordinates $Z_{j} \sim N (0, λ_{j})$ with $λ_{j} > 0$ , and let $X$ be an independent finite-support random vector in $R^{d}$ with $E ∥ X ∥_{2}^{2} \leq P$ . Define $I (X; X + Z)$ as the relative entropy, in nats, of the joint law with respect to the product of its marginals. Then $I (X; X + Z) \leq C_{d} (P) : = \max_{p_{j} \geq 0, \sum_{j} p_{j} \leq P} \frac{1}{2} \sum_{j = 1}^{d} \ln (1 + \frac{p_{j}}{λ_{j}}) .$ The maximum is attained by the allocation in Water-filling maximizes the finite parallel Gaussian allocation objective.

Facts & Assumptions

Given: AC, independent scalar Gaussian noise coordinates of positive variances, an independent finite-support input vector, and its second-moment bound.

[A1]

The Axiom of Choice and Standard normal and normal laws: Gaussian laws are used under AC; each $N (0, λ_{j})$ is a scaled standard-normal law.

[F1]

A positive-definite multivariate normal law has its Gaussian density: every scalar Gaussian with positive variance has a positive Gaussian Lebesgue density.

[F2]

A Gaussian maximizes scalar differential entropy at fixed variance: a scalar density of finite entropy and variance $v > 0$ has $h \leq \frac{1}{2} \ln (2 π e v)$ .

[F3]

Kullback–Leibler divergence is nonnegative: relative entropy between probability measures is nonnegative.

[F4]

Water-filling maximizes the finite parallel Gaussian allocation objective: the finite allocation objective is maximized by its water-filling allocation.

[F5]

Kullback–Leibler divergence: $D (P ∥ Q) = \int \ln (d P / d Q) d P$ for $P ≪ Q$ .

[F6]

Moments, variance, and covariance on a probability space: variance is the expected squared deviation from the mean.

[F7]

Expectations factor over finite products of independent random variables: independent integrable variables have factorized product expectations.

[F8]

Tonelli's theorem for nonnegative measurable functions on a sigma-finite product: nonnegative measurable functions on a sigma-finite product space can be integrated in either order.

[F9]

The natural logarithm as the inverse of the exponential function: logarithms are natural.

[F10]

A normal variable has finite fourth moment: for $Z_{j} \sim N (0, λ_{j})$ , $E Z_{j}^{2} = λ_{j}$ .

Proof

1.1A1F1F10givenalgebra

Write $Y = X + Z$ . Its density is the finite mixture $p_{Y} (y) = \sum_{x} P_{X} (x) \prod_{j} ϕ_{λ_{j}} (y_{j} - x_{j})$ , which is positive and bounded by [F1]. Fix any support point $x_{0}$ with $P_{X} (x_{0}) > 0$ . Then $p_{Y} (y) \geq P_{X} (x_{0}) \prod_{j} ϕ_{λ_{j}} (y_{j} - x_{0 j})$ . The Gaussian upper bound and this lower bound show $∣ \ln p_{Y} (y) ∣ \leq C (1 + ∥ y ∥_{2}^{2})$ for some finite $C$ ; $Y$ has finite second moment, so $h (Y)$ is absolutely finite by [F10]. The same bounds apply to each marginal $Y_{j}$ , and each conditional density given a support point is a Gaussian translate, so all entropy integrals below are finite.

2.1F3F5F9step 1.1givenalgebra

The joint output density has finite differential entropy by step 1.1. On the support of $X$ , the joint-to-product density ratio in [F5] is $\prod_{j} ϕ_{λ_{j}} (y_{j} - x_{j}) / p_{Y} (y)$ . Expanding its logarithm and integrating gives $I (X; Y) = h (Y) - h (Y ∣ X) = h (Y) - h (Z)$ , because each conditional output density is a translate of the noise density. The KL divergence of $P_{Y}$ from the product of its marginals is finite by step 1.1 and nonnegative by [F3]; expanding it gives $h (Y) \leq \sum_{j} h (Y_{j})$ .

3.1F1F2F4F6F7F8F9F10step 1.1step 2.1givenalgebra∎

Independence [F7] and the variance definition [F6] give $Var (Y_{j}) = Var (X_{j}) + λ_{j}$ and $Var (X_{j}) \leq E X_{j}^{2}$ . By [F2], $h (Y_{j}) \leq \frac{1}{2} \ln (2 π e (Var (X_{j}) + λ_{j}))$ . Direct integration of $ϕ_{λ_{j}}$ using [F1] and [F10] gives $h (Z_{j}) = \frac{1}{2} \ln (2 π e λ_{j})$ , hence $h (Z) = \sum_{j} h (Z_{j})$ by independence. Tonelli [F8] on the integrable positive and negative parts from step 1.1 justifies the product integrals. Therefore $I (X; Y) \leq \frac{1}{2} \sum_{j} \ln (1 + Var (X_{j}) / λ_{j}) \leq \frac{1}{2} \sum_{j} \ln (1 + E X_{j}^{2} / λ_{j})$ . The powers $p_{j} = E X_{j}^{2}$ sum to at most $P$ , so [F4] proves the claim.

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

Parallel Gaussian information density obeys a finite-variance law of large numbers

Statement

Assume AC. In orthogonal coordinates let the independent channel branches be $Y_{j} = X_{j} + Z_{j}$ , where $X_{j} \sim N (0, p_{j})$ , $Z_{j} \sim N (0, λ_{j})$ , all coordinates are independent, $p_{j} \geq 0$ , and $λ_{j} > 0$ . Across channel uses take independent copies. Define the information density on the joint support by $ı (X; Y) = \ln \frac{f_{Y ∣ X} (Y ∣ X)}{f_{Y} (Y)} .$ Then $\frac{1}{n} \sum_{t = 1}^{n} ı (X_{t}; Y_{t}) ⟶ \frac{1}{2} \sum_{j = 1}^{d} \ln (1 + \frac{p_{j}}{λ_{j}})$ in probability.

Facts & Assumptions

Given: The Gaussian branch laws and their independence as stated.

[A1]

The Axiom of Choice: AC is inherited from Multivariate normal law, including singular covariance.

[A2]

Finite-dimensional additive Gaussian channel with average power: each use adds an independent fresh Gaussian noise vector.

[F1]

Orthogonal coordinates diagonalize a finite-dimensional Gaussian noise law: a positive-definite Gaussian noise covariance is reduced to independent scalar normal branches by an orthogonal transformation.

[F2]

A positive-definite multivariate normal law has its Gaussian density: every positive-variance scalar Gaussian used here has its Gaussian density.

[F3]

A normal variable has finite fourth moment: if $G \sim N (0, 1)$ then $E G^{2} = 1$ and $E G^{4} = 3$ ; scaling gives the moments of each $X_{j}$ and $Z_{j}$ .

[F4]

The Gaussian integral $\int_{- \infty}^{\infty} e^{- x^{2}} d x = \sqrt{π}$ and Change of variable in an improper integral: $\int_{R} e^{- a (x - b)^{2} / 2} d x = \sqrt{2 π / a}$ for $a > 0$ .

[F5]

Independent random elements have product joint law: independent coordinates have the product density used to form the branchwise output density.

[F6]

The natural logarithm as the inverse of the exponential function: $\ln$ is the natural logarithm.

[F7]

Moments, variance, and covariance on a probability space: variance is the expected squared deviation from the mean.

[F8]

Chebyshev-Markov inequality for the integral: Markov's integral inequality applies to nonnegative squared deviations.

[F9]

Standard normal and normal laws: $N (0, λ_{j})$ is centered with variance $λ_{j}$ .

[F10]

Expectations factor over finite products of independent random variables: expectations of products of independent integrable real random variables factor.

Proof

1.1A1A2F1F2F4F5givenalgebracases

For $p_{j} > 0$ , completing the square gives $x^{2} / p_{j} + (y - x)^{2} / λ_{j} = ((p_{j} + λ_{j}) / (p_{j} λ_{j})) (x - p_{j} y / (p_{j} + λ_{j}))^{2} + y^{2} / (p_{j} + λ_{j})$ , so [F4] yields $\int_{R} ϕ_{p_{j}} (x) ϕ_{λ_{j}} (y - x) d x = (2 π (p_{j} + λ_{j}))^{- 1 / 2} e^{- y^{2} / (2 (p_{j} + λ_{j}))} = ϕ_{p_{j} + λ_{j}} (y)$ . If $p_{j} = 0$ , then $X_{j} = 0$ and $Y_{j} = Z_{j}$ has density $ϕ_{λ_{j}}$ . Independence across coordinates and uses gives product output densities by [F5].

2.1F2F3F5F6F9step 1.1givenalgebracases

For $p_{j} > 0$ , substituting $Y_{j} = X_{j} + Z_{j}$ in the log-density ratio gives $ı_{j} = \frac{1}{2} \ln (1 + p_{j} / λ_{j}) - Z_{j}^{2} / (2 λ_{j}) + (X_{j} + Z_{j})^{2} / (2 (p_{j} + λ_{j}))$ . By [F3] and [F9], the second moments are $p_{j}$ and $λ_{j}$ and the means are zero; [F5] factors the cross moment, so $E ı_{j} = \frac{1}{2} \ln (1 + p_{j} / λ_{j})$ . Its second moment is finite because $(a + b + c)^{2} \leq 3 (a^{2} + b^{2} + c^{2})$ , $(x + z)^{4} \leq 8 (x^{4} + z^{4})$ , and the Gaussian fourth moments in [F3] are finite. If $p_{j} = 0$ , the information density is identically zero, which agrees with the formula; for finitely many branches, $(\sum_{j} ı_{j})^{2} \leq d \sum_{j} ı_{j}^{2}$ , so the summed density has mean $I = \frac{1}{2} \sum_{j} \ln (1 + p_{j} / λ_{j})$ and finite variance.

3.1A2F5F7F8F10step 2.1givenalgebra∎

The pairs $(X_{t}, Y_{t})$ are IID across uses because [A2] gives fresh independent noises and [F5] gives product coordinate laws. Their information densities are therefore IID with mean $I$ and finite variance $v$ by step 2.1. For $s \neq t$ , [F10] factors the expectation of the product of their centered information densities, which is zero; expanding the squared sum gives $E [(\sum_{t = 1}^{n} ı (X_{t}; Y_{t}) - n I)^{2}] = n v$ . For every $η > 0$ , the normalized deviation event forces this square to be at least $n^{2} η^{2}$ , so [F8] bounds its probability by $v / (n η^{2}) \to 0$ .

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite DMC with a nonnegative input cost and feasible budget

Definition

Let $W (y ∣ x)$ be a finite DMC with nonempty finite input alphabet $X$ (Finite discrete memoryless channels). A letter cost is a supplied function $c : X \to [0, \infty)$ with finite real values. Define $c_{\min} : = \min_{x \in X} c (x), c_{\max} : = \max_{x \in X} c (x), \overset{ˉ}{c} (P_{X}) : = \sum_{x \in X} P_{X} (x) c (x)$ for each input probability vector $P_{X}$ (Finite probability vectors). A real number $Γ$ is a feasible cost budget when $Γ \geq c_{\min}$ . Costs and budgets are per channel use; all logarithms and rates in this pair use natural units The natural logarithm as the inverse of the exponential function.

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

Strictly feasible Gaussian inputs yield cost-feasible Gaussian codes

Statement

Assume AC. For the channel in Finite-dimensional additive Gaussian channel with average power, let the noise eigenvalues be $λ_{1}, \dots, λ_{d} > 0$ . Let $P > 0$ and choose $p_{j} \geq 0$ with $\sum_{j} p_{j} < P$ . Then every rate $0 \leq R < I (p) : = \frac{1}{2} \sum_{j = 1}^{d} \ln (1 + \frac{p_{j}}{λ_{j}})$ is achievable by deterministic no-feedback codes meeting average block power $P$ and with average error tending to zero.

Facts & Assumptions

Given: AC, the finite-dimensional Gaussian channel, positive noise eigenvalues, a strict power allocation, and a rate below its Gaussian mutual information.

[A1]

The Axiom of Choice and Finite-dimensional additive Gaussian channel with average power: the Gaussian channel uses fresh independent Gaussian noise and squared Euclidean cost under AC; rates are nats per vector use.

[A2]

Causal feedback codes for a finite-dimensional Gaussian channel: deterministic no-feedback codes are the subcase whose encoders ignore output histories, and their average block power is measured over messages.

[F1]

Orthogonal coordinates diagonalize a finite-dimensional Gaussian noise law: an orthogonal coordinate change diagonalizes the noise and preserves squared input norm and code/error correspondence.

[F2]

Parallel Gaussian information density obeys a finite-variance law of large numbers: for independent Gaussian input and noise branches and IID uses, the normalized sum of information densities converges in probability to $I (p)$ .

[F3]

Threshold decoding bound for memoryless channels with densities: the IID Gaussian code ensemble's expected average error is bounded by an information-density miss probability plus $e^{- τ}$ .

[F4]

A normal variable has finite fourth moment: $E G^{2} = 1$ and $E G^{4} = 3$ for standard normal $G$ , with scaling for any branch variance.

[F5]

Chebyshev-Markov inequality for the integral: a nonnegative measurable variable $V$ satisfies $\Pr (V \geq a) \leq E V / a$ for $a > 0$ .

[F7]

Moments, variance, and covariance on a probability space and Expectations factor over finite products of independent random variables: variances are computed from second moments, and independence factors cross moments.

[F6]

A low-error random code can be pruned to satisfy a strict average cost constraint: a random code ensemble with exchangeable message codewords, vanishing expected cost-violation fraction and vanishing expected error has feasible deterministic subcodes with vanishing rate loss.

Proof

1.1A1F1F2givenconstruct

Use [F1] to work in orthogonal coordinates, and draw each vector use independently with branch inputs $X_{j} \sim N (0, p_{j})$ , independent across branches. Put $μ = \sum_{j} p_{j} < P$ . By [F2], the normalized sum of information densities converges in probability to $I (p)$ .

2.1F2F3step 1.1givenalgebracases

If $R = 0$ , one-message codes meet the assertion. Suppose $R > 0$ , choose $δ > 0$ with $R + 2 δ < I (p)$ , and put $M_{n} = ⌈ e^{n R} ⌉$ . The threshold $\ln (M_{n} - 1) + n δ$ is eventually below $n (R + 2 δ)$ . The weak law in [F2] makes the miss probability tend to zero; [F3] then shows the ensemble expected average error $a_{n}$ tends to zero.

2.2F4F5F7step 1.1givenalgebra

For one vector use put $Q = \sum_{j} X_{j}^{2}$ . By [F4], $E X_{j}^{2} = p_{j}$ and $E X_{j}^{4} = 3 p_{j}^{2}$ ; [F7] then gives $Var (X_{j}^{2}) = 2 p_{j}^{2}$ , and independence factors the cross moments to yield $Var (Q) = 2 \sum_{j} p_{j}^{2} < \infty$ . Across $n$ uses the codeword average cost ${\overset{ˉ}{Q}}_{n}$ has mean $μ$ and variance $Var (Q) / n$ . With $Δ = P - μ > 0$ , the event ${\overset{ˉ}{Q}}_{n} > P$ is contained in ${∣ {\overset{ˉ}{Q}}_{n} - μ ∣ \geq Δ}$ , whose probability is at most $Var (Q) / (n Δ^{2})$ by [F5] applied to the squared deviation. This probability is the expected fraction $q_{n}$ of over-budget codewords, so $q_{n} \to 0$ .

3.1A2F1F6step 2.1step 2.2algebra∎

The codewords are drawn IID, hence are exchangeable, and the random code ensemble has $q_{n} + a_{n} \to 0$ by steps 2.1 and 2.2. Apply [F6] to prune every over-budget word; [A2] identifies the retained deterministic codes as feasible no-feedback codes, with average power at most $P$ , error tending to zero, and rate loss tending to zero. Orthogonal invariance in [F1] carries these codes back to the original channel.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Average-cost fixed-length codes and operational DMC capacity

Definition

Fix a finite DMC and cost model from Finite DMC with a nonnegative input cost and feasible budget, with feasible budget $Γ$ . A length- $n$ , $M$ -message code from Fixed-length codes for a finite DMC is average-cost feasible if $\frac{1}{n M} \sum_{m = 1}^{M} \sum_{t = 1}^{n} c (x_{t} (m)) \leq Γ .$ A rate $R \geq 0$ is average-error achievable under budget $Γ$ if there is a sequence of such codes, for all sufficiently large $n$ , whose average errors from Average and maximal error of a fixed-length code tend to zero and satisfy ${lim inf}_{n \to \infty} n^{- 1} \ln M_{n} \geq R$ . The operational cost-constrained capacity $C (Γ)$ is the supremum of these rates.

For an input probability vector $P_{X}$ , define its expected cost $\overset{ˉ}{c} (P_{X})$ as in Finite DMC with a nonnegative input cost and feasible budget. The cost-constrained information capacity is $C_{I} (Γ) : = \sup_{P_{X} : \overset{ˉ}{c} (P_{X}) \leq Γ} I (P_{X}; W),$ where $I (P_{X}; W)$ and the unconstrained DMC information capacity use natural-log nats as in Single-letter information capacity of a finite DMC and The natural logarithm as the inverse of the exponential function. All rates use natural-log nats (The natural logarithm as the inverse of the exponential function). This definition uses a supremum; attainment is proved separately.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Causal feedback codes for a finite cost-constrained DMC

Definition

Let $W (y ∣ x)$ be the finite DMC Finite discrete memoryless channels and $c : X \to [0, \infty)$ the finite input cost from Finite DMC with a nonnegative input cost and feasible budget, with feasible budget $Γ$ from Average-cost fixed-length codes and operational DMC capacity. For an integer $n \geq 1$ , a deterministic length- $n$ feedback code with $M \geq 1$ equiprobable messages consists of causal maps $f_{t} : [M] \times Y^{t - 1} \to X (1 \leq t \leq n)$ and a decoder $g : Y^{n} \to [M]$ . Let $U$ be a uniform random message on $[M]$ , and set $X_{t} = f_{t} (U, Y^{t - 1})$ . Given $U = m$ , the output law is the product of the row probabilities $W (y_{t} ∣ f_{t} (m, y^{t - 1}))$ . Its expected average cost is $\frac{1}{n} \sum_{t = 1}^{n} E [c (X_{t})],$ where the expectation is over $U$ and the channel outputs. It is feasible when this quantity is at most $Γ$ ; its average error is $\Pr [g (Y^{n}) \neq U]$ and its rate is $n^{- 1} \ln M$ nats per use. The feedback operational capacity $C_{f b} (Γ)$ is the supremum of rates for which feasible codes for all sufficiently large blocklengths have average error tending to zero and limiting inferior rate at least the stated rate. The no-feedback subclass consists of encoders $f_{t}$ that do not depend on $y^{t - 1}$ ; it includes every ordinary fixed-length code from Fixed-length codes for a finite DMC. Its rate uses the natural logarithm The natural logarithm as the inverse of the exponential function.

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

Constrained DMC information capacity is attained, nondecreasing, and concave

Statement

Let $W$ be a finite DMC, $c : X \to [0, \infty)$ a finite letter cost, and $Γ \geq c_{\min}$ . The feasible set ${P_{X} : \overset{ˉ}{c} (P_{X}) \leq Γ}$ is nonempty and compact, and $C_{I} (Γ)$ from Average-cost fixed-length codes and operational DMC capacity is attained with $0 \leq C_{I} (Γ) \leq \ln ∣ X ∣$ . The function $Γ \mapsto C_{I} (Γ)$ is nondecreasing and concave on $[c_{\min}, \infty)$ . If $Γ > c_{\min}$ , then for every maximizing law $P_{X}^{*}$ the laws $P_{X, ϵ} : = (1 - ϵ) P_{X}^{*} + ϵ δ_{x_{\min}}, 0 < ϵ < 1,$ have cost strictly below $Γ$ whenever $P_{X}^{*}$ has cost $Γ$ , and $I (P_{X, ϵ}; W) \to C_{I} (Γ)$ as $ϵ ↓ 0$ .

Facts & Assumptions

Given: A finite DMC $W$ , a finite cost $c$ , and a budget $Γ \geq c_{\min}$ .

[F1]

Finite DMC with a nonnegative input cost and feasible budget and Finite probability vectors: $X$ is finite and nonempty, $c_{\min}$ is attained, and $\overset{ˉ}{c} (P_{X}) = \sum_{x} P_{X} (x) c (x)$ is linear in $P_{X}$ .

[F2]

Average-cost fixed-length codes and operational DMC capacity: $C_{I} (Γ) = \sup_{\overset{ˉ}{c} (P_{X}) \leq Γ} I (P_{X}; W)$ .

[F3]

Single-letter information capacity of a finite DMC, Finite mutual information, Finite conditional entropy, and Finite entropy and mutual-information chain rules: for the induced finite joint law, $I (P_{X}; W) = H (P_{X} W) - \sum_{x} P_{X} (x) H (W (\cdot ∣ x))$ .

[F4]

Finite-simplex entropy is continuous and concave and Finite distributions, entropy, divergence, and stochastic matrices: finite entropy is continuous and concave on each probability simplex, with $0 \leq H \leq \ln m$ . finite entropy is continuous and concave on each probability simplex.

[F5]

For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent: a nonempty closed bounded subset of finite-dimensional Euclidean space is compact, and every continuous real-valued function on it attains its maximum.

[F6]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite KL divergence is nonnegative and equals zero only for identical probability vectors.

Proof

1.1F1F3F4F5F6givenalgebra

The probability simplex on $X$ is closed and bounded in $R^{∣ X ∣}$ . The feasible subset is closed because $P_{X} \mapsto \overset{ˉ}{c} (P_{X})$ is linear and continuous; it is nonempty because $δ_{x_{\min}}$ has cost $c_{\min} \leq Γ$ . Hence it is compact by [F5]. The output law $P_{X} W$ is linear in $P_{X}$ , so [F3]–[F4] show that $P_{X} \mapsto I (P_{X}; W)$ is continuous. Nonnegativity of mutual information follows from [F6] applied to the joint law and product marginals. Also $I (P_{X}; W) = H (P_{X}) - H (X ∣ Y) \leq H (P_{X})$ by [F3], since conditional entropy is a sum of nonnegative terms. Concavity in [F4] gives $H (P_{X}) \leq \ln ∣ X ∣$ : the uniform vector is the average of the finitely many coordinate permutations of $P_{X}$ , all of which have the same entropy. Thus the objective lies in $[0, \ln ∣ X ∣]$ , and [F5] proves its supremum is finite and attained.

2.1F1F2F3F4step 1.1algebra

If $Γ_{0} \leq Γ_{1}$ , the feasible set at $Γ_{0}$ is contained in the one at $Γ_{1}$ , proving monotonicity. For $0 \leq θ \leq 1$ , let $P_{0}, P_{1}$ attain $C_{I} (Γ_{0}), C_{I} (Γ_{1})$ . The mixture $P_{θ} = θ P_{0} + (1 - θ) P_{1}$ has cost at most $θ Γ_{0} + (1 - θ) Γ_{1}$ . By [F3]–[F4], mutual information is concave in $P_{X}$ : the output entropy is concave and the conditional entropy term is linear. Therefore $C_{I} (θ Γ_{0} + (1 - θ) Γ_{1}) \geq θ C_{I} (Γ_{0}) + (1 - θ) C_{I} (Γ_{1})$ .

3.1F1F3step 1.1givenalgebracases∎

Suppose $Γ > c_{\min}$ and $P_{X}^{*}$ attains $C_{I} (Γ)$ . If $\overset{ˉ}{c} (P_{X}^{*}) = Γ$ , choose a minimum-cost symbol $x_{\min}$ from the finite alphabet. Then $\overset{ˉ}{c} (P_{X, ϵ}) = (1 - ϵ) Γ + ϵ c_{\min} < Γ$ for every $ϵ > 0$ . Since $P_{X, ϵ} \to P_{X}^{*}$ and the mutual-information objective is continuous by step 1.1, $I (P_{X, ϵ}; W) \to C_{I} (Γ)$ . If $P_{X}^{*}$ already has strict cost, no approximation is needed.

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

Fano's inequality for a finite message observed through a density

Statement

Let $M$ be uniform on $[N]$ with $N \geq 2$ , and let an observation $Y$ have conditional densities $p_{m}$ with respect to a common measure. Put $q = N^{- 1} \sum_{m} p_{m}$ and define the posterior $π_{m} (y) = p_{m} (y) / (N q (y))$ wherever $q (y) > 0$ . For every measurable decoder $g (Y)$ with error probability $e = \Pr [g (Y) \neq M]$ , $H (M ∣ Y) \leq H (M ∣ g (Y)) \leq h_{2} (e) + e \ln (N - 1) \leq \ln 2 + e \ln N,$ where $h_{2} (e) = - e \ln e - (1 - e) \ln (1 - e)$ with $0 \ln 0 = 0$ .

Facts & Assumptions

Given: A uniform finite message, conditional observation densities, their mixture density, and a measurable finite-valued decoder.

[F1]

Finite distributions, entropy, divergence, and stochastic matrices: the entropy of a finite probability vector $r$ is $H (r) = - \sum_{i} r_{i} \ln r_{i}$ , with zero coordinates contributing zero.

[F2]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite probability vectors satisfy $D (r ∥ s) \geq 0$ whenever the divergence is defined, with equality exactly at $r = s$ .

[F3]

Finite-alphabet Fano inequality: for a finite message and a finite estimate with error probability $e$ , $H (M ∣ \hat{M}) \leq h_{2} (e) + e \ln (N - 1)$ .

[F4]

The natural logarithm as the inverse of the exponential function: the logarithms are natural, so entropies are in nats.

[F5]

A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere: a nonnegative measurable function with zero integral is zero almost everywhere, on an arbitrary measure space.

[F6]

A nonnegative measurable function with finite integral is finite almost everywhere: a nonnegative measurable function with finite integral is finite almost everywhere.

[F7]

A nonnegative integral over a null set vanishes: the nonnegative integral over a measurable null set is zero, even for an extended-valued integrand.

Proof

1.1F1F2F6F7givenalgebra

Since $\int q d ν = N^{- 1} \sum_{m} \int p_{m} d ν = 1$ , [F6] makes $B = {q = + \infty}$ a measurable $ν$ -null set. Replace every $p_{m}$ by zero on $B$ and use their new mixture $q$ ; [F7] shows that all conditional and marginal laws are unchanged. These density versions are finite everywhere, since $p_{m} \leq N q$ off $B$ . Define $π_{m} = p_{m} / (N q)$ where $q > 0$ and $π_{m} = 1 / N$ where $q = 0$ . This is a measurable probability vector everywhere and a posterior version: for every measurable $A$ , $\int_{A} q π_{m} d ν = N^{- 1} \int_{A} p_{m} d ν = \Pr (M = m, Y \in A)$ . Values on the zero-density set have no effect. Thus $H (M ∣ Y) = \int H (π) d Q$ , where $d Q = q d ν$ is the observation probability law. By [F1] and comparison with the uniform vector in [F2], $0 \leq H (π) \leq \ln N$ , so this conditional entropy is finite. All posterior formulas in the Statement are understood for these almost-everywhere density versions.

2.1F1F2F5step 1.1givenalgebracases

For each decoder value $j$ with $α_{j} = Q (A_{j}) > 0$ , let $A_{j} = g^{- 1} (j)$ and $r^{(j)} = α_{j}^{- 1} \int_{A_{j}} π d Q$ ; this is the posterior probability vector given that estimate. If $r_{m}^{(j)} = 0$ , then $\int_{A_{j}} π_{m} d Q = 0$ , so [F5], applied to the measure $Q$ restricted to $A_{j}$ , gives $π_{m} = 0$ almost everywhere there. Discard the union of these finitely many exceptional null sets. On the remainder, $π$ is supported on the positive coordinates of $r^{(j)}$ , so $D (π ∥ r^{(j)})$ has no infinite term. The finitely many constants $\ln r_{m}^{(j)}$ on that support and the bounded entropy in step 1.1 justify termwise integration. Expansion and [F2] give $α_{j}^{- 1} \int_{A_{j}} D (π ∥ r^{(j)}) d Q = H (r^{(j)}) - α_{j}^{- 1} \int_{A_{j}} H (π) d Q \geq 0$ . Decoder cells of zero $Q$ -mass contribute zero; summing over the other cells proves $H (M ∣ g (Y)) \geq H (M ∣ Y)$ .

3.1F3F4step 2.1given∎

Apply [F3] to the finite pair $(M, g (Y))$ . Its sharp and relaxed Fano bounds give both upper inequalities in the Statement; the entropy convention in [F4] makes them nats. Together with step 2.1 this proves the full chain.

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

Strictly feasible DMC input laws achieve every lower mutual-information rate

Statement

Let $W$ be a finite DMC with cost $c$ , feasible budget $Γ \geq c_{\min}$ , and cost-constrained information capacity $C_{I} (Γ)$ . For every $0 \leq R < C_{I} (Γ)$ , there are deterministic ordinary codes with rate tending to at least $R$ , average error tending to zero, and average block cost at most $Γ$ .

Facts & Assumptions

Given: The finite DMC and cost model, the feasible budget, and a rate $R$ strictly below $C_{I} (Γ)$ .

[A1]

Finite discrete memoryless channels, Finite DMC with a nonnegative input cost and feasible budget, Average-cost fixed-length codes and operational DMC capacity, Fixed-length codes for a finite DMC, and Average and maximal error of a fixed-length code: the product DMC, finite letter cost, deterministic code, uniform-message average error, and constrained information-capacity convention.

[F1]

Constrained DMC information capacity is attained, nondecreasing, and concave: the constrained maximum is attained, and for $Γ > c_{\min}$ its value can be approached by input laws of strictly smaller cost.

[F2]

IID DMC information density converges to mutual information: for a fixed finite DMC input law, the normalized IID information density converges in probability to $I (P_{X}; W)$ .

[F3]

Threshold decoding bound for memoryless channels with densities: an IID random code's expected average error is bounded by the information-density miss probability plus the threshold false-alarm term.

[F4]

A low-error random code can be pruned to satisfy a strict average cost constraint: if expected cost-violating fraction and ensemble average error both tend to zero, pruning yields feasible deterministic subcodes with vanishing error and vanishing rate loss.

[F5]

Chebyshev's inequality on a finite probability space: a finite random variable $V$ satisfies $\Pr (∣ V - E V ∣ \geq t) \leq Var (V) / t^{2}$ for $t > 0$ .

[F6]

Single-letter information capacity of a finite DMC, Finite DMC information density, and Finite stochastic kernels: the induced law determines mutual information and information density; each finite channel row sums to one.

Proof

1.1F1givencases

If $R = 0$ , the one-message code that repeats a minimum-cost symbol has zero error and cost $c_{\min} \leq Γ$ . Suppose $R > 0$ . If $Γ > c_{\min}$ , [F1] gives an input law $P_{X}$ with $\overset{ˉ}{c} (P_{X}) < Γ$ and $I (P_{X}; W) > R$ . If $Γ = c_{\min}$ , choose an attaining law from [F1]. Feasibility gives $\sum_{x} P_{X} (x) (c (x) - c_{\min}) \leq 0$ ; every summand is nonnegative, so this law is supported on minimum-cost symbols and its mutual information exceeds $R$ .

2.1F2step 1.1givenalgebra

Choose $δ > 0$ with $R + 2 δ < I (P_{X}; W)$ and $M_{n} = ⌈ e^{n R} ⌉$ . For the IID input and product DMC, [F2] makes the miss probability at threshold $\ln (M_{n} - 1) + n δ$ tend to zero, since the threshold divided by $n$ tends to $R + δ < I (P_{X}; W)$ .

3.1A1F3F4F5F6step 1.1step 2.1givencasesalgebra∎

By [F3], the IID random-code ensemble has expected average error $a_{n} \to 0$ . If $Γ > c_{\min}$ , the letter costs are bounded on the finite alphabet, so the variance of their $n$ -letter average is $Var (c (X_{1})) / n$ ; [F5] implies the expected fraction $q_{n}$ of codewords whose average cost exceeds $Γ$ tends to zero because $E c (X_{1}) < Γ$ . Apply [F4] to obtain deterministic subcodes with every retained word feasible, error tending to zero, and rate loss tending to zero. If $Γ = c_{\min}$ , every drawn input letter has minimum cost, so every random codeword has cost exactly $Γ$ and no pruning is needed; [F3] supplies deterministic codes with vanishing error.

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

An average-cost DMC block input has mutual information at most n C_I(Gamma)

Statement

Let $X^{n} = (X_{1}, \dots, X_{n})$ be any random input to a finite DMC $W$ and let the output follow the memoryless product channel. If $\frac{1}{n} \sum_{t = 1}^{n} E c (X_{t}) \leq Γ$ for a feasible budget $Γ$ , then $I (X^{n}; Y^{n}) \leq n C_{I} (Γ),$ where $C_{I}$ is defined in Average-cost fixed-length codes and operational DMC capacity.

Facts & Assumptions

Given: A finite DMC with finite letter cost, a feasible budget, and a possibly dependent block input satisfying the stated expected average cost constraint.

[F1]

Finite entropy and mutual-information chain rules: finite joint entropy and mutual information satisfy the chain rules.

[F2]

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

[F3]

Finite DMC with a nonnegative input cost and feasible budget, Average-cost fixed-length codes and operational DMC capacity, Single-letter information capacity of a finite DMC, and Finite probability vectors: $C_{I} (γ) = \sup_{P_{X} : E c (X) \leq γ} I (P_{X}; W)$ for every feasible $γ$ .

[F4]

Constrained DMC information capacity is attained, nondecreasing, and concave: $C_{I}$ is nondecreasing and concave on $[c_{\min}, \infty)$ .

[F5]

Finite discrete memoryless channels: conditioned on $X^{n}$ , the output coordinates have product law $\prod_{t} W (y_{t} ∣ X_{t})$ .

[F6]

Jensen's inequality for an integrable cost random variable: an integrable cost variable in $[c_{\min}, \infty)$ can be passed through a finite concave function by Jensen's inequality.

[F7]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite mutual information is nonnegative because it is a KL divergence.

Proof

1.1F1F2F5F7givenalgebra

By [F1], $H (Y^{n}) = \sum_{t} H (Y_{t} ∣ Y^{t - 1})$ . For each $t$ , the difference $H (Y_{t}) - H (Y_{t} ∣ Y^{t - 1}) = I (Y_{t}; Y^{t - 1})$ is nonnegative by [F7], so $H (Y^{n}) \leq \sum_{t} H (Y_{t})$ . The product channel [F5] and the chain rule give $H (Y^{n} ∣ X^{n}) = \sum_{t} H (Y_{t} ∣ X_{t})$ . Subtracting and using [F2] yields $I (X^{n}; Y^{n}) \leq \sum_{t = 1}^{n} I (X_{t}; Y_{t})$ .

1.2F3F4F6givenalgebra

Put $γ_{t} = E c (X_{t}) \geq c_{\min}$ . By [F3], $I (X_{t}; Y_{t}) \leq C_{I} (γ_{t})$ . Apply [F4] and [F6] to the uniform random variable taking values $γ_{1}, \dots, γ_{n}$ ; this gives $\sum_{t} C_{I} (γ_{t}) \leq n C_{I} (n^{- 1} \sum_{t} γ_{t}) \leq n C_{I} (Γ)$ .

2.1step 1.1step 1.2algebra∎

Combining steps 1.1 and 1.2 proves the claimed block bound.

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

Capacity of finite parallel Gaussian channels with and without feedback

Statement

Assume AC and use the finite-dimensional channel of dimension $d$ and covariance $K$ from Finite-dimensional additive Gaussian channel with average power. Let $λ_{1}, \dots, λ_{d} > 0$ be the eigenvalues of $K$ and put $λ_{\min} : = \min_{j} λ_{j}$ . Both the ordinary no-feedback capacity $C_{n f} (P)$ and the causal-feedback capacity $C_{f b} (P)$ defined in Causal feedback codes for a finite-dimensional Gaussian channel equal $C_{K} (P) = \max_{p_{j} \geq 0, \sum_{j} p_{j} \leq P} \frac{1}{2} \sum_{j = 1}^{d} \ln (1 + \frac{p_{j}}{λ_{j}}) = \frac{1}{2} \sum_{j = 1}^{d} \ln^{+} ⁣ (\frac{T}{λ_{j}}),$ where $T$ is the unique water level solving $\sum_{j} (T - λ_{j})^{+} = P$ when $P > 0$ ; for $P = 0$ , $C_{K} (0) = 0$ and all $p_{j} = 0$ . Thus feedback does not increase capacity.

Facts & Assumptions

Given: AC, a finite-dimensional additive Gaussian channel with positive-definite covariance, a finite-message code, and an expected average-power budget.

[A1]

The Axiom of Choice and Finite-dimensional additive Gaussian channel with average power: the Gaussian channel has independent fresh $N_{d} (0, K)$ noises and uses squared Euclidean norm as cost under AC.

[A2]

Causal feedback codes for a finite-dimensional Gaussian channel: each causal encoder has the form $f_{t} (M, Y^{t - 1})$ , the decoder is measurable, and the power constraint is expected average input energy.

[F1]

Orthogonal coordinates diagonalize a finite-dimensional Gaussian noise law: orthogonal coordinates diagonalize $K$ and preserve power and code/error correspondence.

[F2]

Finite-input vector Gaussian mutual information is bounded by water-filling: for every finite-support vector input of second moment at most $u$ , its one-use mutual information is at most $C_{K} (u)$ .

[F3]

Water-filling maximizes the finite parallel Gaussian allocation objective: $C_{K} (u)$ is the maximum allocation value and is nondecreasing and concave.

[F4]

Jensen's inequality for an integrable cost random variable: for integrable $U \geq 0$ , the finite concave function $C_{K}$ satisfies $E C_{K} (U) \leq C_{K} (E U)$ .

[F5]

Fano's inequality for a finite message observed through a density: for an $N$ -message variable observed through conditional densities and decoded with error $e$ , $H (M ∣ Y) \leq \ln 2 + e \ln N$ .

[F6]

Strictly feasible Gaussian inputs yield cost-feasible Gaussian codes: every rate below the Gaussian-input mutual information of a strict allocation is achievable with no feedback under the average power budget.

[F7]

A positive-definite multivariate normal law has its Gaussian density: positive-definite Gaussian noise has a positive Lebesgue density.

[F8]

The natural logarithm as the inverse of the exponential function: $\ln$ is the natural logarithm.

[F9]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\ln^{'} (x) = 1 / x$ for $x > 0$ , so integrating its derivative gives $\ln (1 + x) \leq x$ for $x \geq 0$ and continuity of the finite rate expression.

[F10]

A nonnegative measurable function has integral $0$ exactly when it vanishes almost everywhere: a nonnegative measurable function of integral zero vanishes almost everywhere; on the probability space this says zero expected nonnegative energy is zero almost surely.

Proof

1.1A1A2F1F2F5F7givenalgebra

Use [F1] to express the channel in independent scalar branches. For a feedback code from [A2], conditional on each message $m$ the output vector has density $p (y^{n} ∣ m) = \prod_{t = 1}^{n} ϕ_{K} (y_{t} - f_{t} (m, y^{t - 1})),$ where $ϕ_{K} (z) = (2 π)^{- d / 2} (\det K)^{- 1 / 2} \exp (- z^{T} K^{- 1} z / 2)$ is positive by [F7]. Thus [F5] applies. Since $M$ is finite, define $I (M; Y^{n}) = H (M) - H (M ∣ Y^{n})$ using the posterior density of [F5]. Bayes' formula factors $\Pr (M = m ∣ Y^{n}) / \Pr (M = m)$ into the product over $t$ of $p (Y_{t} ∣ M = m, Y^{t - 1}) / p (Y_{t} ∣ Y^{t - 1})$ ; taking logarithms and expectations proves $I (M; Y^{n}) = \sum_{t} I (M; Y_{t} ∣ Y^{t - 1})$ . At a fixed history, $X_{t} = f_{t} (M, h)$ has finite support; grouping the finite mixture terms for messages with the same input shows $I (M; Y_{t} ∣ h) = I (X_{t}; Y_{t} ∣ h)$ because their conditional output densities are identical. Hence [F2] bounds this by $C_{K} (u_{t, h})$ , where $u_{t, h} = E [∥ X_{t} ∥^{2} ∣ h]$ .

2.1F3F4F8F9step 1.1givenalgebra

Let $T$ be uniform on $[n]$ , independent of the channel, and let $H = Y^{T - 1}$ and $U = u_{T, H}$ . Then $U \geq 0$ and $E U = n^{- 1} \sum_{t} E ∥ X_{t} ∥^{2} \leq P$ . For every allocation with total power at most $u$ , [F8]--[F9] give $\frac{1}{2} \sum_{j} \ln (1 + p_{j} / λ_{j}) \leq \frac{1}{2} \sum_{j} p_{j} / λ_{j} \leq u / (2 λ_{\min})$ ; hence $C_{K} (U)$ is integrable. Apply [F4] to step 1.1 and then monotonicity of $C_{K}$ to obtain $I (M; Y^{n}) \leq n C_{K} (E U) \leq n C_{K} (P)$ .

3.1F5step 2.1givenalgebracases

If $N = 1$ the rate is zero. If $N \geq 2$ , [F5] and $H (M) = \ln N$ give $I (M; Y^{n}) \geq (1 - e) \ln N - \ln 2$ . Combining with step 2.1 shows every reliable feedback rate is at most $C_{K} (P)$ . The no-feedback capacity is bounded by the same argument because no-feedback codes are a subclass.

4.1A1A2F3F6F9F10step 3.1givencasesalgebra∎

If $P = 0$ , put $V = \sum_{t = 1}^{n} ∥ X_{t} ∥^{2}$ . This is nonnegative and the expected-power constraint gives $E V \leq n P = 0$ , hence $E V = 0$ . By [F10], $V = 0$ almost surely, and every summand is therefore zero almost surely. Thus $X_{t} = 0$ for every $t$ outside one null set and $Y^{n} = Z^{n}$ almost surely. The fresh noise vector is independent of the message by [A1], so the outputs carry no message information and the Fano bound in step 3.1 gives zero reliable rate. One-message codes attain rate zero. If $P > 0$ , [F3] supplies the allocation $p_{j}^{*}$ with total power $P$ . For any $R < C_{K} (P)$ choose $ϵ > 0$ so the strict allocation $(1 - ϵ) p^{*}$ has Gaussian mutual information greater than $R$ ; continuity from [F9] gives such an $ϵ$ . Apply [F6] to obtain no-feedback codes at every such rate, and therefore also feedback codes. Letting $R ↑ C_{K} (P)$ proves both lower bounds, including the case $C_{K} (P) = 0$ by a one-message code.

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

Average-cost capacity formula for a finite DMC

Statement

Let $W$ be a finite DMC with finite nonnegative input cost $c$ , and let $Γ \geq c_{\min}$ . Under the uniform-message average block-cost and average-error conventions of Average-cost fixed-length codes and operational DMC capacity, the operational capacity is $C (Γ) = C_{I} (Γ) = \max_{P_{X} : E c (X) \leq Γ} I (P_{X}; W),$ with all rates measured in nats per use.

Facts & Assumptions

Given: A finite memoryless channel, a finite letter cost, and a feasible average-cost budget.

[A1]

Finite discrete memoryless channels, Finite DMC with a nonnegative input cost and feasible budget, and Average-cost fixed-length codes and operational DMC capacity: $C (Γ)$ uses deterministic length- $n$ codes, uniform-message average error and average block cost; $C_{I}$ is the supremum over input laws with expected letter cost at most $Γ$ .

[F1]

Constrained DMC information capacity is attained, nondecreasing, and concave: the feasible input set is compact, the maximum is attained, and $C_{I}$ is nondecreasing and concave; for $Γ > c_{\min}$ its maximum can be approached with strict-cost laws.

[F2]

An average-cost DMC block input has mutual information at most n C_I(Gamma): every block input satisfying the average cost constraint obeys $I (X^{n}; Y^{n}) \leq n C_{I} (Γ)$ .

[F3]

Strictly feasible DMC input laws achieve every lower mutual-information rate: every rate below $C_{I} (Γ)$ is achievable by average-cost feasible ordinary codes, including the minimum-cost endpoint.

[F4]

Finite-alphabet Fano inequality: if an estimate of a uniform $M$ -message variable has error $e$ , then $H (M ∣ \hat{M}) \leq h_{2} (e) + e \ln (M - 1)$ .

[F5]

Finite entropy and mutual-information chain rules: finite entropy obeys the chain rule and $I (U; V) = H (U) - H (U ∣ V)$ .

[F6]

Data processing for a finite Markov chain, with equality condition: for finite Markov variables $U \to V \to Z$ , $I (U; Z) \leq I (V; Z)$ .

Proof

1.1A1F2F4F5F6givenalgebracases

If $M = 1$ , the rate is zero and the converse is immediate. Suppose $M \geq 2$ . Then the message and channel variables form the finite Markov chains $M \to X^{n} \to Y^{n}$ and $M \to Y^{n} \to \hat{M}$ . By [F5] and [F6], $I (M; Y^{n}) \geq I (M; \hat{M}) = \ln M - H (M ∣ \hat{M}) \geq (1 - e) \ln M - \ln 2$ , using the relaxed Fano bound in [F4]. Feasibility and [A1] give $n^{- 1} \sum_{t} E c (X_{t}) \leq Γ$ , so [F2] applies. Also [F6] gives $I (M; Y^{n}) \leq I (X^{n}; Y^{n})$ , and [F2] bounds the latter by $n C_{I} (Γ)$ . Hence $(1 - e) \ln M \leq n C_{I} (Γ) + \ln 2$ .

2.1step 1.1givenalgebra

Along any reliable sequence, $e_{n} \to 0$ , so step 1.1 implies $lim sup n^{- 1} \ln M_{n} \leq C_{I} (Γ)$ . This proves $C (Γ) \leq C_{I} (Γ)$ .

3.1F1F3givencases∎

For $R = 0$ , a one-message minimum-cost code is feasible. If $0 < R < C_{I} (Γ)$ , [F3] constructs a reliable feasible code sequence of rate at least $R$ . Therefore every rate below $C_{I} (Γ)$ is operationally achievable, so $C (Γ) \geq C_{I} (Γ)$ by the supremum definition, also when $C_{I} (Γ) = 0$ . Attainment of the displayed maximum is [F1].

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

An inactive DMC cost constraint recovers ordinary capacity

Statement

For a finite DMC with letter cost $c$ and budget $Γ \geq c_{\max}$ , the cost-constrained operational capacity equals the ordinary DMC capacity, with the same average-error convention and in nats.

Facts & Assumptions

Given: A finite DMC, a finite letter cost, and a budget at least the maximum letter cost.

[F1]

Finite DMC with a nonnegative input cost and feasible budget and Average-cost fixed-length codes and operational DMC capacity: each codeword's per-use average cost is an average of the letter costs and the information-capacity constraint is $E c (X) \leq Γ$ .

[F2]

Average-cost capacity formula for a finite DMC: the cost-constrained operational capacity equals $\max_{P_{X} : E c (X) \leq Γ} I (P_{X}; W)$ .

[F3]

Operational capacity formula for a finite DMC: ordinary average-error DMC capacity equals $\max_{P_{X}} I (P_{X}; W)$ .

Proof

1.1F1givenalgebra

Every letter has $c (x) \leq c_{\max} \leq Γ$ by [F1]. Therefore every ordinary code satisfies the block cost constraint, and every input distribution satisfies the one-letter cost constraint. Conversely a cost-feasible code or distribution is still an ordinary one, so the two code classes and feasible input sets coincide.

2.1F2F3step 1.1given∎

Apply [F2] and [F3] to these identical code and input classes. Their operational capacities agree; both use average error and natural-log nats by their definitions.

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

Causal feedback does not increase finite DMC capacity under average cost

Statement

For every finite DMC and finite nonnegative letter cost with feasible budget $Γ$ , the feedback operational capacity $C_{f b} (Γ)$ defined in Causal feedback codes for a finite cost-constrained DMC equals the ordinary average-error capacity $C (Γ)$ in Average-cost fixed-length codes and operational DMC capacity. Thus $C_{f b} (Γ) = C_{I} (Γ)$ .

Facts & Assumptions

Given: A finite DMC, its finite letter cost, a feasible budget, and a causal deterministic feedback code with message count $M$ and uniform random message $U \in [M]$ .

[A1]

Causal feedback codes for a finite cost-constrained DMC: at each time $t$ , $X_{t} = f_{t} (U, Y^{t - 1})$ and the conditional output row is $W (\cdot ∣ X_{t})$ ; the cost is expected average letter cost.

[F1]

Finite entropy and mutual-information chain rules: mutual information expands as $I (U; Y^{n}) = \sum_{t} I (U; Y_{t} ∣ Y^{t - 1})$ .

[F2]

Data processing for a finite Markov chain, with equality condition: conditionally on a history $h$ , the finite Markov relation $U \to X_{t} \to Y_{t}$ implies $I (U; Y_{t} ∣ Y^{t - 1} = h) \leq I (X_{t}; Y_{t} ∣ Y^{t - 1} = h)$ .

[F3]

Finite DMC with a nonnegative input cost and feasible budget and Constrained DMC information capacity is attained, nondecreasing, and concave: $C_{I} (u)$ is nondecreasing and concave for $u \geq c_{\min}$ and satisfies $0 \leq C_{I} (u) \leq \ln ∣ X ∣$ .

[F4]

Jensen's inequality for an integrable cost random variable: for an integrable random cost $V \geq c_{\min}$ and finite concave $f$ , $E f (V) \leq f (E V)$ .

[F5]

Finite-alphabet Fano inequality: for $M \geq 2$ , the decoder $\hat{U} = g (Y^{n})$ with error $e = \Pr [\hat{U} \neq U]$ satisfies $H (U ∣ \hat{U}) \leq h_{2} (e) + e \ln (M - 1)$ .

[F6]

Average-cost capacity formula for a finite DMC: the ordinary capacity equals $C_{I} (Γ)$ .

Proof

1.1A1F1F2F3givenalgebra

For each time $t$ and each positive-probability history $h = y^{t - 1}$ , the causal encoder and memoryless channel give the finite Markov chain $U \to X_{t} \to Y_{t}$ . By chain rule [F1] and data processing [F2], $I (U; Y^{n}) \leq \sum_{t = 1}^{n} E_{Y^{t - 1}} C_{I} (E [c (X_{t}) ∣ Y^{t - 1}])$ , applying the definition of $C_{I}$ to each conditional input law, whose cost is at least $c_{\min}$ .

2.1F3F4step 1.1givenalgebra

Give a uniform random index $T \in [n]$ independent of the code and set $V = E [c (X_{T}) ∣ T, Y^{T - 1}]$ . Then $V \geq c_{\min}$ , $E V = n^{- 1} \sum_{t} E c (X_{t}) \leq Γ$ , and $C_{I} (V)$ is integrable by [F3]. Applying [F4] and monotonicity in [F3] to step 1.1 yields $I (U; Y^{n}) \leq n E C_{I} (V) \leq n C_{I} (E V) \leq n C_{I} (Γ)$ .

3.1F5F6step 2.1givenalgebracases∎

If $M = 1$ , the rate is zero. If $M \geq 2$ , the relaxed Fano bound [F5] and the deterministic decoder imply $(1 - e) \ln M \leq I (U; Y^{n}) + \ln 2 \leq n C_{I} (Γ) + \ln 2$ . Thus reliable feedback rates are at most $C_{I} (Γ) = C (Γ)$ by [F6]. Every ordinary feasible code is a feedback code whose encoders ignore past outputs, so $C_{f b} (Γ) \geq C (Γ)$ ; the reverse inequality follows from the converse.

5 · Examples, counterexamples and false statements

None yet.