InformationTheory

InformationTheory.Shannon.WynerZiv.Achievability.MassBound

source

Wyner–Ziv achievability — source→ambient AEP mass transport and entropy helpers #

Source→ambient transport of the per-codeword AEP mass bound #

The per-covering-codeword side-information typicality mass, taken under the Wyner–Ziv source product measure Measure.pi (source per-coord) on α' × β, is transported to the abstract per-codeword AEP bound wz_covering_codeword_sideInfo_mass_le on the side-information ambient rdAmbient (wzSideInfoMarginal P_XY κ') over the positive-Y-marginal subtype β'. The transport combines (a) the n-fold side-information-law agreement (the source's Y-law is the β-image of the ambient's β'-Y-law), and (b) the entropy → wzMutualInfoYU exponent bridge. The generic injective-map helpers preserve entropy and per-atom mass under the β' → β coercion (the source lives over full β, the ambient over the subtype).

theorem

InformationTheory.Shannon.wz_source_codeword_sideInfo_mass_le

source
{α : Type u_1} {β : Type u_2} [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] (P_XY : MeasureTheory.Measure (α × β)) [MeasureTheory.IsProbabilityMeasure P_XY] [Nonempty { x : α // 0 < y : β, P_XY.real {(x, y)} }] {k : } [Nonempty (Fin k)] (κ' : αFin k) (hκ'pos : ∀ (x : α) (u : Fin k), 0 < κ' x u) (hκ'sum : ∀ (x : α), u : Fin k, κ' x u = 1) (q' : α × β × Fin k) (hfact_eq : ∀ (x : α) (y : β) (u : Fin k), q' (x, y, u) = κ' x u * P_XY.real {(x, y)}) (ε : ) (hε_pos : 0 < ε) (n : ) (u : Fin nFin k) :
(MeasureTheory.Measure.pi fun (x : Fin n) => ChannelCoding.pmfToMeasure fun (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × β) => P_XY.real {(p.1, p.2)}).real {p : Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} } × β | (u, fun (i : Fin n) => (p i).2) ChannelCoding.jointlyTypicalSet (rdAmbient (wzSideInfoMarginal P_XY κ')) ChannelCoding.iidXs (fun (i : ) (ω : Fin k × { y : β // 0 < x : α, P_XY.real {(x, y)} }) => (ChannelCoding.iidYs i ω)) n ε} Real.exp (-n * (wzMutualInfoYU (Fin k) q' - 3 * ε))

Per-covering-codeword side-information typicality mass, under the source product measure. For any fixed covering codeword u : Fin n → Fin k, the probability — under the Wyner–Ziv source product measure Measure.pi of p ↦ P_XY{(p.1.1, p.2)} on α' × β — that u is jointly typical (radius ε, side-information ambient rdAmbient (wzSideInfoMarginal P_XY κ')) with the side-information block fun i ↦ (p i).2 is at most exp(−n · (I(Y;U) − 3ε)), where I(Y;U) = wzMutualInfoYU (Fin k) q'.

