InformationTheory

InformationTheory.Shannon.AWGN.PerCodewordPowerConstraint

source

Per-codeword power constraint #

The per-codeword power-constraint expurgation bound for the AWGN channel: each individual codeword drawn from the Gaussian product law violates the power budget on a codebook set of vanishing mass. This is the WLLN/Markov fact consumed by the Cover–Thomas expurgation argument.

Main statements #

Per-codeword power constraint #

theorem

InformationTheory.Shannon.AWGN.awgnPowerConstraintPerCodeword_holds

source
(P_cb P_target : ) (hP_slack : P_cb.toNNReal < P_target) (N : NNReal) ε : :
0 < ε∃ (N₀ : ), ∀ ⦃n : ⦄, N₀ n∀ ⦃M : ⦄, 0 < M∀ (m : Fin M), (MeasureTheory.Measure.pi fun (x : Fin M) => MeasureTheory.Measure.pi fun (x : Fin n) => ProbabilityTheory.gaussianReal 0 P_cb.toNNReal) {c : Fin MFin n | n * P_target < i : Fin n, c m i ^ 2} ENNReal.ofReal ε

Per-codeword power-constraint expurgation bound.

For a codebook drawn from the 2-stage Gaussian product law at codeword variance P_cb, and a power target P_target with strict slack P_cb < P_target, each individual codeword m violates the power budget ∑ᵢ (c m i)² > n · P_target on a codebook set of mass ≤ ε (for all n past a threshold N₀).

This is the per-codeword marginal form: unlike the false ∀ m-form (mass of the all-codewords-OK set ≥ 1 − ε, which decays like q^M ≈ exp(−exp(n(R−ψ)))), the per-codeword marginal mass is M-independent (the m-th coordinate marginal of Measure.pi (fun _ : Fin M => νₙ) is νₙ), so no exponential rate / capacity rate bound is needed. It is exactly the WLLN/Markov fact the Cover–Thomas expurgation argument consumes.

Proof: the m-th coordinate marginal is νₙ = Measure.pi (fun _ : Fin n => gaussianReal 0 P_cb.toNNReal) (measurePreserving_eval), reducing the codebook mass to the single-codeword chi-square upper-tail mass. Apply the abstract Chebyshev engine pi_empirical_mean_concentration with statistic φ x = x², μ[φ] = (P_cb.toNNReal : ℝ) (centred Gaussian second moment = variance), and the deviation level δ = P_target − (P_cb.toNNReal : ℝ) > 0: the violating set {x | n·P_target < ∑ᵢ xᵢ²} is contained in the deviation set {x | δ ≤ |(∑ᵢ φ(xᵢ))/n − μ[φ]|}, whose mass is ≤ variance(φ)/(n·δ²); choosing N₀ > variance(φ)/(ε·δ²) gives ≤ ε. MemLp φ 2 holds because the Gaussian has a finite 4th moment (memLp_id_gaussianReal 4, polynomial — no log).

Used by