InformationTheory.Shannon.AWGN.CapacityConverseMaxent
AWGN single-letter capacity converse (Gaussian max-entropy) #
The single-letter capacity converse: for any input law p : Measure ℝ with second
moment ≤ P, (mutualInfoOfChannel p (awgnChannel N)).toReal ≤ (1/2) log(1 + P/N).
This discharges the h_max_ent hypothesis of
awgnCapacity_eq (AWGN/Basic.lean).
Main statements #
awgn_per_input_mi_le_log— the per-input mutual-information bound.awgn_capacity_closed_form_genuine— the assembled capacity closed form.
Implementation notes #
The argument follows Cover–Thomas. I(X;Y) = h(Y) − h(Y|X) (chain rule
mutualInfoOfChannel_toReal_eq_diffEntropy_sub) combines with the Gaussian
max-entropy bound differentialEntropy_le_gaussian_of_variance_le:
MI = h(Y) − h(Y|X)(chain rule, proxy form).h(Y|X) = ∫ h(𝒩(x,N)) dp = (1/2) log(2πeN)(fiber entropy constant).h(Y) ≤ (1/2) log(2πe·Var(Y))(max-entropy,m := E[Y]).Var(Y) ≤ E[X²] + N ≤ P + N.- arithmetic
(1/2)log(2πe(P+N)) − (1/2)log(2πeN) = (1/2)log(1+P/N).
The output law is q := outputDistribution p W = p ∗ 𝒩(0,N). The hardest step is the
mixture-output log-density integrability (h_int_out / h_ent_int), isolated in
outputDistribution_logDensity_integrable; it is proven via the convolution density
representation q = vol.withDensity (∫⁻ x, gaussianPDF x N · ∂p), the Gaussian upper
bound, the mixture Gaussian lower bound (Chebyshev concentration + Gaussian tail), and
finite-second-moment domination.
Gaussian pdf sup upper bound #
InformationTheory.Shannon.AWGN.gaussianPDFReal_le_sup
sourceGaussian pdf sup upper bound gaussianPDFReal m v y ≤ (√(2πv))⁻¹.
The exponential factor rexp (-(y-m)²/(2v)) is ≤ 1 (nonpositive exponent), so the
pdf is bounded above by its normalization constant.
Used by
Output law is the noise convolution #
InformationTheory.Shannon.AWGN.outputDistribution_awgn_eq_conv
sourceFor any SFinite input p, the AWGN output is the convolution with the noise
law: outputDistribution p (awgnChannel N h_meas) = p ∗ gaussianReal 0 N.
Via outputDistribution = (p⊗ₘW).snd = W ∘ₘ p (snd_compProd) and the in-tree
translation-kernel ↔ convolution bridge bind_eq_conv_of_translation_kernel.
Used by
Log algebra #
InformationTheory.Shannon.AWGN.capacity_log_diff
sourceThe capacity log-algebra step:
(1/2)log(2πe(P+N)) − (1/2)log(2πeN) = (1/2)log(1+P/N).
Used by
Output second moment / variance bound #
InformationTheory.Shannon.AWGN.integral_sub_sq_gaussianReal
sourceSecond moment of a shifted real Gaussian: ∫ z, (z − c)² ∂𝒩(0,N) = N + c².
Used by
InformationTheory.Shannon.AWGN.output_sq_sub_integrable
source(y − m)² is integrable against the mixture output law p ∗ 𝒩(0,N) (for any m),
given that the input second moment is integrable.
hp_2mom_int : Integrable (fun x ↦ x²) p is a regularity precondition: the bare
constraint ∫ x² ∂p ≤ P does not imply integrability (a non-integrable x² gives the
degenerate ∫ x² ∂p = 0 ≤ P).
Used by
InformationTheory.Shannon.AWGN.output_secondMoment_eq
sourceSecond moment of the mixture output: ∫ y² ∂(p ∗ 𝒩(0,N)) = ∫ x² ∂p + N.
Via integral_conv (the output is (p.prod 𝒩).map (·+·)) and the fiber identity
∫ z, (x + z)² ∂𝒩(0,N) = x² + N.
Used by
InformationTheory.Shannon.AWGN.output_variance_le
sourceThe mixture output law q = p ∗ 𝒩(0,N) has variance at most P + N:
Var(Y) ≤ E[Y²] = E[X²] + N ≤ P + N. With m := ∫ y ∂q the true mean,
∫ (y − m)² ∂q = Var(Y) ≤ P + N.
hp_2mom_int is a regularity precondition (see output_sq_sub_integrable).
Used by
Fiber absolute continuity w.r.t. output #
InformationTheory.Shannon.AWGN.fibre_absolutelyContinuous_output_general
sourceEach AWGN fiber is absolutely continuous w.r.t. the (mixture) output law:
∀ x, awgnChannel N h_meas x ≪ outputDistribution p (awgnChannel N h_meas).
The output q = p ∗ 𝒩(0,N) is full-support since 𝒩(0,N) ≪ volume, so each
𝒩(x,N) ≪ q. The in-tree awgnChannel_apply_absolutelyContinuous_output is
Gaussian-input-only and not reusable here.
Used by
InformationTheory.Shannon.AWGN.integrable_log_proxy_fibre_compProd_general
sourceProxy-form joint integrability of the AWGN fiber log-density for an arbitrary
probability-measure input p: fun z ↦ Real.log (gaussianPDF z.1 N z.2).toReal is
integrable against the joint p ⊗ₘ awgnChannel N. The integrand decomposes everywhere
as c₀ + c₁·(z.2 − z.1)², and the (z.2 − z.1)² term is integrable against the joint
via Measure.integrable_compProd_iff (per-fiber integrability + constant L¹-norm N).
The proof uses only that p is a probability measure, so it is the general-p
counterpart of the Gaussian-input-only
ContChannelMIDecomp.integrable_log_proxy_fibre_compProd.
Used by
Mixture output log-density integrability #
InformationTheory.Shannon.AWGN.outputMixtureDensity
sourceThe mixture output density f_q(y) := ∫⁻ x, gaussianPDF x N y ∂p (the value of the
convolution density at y). The output law q = p ∗ 𝒩(0,N) equals
volume.withDensity outputMixtureDensity.
Equations
- InformationTheory.Shannon.AWGN.outputMixtureDensity N p y = ∫⁻ (x : ℝ), ProbabilityTheory.gaussianPDF x N y ∂p
Instances For
Used by
InformationTheory.Shannon.AWGN.measurable_outputMixtureDensity
sourceThe mixture density is jointly measurable in y.
Used by
InformationTheory.Shannon.AWGN.measurable_gaussianPDF_fst
sourceMeasurability of the Gaussian pdf in the mean parameter (fixed argument y):
Measurable (fun x ↦ gaussianPDF x N y). Isolated as its own declaration because the
(uncurry).comp term, if elaborated with an expected type pushed in, makes isDefEq
unfold gaussianPDF/gaussianPDFReal and hit a heartbeat timeout; the have h := …; exact h
shape elaborates comp freely and matches cheaply. Consumers call this lemma (term reuse).
Used by
InformationTheory.Shannon.AWGN.output_eq_withDensity_mixture
sourceThe mixture output q = p ∗ 𝒩(0,N) is
volume.withDensity (fun y ↦ ∫⁻ x, gaussianPDF x N y ∂p). Holds for any input p
(possibly discrete) since the noise is absolutely continuous, via lintegral_conv
(Tonelli) and the translation 𝒩(x,N) = volume.withDensity (gaussianPDF x N).
The Gaussian density is kept behind the opaque local g := fun z ↦ gaussianPDF z.1 N z.2
to stop isDefEq/whnf from unfolding gaussianReal/gaussianPDFReal during the Fubini
swap (which otherwise hits a heartbeat timeout).
@audit:ok
Used by
InformationTheory.Shannon.AWGN.output_rnDeriv_ae_mixture
sourceThe output rnDeriv is a.e. the mixture density.
Used by
InformationTheory.Shannon.AWGN.outputMixtureDensity_le_sup
sourceThe mixture density is bounded above by (√(2πN))⁻¹: each Gaussian component is
≤ (√(2πN))⁻¹ (gaussianPDFReal_le_sup), and p is a probability measure, so the
average inherits the bound.
Used by
InformationTheory.Shannon.AWGN.output_logDensity_lower_bound
sourceThe mixture density admits a Gaussian lower bound f_q(y) ≥ c·exp(−a·y²) with
c, a > 0, equivalently a quadratic upper bound on −log f_q: there exist a, b : ℝ
with −log (f_q y).toReal ≤ a · y² + b for all y. Chebyshev concentrates ≥ 1/2
of the mass of p on {|x| ≤ R} (from the finite second moment), and on that set
gaussianPDF x N y has a Gaussian-tail lower bound quadratic in y.
@audit:ok
Used by
InformationTheory.Shannon.AWGN.outputMixtureDensity_log_abs_le
sourceQuadratic bound on |log f_q|: there exist c₀, c₁ : ℝ with
|log (f_q y).toReal| ≤ c₀ + c₁ · y² for all y. Combines the constant upper bound
outputMixtureDensity_le_sup with the quadratic lower bound
output_logDensity_lower_bound.
Used by
InformationTheory.Shannon.AWGN.outputDistribution_logDensity_integrable
sourceThe continuous mixture output q = p ∗ 𝒩(0,N) has integrable log-density:
negMulLog ((q.rnDeriv vol ·).toReal) is volume-integrable. The output density is
bounded above by (√(2πN))⁻¹ and −log f_q is bounded by a quadratic, so
|negMulLog f_q(y)| = |f_q(y) · log f_q(y)| ≤ f_q(y)·(c₀ + c₁·y²), integrable against
volume since ∫ f_q(y)·(c₀+c₁y²) dvol = ∫ (c₀+c₁y²) dq < ∞ (finite second moment of
q).
The input p is constrained by membership in awgnPowerConstraintSet P (lintegral
second moment ≤ P), which carries the genuine integrability of x² via
awgnPowerConstraintSet_mem_iff_integrable. This rules out the heavy-tailed inputs
(Cauchy etc.) that would break the statement.
@audit:ok
Used by
InformationTheory.Shannon.AWGN.outputDistribution_logDensity_integrable_joint
sourceJoint form of outputDistribution_logDensity_integrable:
log ((q.rnDeriv vol ·).toReal) ∘ snd is integrable against the joint p ⊗ₘ W.
Lift along the snd-marginal: q = (p ⊗ₘ W).map Prod.snd, and |log f_q| ≤ c₀ + c₁·y²
is integrable against q (finite second moment), so the snd-pullback is integrable
against p ⊗ₘ W, via integrable_map_measure and outputMixtureDensity_log_abs_le.
@audit:ok
Used by
Per-input mutual-information bound #
InformationTheory.Shannon.AWGN.awgn_per_input_mi_le_log
sourceFinal converse conclusion (supplies the h_max_ent of
awgnCapacity_eq). For any input law p ∈ awgnPowerConstraintSet P
(lintegral second moment ≤ P),
(mutualInfoOfChannel p (awgnChannel N)).toReal ≤ (1/2) log(1 + P/N).
Assembled from the chain rule (mutualInfoOfChannel_toReal_eq_diffEntropy_sub),
the fiber entropy constant, the Gaussian max-entropy bound
(differentialEntropy_le_gaussian_of_variance_le), Var(Y) ≤ P + N, and the capacity
log-algebra.
The constraint is membership in awgnPowerConstraintSet P (lintegral form), which
carries the genuine integrability of x² (awgnPowerConstraintSet_mem_iff_integrable),
ruling out the heavy-tailed inputs (Cauchy etc.) that make a Bochner-only signature
false. The output log-density integrability hypotheses (h_int_out / h_ent_int) are
supplied by outputDistribution_logDensity_integrable[_joint].
@audit:ok
Used by
Capacity closed form #
InformationTheory.Shannon.AWGN.awgn_capacity_closed_form_genuine
sourceAWGN capacity closed form (Cover-Thomas).
awgnCapacity P N = (1/2) log(1 + P/N). This supersedes
awgnCapacity_eq (AWGN/Basic.lean): there the converse
max-entropy bound h_max_ent was an explicit hypothesis; here it is discharged by
awgn_per_input_mi_le_log. The achievability bridge (awgn_mi_gaussian_closed_form_of_out),
the MI decomposition (isAwgnMIDecomp_of_densitySplit) and the bind/conv
output-Gaussian fact are all wired upstream.
@audit:ok