This transports wz_covering_codeword_sideInfo_mass_le from the side-information ambient onto the source product measure. Two facts do the work. Side-information-law agreement: the source pair law's β-marginal is y ↦ ∑_x P_XY{(x,y)}, and the β-coerced β'-marginal of wzSideInfoMarginal summed over the covering codeword is y ↦ ∑_x κ' x u · P_XY{(x,y)} = ∑_x P_XY{(x,y)} by hκ'sum, so the source's n-fold Y-law is the β-image (Subtype.val) of the ambient's β'-Y-law (Measure.pi_map_pi + the iid n-fold law) and the fixed-u slice mass is preserved (the β-vs-β' alphabet gap is absorbed by the injective coercion, under which entropy and pmfLog are invariant). Exponent bridge: wzMutualInfoYU (Fin k) q' equals the ambient's I(U;Y) = H(U)+H(Y)-H(U,Y) (the β-values outside β' carry zero mass, negMulLog 0 = 0), which discharges the exponent hypothesis at I_YU := wzMutualInfoYU q' - 3ε.

Non-bundled: the conclusion is a per-codeword mass upper bound (Measure.real {…} ≤ exp …), not the operational error probability; hκ'pos/hκ'sum/hfact_eq are the covering-kernel regularity preconditions, and the exponent is pinned to the actual pmf by hfact_eq (no free-exponent gap).

@audit:ok

Used by
    theorem

    InformationTheory.Shannon.wz_exists_binning_E2_bound

    source
    {α : Type u_1} {β : Type u_2} {γ : Type u_3} [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [Fintype γ] [DecidableEq γ] [Nonempty γ] [MeasurableSpace γ] [MeasurableSingletonClass γ] (P_XY : MeasureTheory.Measure (α × β)) [MeasureTheory.IsProbabilityMeasure P_XY] [Nonempty { x : α // 0 < y : β, P_XY.real {(x, y)} }] (d : DistortionFn α γ) (R : ) {k : } [Nonempty (Fin k)] (κ' : αFin k) (hκ'pos : ∀ (x : α) (u : Fin k), 0 < κ' x u) (hκ'sum : ∀ (x : α), u : Fin k, κ' x u = 1) (q' : α × β × Fin k) (hfact_eq : ∀ (x : α) (y : β) (u : Fin k), q' (x, y, u) = κ' x u * P_XY.real {(x, y)}) (R₁ ε : ) (hε_pos : 0 < ε) (hε_conf : R₁ - wzMutualInfoYU (Fin k) q' + 3 * ε < R) (qf : (α × β × Fin k) × (Fin k × βγ)) (dα' : DistortionFn { x : α // 0 < y : β, P_XY.real {(x, y)} } γ) (hd'_link : ∀ (x' : { x : α // 0 < y : β, P_XY.real {(x, y)} }) (g : γ), dα' x' g = d (↑x') g) (δ : ) ( : 0 < δ) :
    ∃ (N_E2 : ), ∀ (n : ), N_E2 n∀ (M₁ : ) (c₁ : LossyCode M₁ n { x : α // 0 < y : β, P_XY.real {(x, y)} } (Fin k)), M₁ Real.exp (n * R₁) + 1(MeasureTheory.Measure.pi fun (x : Fin n) => ChannelCoding.pmfToMeasure fun (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × β) => P_XY.real {(p.1, p.2)}).real (wzCoveringAcceptFailSet P_XY κ' c₁ ε) δ / 2 / (8 * (distortionMax d + 1)) → ∃ (f : Fin M₁Fin (codebookSize R n)), distortionMax dα' * (MeasureTheory.Measure.pi fun (x : Fin n) => ChannelCoding.pmfToMeasure fun (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × β) => P_XY.real {(p.1, p.2)}).real {p : Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} } × β | wzBinTypicalDecoder (rdAmbient (wzSideInfoMarginal P_XY κ')) ChannelCoding.iidXs (fun (i : ) (ω : Fin k × { y : β // 0 < x : α, P_XY.real {(x, y)} }) => (ChannelCoding.iidYs i ω)) ε c₁ f (f (c₁.encoder fun (j : Fin n) => (p j).1), fun (i : Fin n) => (p i).2) c₁.decoder (c₁.encoder fun (j : Fin n) => (p j).1)} δ / 4

    Codebook-restricted confusion (E2) probability is squeezable. For a covering codebook of size M₁ ≲ exp(n·R₁) and n beyond a threshold, at the shared conditional-typicality radius ε (an explicit input, pinned to the covering-acceptance mass precondition and used as the bin-decoder radius) there is a derandomized index binning f making the bin-decoder confusion probability so small that distortionMax dα' · Pr[E2] ≤ δ/4. Combines the binning-averaged confusion exponent (wz_codebook_confusion_expectation_le, fed wz_covering_codeword_sideInfo_mass_le + collision wzIndexBinningMeasure_collision, instantiated over the positive-Y-marginal subtype β'), the binning derandomization, and the exponent squeeze (hε_conf : R₁ − I(Y;U) + 3·ε < R), with the source ↔ side-info-ambient identification.

    The full event {bin decoder fails to recover the true covering word} decomposes as E2 ⊆ E2b {some other bin member typical, confusion} ∪ C2 {true word not jointly typical, covering-acceptance failure}. Two hypotheses are therefore load-free preconditions, not the analytic core: the covering codebook size upper bound (M₁ : ℝ) ≤ exp(n·R₁) + 1 (the confusion count scales with the number of codewords, so the E2b squeeze needs M₁ capped near ⌈exp(n·R₁)⌉, the size the covering theorem actually produces), and the pinned covering-acceptance mass hcov_accept (a precondition-exposure of the covering code's own acceptance-mass property, discharged by the covering atom). The radius ε is pinned at a single explicit value; the huge-ε regime that makes wzCoveringAcceptFailSet vacuously empty is excluded by hε_conf (wzCoveringAcceptFailSet's mass is monotone decreasing in ε), and dα' is tied to d by hd'_link : ∀ x' g, dα' x' g = d x'.1 g (so distortionMax dα' ≤ distortionMax d).

    The body is sorry-free: it proves {decoder ≠ true word} ⊆ C2 ∪ E2b (wzBinTypicalDecoder_eq_of_unique contrapositive), bounds C2 by the pinned hcov_accept premise, chooses f by one derandomization (exists_le_integral over wzIndexBinningMeasure fed the confusion bound, whose per-codeword mass is wz_source_codeword_sideInfo_mass_le), and squeezes the confusion exponent to 0 (wz_tendsto_exp_mul_codebookSize_inv; the degenerate M₁ ≤ 1 covering has an empty confusion event, handled by Subsingleton (Fin M₁)), then scales by distortionMax dα' ≤ distortionMax d.

    Used by
      theorem

      InformationTheory.Shannon.wz_perN_covering_binning_code

      source
      {α : Type u_1} {β : Type u_2} {γ : Type u_3} [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] [Fintype γ] [DecidableEq γ] [Nonempty γ] [MeasurableSpace γ] [MeasurableSingletonClass γ] (P_XY : MeasureTheory.Measure (α × β)) [MeasureTheory.IsProbabilityMeasure P_XY] (d : DistortionFn α γ) (R D : ) (k : ) (qf : (α × β × Fin k) × (Fin k × βγ)) (δ : ) ( : 0 < δ) (q' : α × β × Fin k) (κ' : αFin k) (qStar : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k) (d' : DistortionFn { x : α // 0 < y : β, P_XY.real {(x, y)} } (Fin k)) (R₁ : ) (hfact_eq : ∀ (x : α) (y : β) (u : Fin k), q' (x, y, u) = κ' x u * P_XY.real {(x, y)}) (hκ'pos : ∀ (x : α) (u : Fin k), 0 < κ' x u) (hκ'sum : ∀ (x : α), u : Fin k, κ' x u = 1) (hobj' : wzMutualInfoXU (Fin k) q' - wzMutualInfoYU (Fin k) q' < R) (hqStar_eq : ∀ (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k), qStar p = κ' (↑p.1) p.2 * y : β, P_XY.real {(p.1, y)}) (hqStar_pos : ∀ (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k), 0 < qStar p) (hqStar_mem : qStar stdSimplex ({ x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k)) (hfeas : expectedDistortionPmf d' qStar D + δ / 2) (hd'_eq : ∀ (x' : { x : α // 0 < y : β, P_XY.real {(x, y)} }) (u : Fin k), d' x' u = (∑ y : β, (P_XY.real {(x', y)} / y' : β, P_XY.real {(x', y')}) * (d (↑x') (qf.2 (u, y)))).toNNReal) (hqf : qf WynerZivFactorizableConstraint (Fin k) (fun (p : α × β) => P_XY.real {p}) (fun (a : α) (b : γ) => (d a b)) D) (hsplit : R₁ - wzMutualInfoYU (Fin k) q' < R) (hcov₁ : ∀ (ε' : ), 0 < ε'∀ (ε : ), 0 < ε∃ (N : ), ∀ (n : ), N n∃ (M : ), Real.exp (n * R₁)⌉₊ M M Real.exp (n * R₁) + 1 ∃ (c : LossyCode M n { x : α // 0 < y : β, P_XY.real {(x, y)} } (Fin k)), c.expectedBlockDistortion (MeasureTheory.Measure.map (ChannelCoding.iidXs 0) (rdAmbient qStar)) d' D + δ / 2 + ε' (MeasureTheory.Measure.pi fun (x : Fin n) => ChannelCoding.pmfToMeasure fun (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × β) => P_XY.real {(p.1, p.2)}).real (wzCoveringAcceptFailSet P_XY κ' c ε) δ / 2 / (8 * (distortionMax d + 1))) :
      ∃ (N : ), ∀ (n : ), ∃ (c : WynerZivCode (codebookSize R n) n α β γ), N nc.expectedBlockDistortion P_XY d D + δ

      Per-n Wyner–Ziv code family at a fixed covering rate. Given the covering data together with an already-chosen covering rate R₁ (strictly above I(X;U), so that hcov₁ — the covering LossyCode family at rate R₁ — is available) and the net-rate gap hsplit : R₁ − I(Y;U) < R, assemble the per-n Wyner–Ziv code family at the operational rate R: bin the covering index down to codebookSize R n messages (wzIndexBinningMeasure), decode by the bin conditional-typicality search (wzCodeOfCoveringBinning / wzBinTypicalDecoder), bound the covering-failure (wz_covering_failure_prob_le, fed the mass lower bound via wz_covering_sideInfo_mass_ge) and the codebook-restricted decoder-confusion ( wz_codebook_confusion_expectation_le, fed the per-codeword mass upper bound via wz_covering_codeword_sideInfo_mass_le and the collision wzIndexBinningMeasure_collision) error events, extract a good deterministic codebook + binning by double derandomization, squeeze the residual distortion excess to 0, and extend the covering code α' → α (wzLiftSupportCode).

      No error-probability or decoder-correctness claim is a hypothesis: hcov₁ is the separately-established rate-distortion covering LossyCode family at covering rate R₁ (≈ I(X;U)), not the binned WynerZivCode at operational rate R; the index binning, the bin decoder, and the confusion exponent are the residual body work. The distortion budget is split so hfeas/hcov₁ target D + δ/2, reserving δ/2 for the finite-n error terms (mirrors the rate-distortion sister rate_distortion_achievability): the WZ distortion decomposes as a good-event proxy + distortionMax d · (P[E1]+P[E2]), so the reserved slack is absorbed by the error exponents (all → 0). Three preconditions are definitional/regularity, not load-bearing on the operational conclusion: hd'_eq pins the covering proxy d' to 𝔼_{Y|X}[d ∘ qf.2] (killing the d' := 0 counterexample, where the real WZ distortion under d ∘ qf.2 would be unconstrained), hqf supplies the test channel's WynerZivFactorizableConstraint membership (the Markov U-X-Y structure), and hcov₁ exposes the covering size bounds ⌈exp(n·R₁)⌉ ≤ M ≤ exp(n·R₁) + 1 (the E2 squeeze needs M capped above, the ceiling size the covering theorem actually produces). All are discharged by construction at wz_coveringFamily_of_testChannel. hobj'/hsplit/hfeas are objective/feasibility/rate preconditions; positivity and simplex membership are regularity.

      Used by