TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

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

Depends on

Used by

Dependency tree · two levels

32 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning, Chapter 20 §20.1 (standard reference, not scraped)
Yury Polyanskiy, MIT 6.441 Information Theory, Chapter 17 §§17.1–17.2 (standard reference, not scraped)