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.
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 . Let and choose with . Then every rate is achievable by deterministic no-feedback codes meeting average block power 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.
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.
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.
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.
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 .
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 .
A normal variable has finite fourth moment: and for standard normal , with scaling for any branch variance.
Chebyshev-Markov inequality for the integral: a nonnegative measurable variable satisfies for .
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.
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
Use [F1] to work in orthogonal coordinates, and draw each vector use independently with branch inputs , independent across branches. Put . By [F2], the normalized sum of information densities converges in probability to .
If , one-message codes meet the assertion. Suppose , choose with , and put . The threshold is eventually below . The weak law in [F2] makes the miss probability tend to zero; [F3] then shows the ensemble expected average error tends to zero.
For one vector use put . By [F4], and ; [F7] then gives , and independence factors the cross moments to yield . Across uses the codeword average cost has mean and variance . With , the event is contained in , whose probability is at most by [F5] applied to the squared deviation. This probability is the expected fraction of over-budget codewords, so .
The codewords are drawn IID, hence are exchangeable, and the random code ensemble has 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 , error tending to zero, and rate loss tending to zero. Orthogonal invariance in [F1] carries these codes back to the original channel.
Depends on
- The Axiom of Choice
- Finite-dimensional additive Gaussian channel with average power
- Causal feedback codes for a finite-dimensional Gaussian channel
- A low-error random code can be pruned to satisfy a strict average cost constraint
- Threshold decoding bound for memoryless channels with densities
- Orthogonal coordinates diagonalize a finite-dimensional Gaussian noise law
- Parallel Gaussian information density obeys a finite-variance law of large numbers
- A normal variable has finite fourth moment
- Moments, variance, and covariance on a probability space
- Expectations factor over finite products of independent random variables
- Chebyshev-Markov inequality for the integral
Used by
Dependency tree · two levels
45 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, 20.3 (standard reference, not scraped)
- Yury Polyanskiy, MIT 6.441 Information Theory, Chapter 17 §§17.1–17.3 (standard reference, not scraped)