InformationTheory

InformationTheory.Shannon.WynerZiv.Achievability.Concentration

source

Wyner–Ziv achievability — inner concentration sub-lemmas for the Markov-lemma covering bound #

Inner concentration — band sub-lemmas #

The Markov-lemma concentration wz_covering_markov_concentration is assembled from six band sub-lemmas. The covering-acceptance failure event unfolds — via mem_jointlyTypicalSet_iff — into a conjunction of three independent entropy-band typicalities (U-band ∧ Y-band ∧ joint-band), so its De Morgan complement is a union of three band-failures, each with an independent witness:

  • wz_covering_uMarginal_map_eq — the covering pmf qStar's U-marginal equals the side-information marginal wzSideInfoMarginal's U-marginal (both = P_U); this makes the U-band consistent between the two ambients.
  • wz_covering_success_subset_uTypical — covering-success ⊆ {chosen word U-typical in the side-information ambient}; the covering U-band plus the marginal identity makes U-typicality identical in the two ambients (mass-0 set inclusion, no threshold N).
  • wz_covering_src_yProj_eq_pi — the Y-projection of the source product measure is the product of the source Y-law (Measure.pi_map_pi).
  • wz_covering_yBand_aep — the source-measure Y-band failure has mass ≤ tol/4 for n large (a one-dimensional AEP on the iid side-information sequence, independent of the code).
  • wz_covering_jointBand_concentration — the hard kernel: covering-success ∩ {joint (U,Y)-band failure} has mass ≤ tol/4. The correlated-joint conditional-typicality concentration (the Markov lemma); U = c.decoder (c.encoder x) is a function of the whole x-block, so (U_i, Y_i) is neither iid nor independent — a from-scratch in-project assembly absent from Mathlib.
  • the assembly (the body of wz_covering_markov_concentration): N := max N_Y N_J, and a union bound over the three band-failures gives 0 + tol/4 + tol/4 = tol/2.
theorem

InformationTheory.Shannon.wz_covering_success_subset_uTypical

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] {k : } (κ' : αFin k) (qStar : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k) (hκ'_pos : ∀ (x : α) (u : Fin k), 0 < κ' x u) (hκ'_sum : ∀ (x : α), u : Fin k, κ' x u = 1) (hqStar : ∀ (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k), qStar p = κ' (↑p.1) p.2 * y : β, P_XY.real {(p.1, y)}) (ε : ) (n M : ) (c : LossyCode M n { x : α // 0 < y : β, P_XY.real {(x, y)} } (Fin k)) :
{p : Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} } × β | (fun (j : Fin n) => (p j).1, c.decoder (c.encoder fun (j : Fin n) => (p j).1)) ChannelCoding.jointlyTypicalSet (rdAmbient qStar) ChannelCoding.iidXs ChannelCoding.iidYs n ε} {p : Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} } × β | c.decoder (c.encoder fun (j : Fin n) => (p j).1) typicalSet (rdAmbient (wzSideInfoMarginal P_XY κ')) ChannelCoding.iidXs n ε}

If the chosen covering word c.decoder (c.encoder x) typically covers x (covering-success in rdAmbient qStar), then it is U-typical in the side-information ambient. The covering-success U-band bands the word against qStar's U-marginal; L0 makes that identical to the side-information ambient's U-marginal, so the two U-typical sets coincide. Pure set inclusion (no threshold N).

Used by
    theorem

    InformationTheory.Shannon.wz_covering_yBand_aep

    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] {k : } (κ' : αFin k) (hκ'_pos : ∀ (x : α) (u : Fin k), 0 < κ' x u) (hκ'_sum : ∀ (x : α), u : Fin k, κ' x u = 1) (ε : ) ( : 0 < ε) (tol : ) (htol : 0 < tol) :
    ∃ (N : ), ∀ (n : ), N n(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)} } × β | (fun (i : Fin n) => (p i).2)typicalSet (rdAmbient (wzSideInfoMarginal P_XY κ')) (fun (i : ) (ω : Fin k × { y : β // 0 < x : α, P_XY.real {(x, y)} }) => (ChannelCoding.iidYs i ω)) n ε} tol / 4

    For n large the source-measure mass of the Y-band failure — the side-information block y is not typical in the side-information ambient — is at most tol/4. A one-dimensional AEP on the iid Y-sequence (law P_Y = ∑ₓ P_XY{(x, ·)}), independent of the code c and of covering-success. Transports typicalSet_prob_ge_of_rate (the ℕ-process AEP) onto the source product measure via the β'β coercion, mirroring the wz_source_codeword_sideInfo_mass_le transport.

    Used by
      theorem

      InformationTheory.Shannon.wz_covering_xyBand_aep

      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] (ε : ) ( : 0 < ε) (tol : ) (htol : 0 < tol) :
      ∃ (N : ), ∀ (n : ), N n(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 (typicalSet (rdAmbient fun (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × β) => P_XY.real {(p.1, p.2)}) (ChannelCoding.jointSequence ChannelCoding.iidXs ChannelCoding.iidYs) n ε) tol / 8

      For n large the source-measure mass of the (X,Y)-joint-atypical set — the block (x_i,y_i) = p_i is not typical in the (X,Y)-joint ambient rdAmbient Src (Src(x',y) = P_XY{(x'.1,y)}, the SRC per-coordinate law) — is at most tol/8. The (x_i,y_i) pairs are iid ~ Src under SRC, so this is a direct AEP (typicalSet_prob_ge_of_rate) transported by rdAmbient_map_jointRV_jointSequence_eq_pi. Independent of the code c.

      Used by
        theorem

        InformationTheory.Shannon.wz_srcBlock_condMeasure_split

        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] {n : } (S : Set (Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} } × β)) :
        (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 S = xb : Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} }, (∏ i : Fin n, y : β, P_XY.real {((xb i), y)}) * (MeasureTheory.Measure.pi fun (i : Fin n) => ChannelCoding.pmfToMeasure fun (y : β) => P_XY.real {((xb i), y)} / y' : β, P_XY.real {((xb i), y')}).real {yb : Fin nβ | (fun (i : Fin n) => (xb i, yb i)) S}

        The source-block measure SRC = Measure.pi (fun _ ↦ pmfToMeasure Src) with Src (x, y) = P_XY{(x, y)} disintegrates over the x-block: for any block event S, SRC.real S = ∑_{xb} (∏_i P_X(xb_i)) · condY(xb).real (xb-slice of S), where P_X(x) = ∑_y P_XY{(x, y)} (positive on the x-alphabet subtype) and the conditional y-block measure condY(xb) = Measure.pi (fun i ↦ pmfToMeasure (P(·|xb_i))) uses the normalized per-coordinate law P(y|x) = P_XY{(x, y)} / P_X(x), hence a genuine probability measure — the form the conditional-Chebyshev step consumes. This avoids general condDistrib on Measure.pi (a Mathlib 0-hit); it is elementary finite Fubini via pmfToMeasure atomicity and Measure.pi_pi, with no AEP.

        Used by
          theorem

          InformationTheory.Shannon.wz_covering_strongTypical_indep_mass_ge

          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] {k : } [Nonempty (Fin k)] [Nonempty { x : α // 0 < y : β, P_XY.real {(x, y)} }] (qStar : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k) (hpos : ∀ (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k), 0 < qStar p) (hmem : qStar stdSimplex ({ x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k)) {ε δ η : } ( : 0 < ε) ( : 0 < δ) ( : 0 < η) :

          The independent-product mass of the strong joint-typical set under the covering ambient rdAmbient qStar — the probability that an independently drawn covering word U^n is strongly jointly typical with the source block X^n at radius ε — is bounded below by the standard random-coding exponent (1 − η)·exp(n·((H(Z) − H(X) − H(Y)) − slack)). This is the WZ instantiation of jointStronglyTypicalSet_indep_prob_ge, discharging its independence / ident-distribution / full-support / marginal-matching premises from the ambient-regularity lemmas of rdAmbient qStar (full support of qStar gives hposX/Y/Z). It is the covering-success lower bound feeding the joint (distortion + covering-success) derandomize of wz_coveringFamily_of_testChannel.

          Used by
            noncomputable def

            InformationTheory.Shannon.wzCoveringStrongRadius

            source
            {α : Type u_1} {β : Type u_2} [Fintype α] [MeasurableSpace α] [Fintype β] [MeasurableSpace β] (P_XY : MeasureTheory.Measure (α × β)) {k : } (κ' : αFin k) (ε : ) :

            The radius ε_cov = ε / (2·(1 + C)) at which the covering word is required to be strongly (x, U)-typical, where C = ∑_{x,u} |g(x, u)| is the mean-pin amplification constant of wz_wsm_negLog_mean_pin_of_stronglyTypical (g = wzCondMeanKernel). The mean-pin bounds |M(xb) − H(wsm)| by C · (strong radius), so to keep the conditional-mean statistic within ε/2 of H(wsm) — the slack the correlated Markov core needs to absorb the acceptance-band radius ε — the strong covering radius must be ≤ ε/(2C). Using ε/(2·(1 + C)) makes the choice unconditional (C ≥ 0) and keeps ε_cov > 0. This is a computed term of ε, κ', P_XY (NOT a new lemma parameter), so the chain signatures stay fixed. Strong typicality at the same radius ε would only pin M within C·ε ≫ ε, leaving an O(ε) partial-relabel counterexample class open (a scaled-down label swap); the smaller radius closes that class.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              Used by
                theorem

                InformationTheory.Shannon.wzCoveringStrongRadius_pos

                source
                {α : Type u_1} {β : Type u_2} [Fintype α] [DecidableEq α] [Nonempty α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β] [DecidableEq β] [Nonempty β] [MeasurableSpace β] [MeasurableSingletonClass β] (P_XY : MeasureTheory.Measure (α × β)) {k : } (κ' : αFin k) {ε : } ( : 0 < ε) :

                The strong covering radius is positive for ε > 0 (the denominator 2·(1 + ∑|g|) is ≥ 2).

                Used by
                  def

                  InformationTheory.Shannon.wzCoveringSuccessStrong

                  source
                  {α : Type u_1} {β : Type u_2} [Fintype α] [DecidableEq α] [MeasurableSpace α] [Fintype β] [MeasurableSpace β] (P_XY : MeasureTheory.Measure (α × β)) [MeasureTheory.IsProbabilityMeasure P_XY] {k : } (κ' : αFin k) (qStar : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k) {n M : } (c : LossyCode M n { x : α // 0 < y : β, P_XY.real {(x, y)} } (Fin k)) (ε : ) :
                  Set (Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} } × β)

                  The covering-success event for the strong-Ecov Wyner–Ziv covering chain: the chosen covering word c.decoder (c.encoder x) is jointly typical with the source x in the covering ambient rdAmbient qStar, in BOTH readings.

                  • The strong reading (jointStronglyTypicalSet) is a per-symbol type pin at the smaller radius wzCoveringStrongRadius P_XY κ' ε = ε/(2(1 + C)); it is the strengthening that makes the correlated Markov core wz_covering_jointBand_markov_core true-as-framed, by pinning the conditional-mean statistic M(xb) to within C · ε_cov < ε/2 of H(wzSideInfoMarginal) through wz_wsm_negLog_mean_pin_of_stronglyTypical. This kills not only the full entropy-preserving label-swap counterexample but the whole O(ε) partial-relabel class that strong typicality at the same radius ε would leave open (there |M − H| ≤ C·ε ≫ ε).
                  • The weak reading (jointlyTypicalSet) is an entropy band at radius ε; it is retained so that the acceptance-band U-typicality plumbing wz_covering_success_subset_uTypical — which needs the weak U-band at radius ε — goes through unchanged.

                  Strong typicality at radius ε_cov does not imply the weak U-band at radius ε (the strong-to-weak bridge widens the radius by ε_cov·logSumAbs, an unrelated constant), so the covering-success event is the intersection of the two readings. This keeps every lemma signature in the chain fixed (the radii are computed terms of ε) while making the correlated Markov concentration true-as-framed.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    Used by
                      theorem

                      InformationTheory.Shannon.wzCoveringSuccessStrong_subset_weak

                      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] {k : } (κ' : αFin k) (qStar : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k) {n M : } (c : LossyCode M n { x : α // 0 < y : β, P_XY.real {(x, y)} } (Fin k)) (ε : ) :
                      wzCoveringSuccessStrong P_XY κ' qStar c ε {p : Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} } × β | (fun (j : Fin n) => (p j).1, c.decoder (c.encoder fun (j : Fin n) => (p j).1)) ChannelCoding.jointlyTypicalSet (rdAmbient qStar) ChannelCoding.iidXs ChannelCoding.iidYs n ε}

                      Strong covering-success implies weak covering-success (the second conjunct, at radius ε), the reading the U-typicality plumbing consumes.

                      Used by
                        theorem

                        InformationTheory.Shannon.wz_covering_uyBand_condSlice_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] {k : } (κ' : αFin k) (qStar : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k) (hκ'_pos : ∀ (x : α) (u : Fin k), 0 < κ' x u) (hκ'_sum : ∀ (x : α), u : Fin k, κ' x u = 1) (hqStar : ∀ (p : { x : α // 0 < y : β, P_XY.real {(x, y)} } × Fin k), qStar p = κ' (↑p.1) p.2 * y : β, P_XY.real {(p.1, y)}) (ε : ) ( : 0 < ε) (tol : ) (htol : 0 < tol) :
                        ∃ (N : ), ∀ (n : ), N n∀ (M : ) (c : LossyCode M n { x : α // 0 < y : β, P_XY.real {(x, y)} } (Fin k)) (xb : Fin n{ x : α // 0 < y : β, P_XY.real {(x, y)} }), (fun (i : Fin n) => (xb i, c.decoder (c.encoder xb) i)) stronglyTypicalSet (rdAmbient qStar) (ChannelCoding.jointSequence ChannelCoding.iidXs ChannelCoding.iidYs) n (wzCoveringStrongRadius P_XY κ' ε)(MeasureTheory.Measure.pi fun (i : Fin n) => ChannelCoding.pmfToMeasure fun (y : β) => P_XY.real {((xb i), y)} / y' : β, P_XY.real {((xb i), y')}).real {yb : Fin nβ | (fun (i : Fin n) => (c.decoder (c.encoder xb) i, yb i))typicalSet (rdAmbient (wzSideInfoMarginal P_XY κ')) (ChannelCoding.jointSequence ChannelCoding.iidXs fun (i : ) (ω : Fin k × { y : β // 0 < x : α, P_XY.real {(x, y)} }) => (ChannelCoding.iidYs i ω)) n ε} tol / 8

                        For a strong-covering x-block xb — one whose induced (x, U) block (xb i, c.decoder (c.encoder xb) i) is strongly typical for the covering ambient at the strong radius ε_cov = wzCoveringStrongRadius P_XY κ' ε — the conditional side-information measure of the (U, Y)-atypical slice is ≤ tol/8 for n ≥ N. This is the conditional AEP U — X — Y: the mean-pin (wz_wsm_negLog_mean_pin_of_stronglyTypical) puts the conditional mean of -log wsm(U_i, ·) within C·ε_cov < ε/2 of H(wsm), and the conditional Chebyshev (pi_nonuniform_concentration_tendsto, deviation ε/2) concentrates the empirical (U, Y)-entropy there, so (U, Y)-atypicality (radius ε) has vanishing conditional mass. This is the from-scratch conditional-AEP kernel; the surrounding finite-Fubini split, good/bad x-block dichotomy and summation are discharged in wz_covering_jointBand_markov_core.

                        Implementation notes. The hypothesis uses strong (not weak) typicality: strong typicality pins the per-symbol (x, u)-type in total variation, controlling the linear functional M = ⟨type, g⟩ that the conclusion needs — no finer structure required — whereas weak entropy-only typicality fails on an entropy-preserving label-swap counterexample class. The assembly mirrors the in-tree template wz_covering_yBand_aep: a uniform sup-bound B = ∑_q |log wsm(q)| on the per-coordinate log-statistic, its conditional mean identified with wzCondMeanKernel, and the ambient entropy ∑_q negMulLog(wsm q), combined through the radius-separated mean-pin (C·ε_cov < ε/2) and the Chebyshev engine (pi_nonuniform_concentration_tendsto, δ = ε/2) by a strict triangle inequality. The hκ'_pos/hκ'_sum/hqStar hypotheses are full-support / proper-pmf / qStarκ' consistency preconditions (used to place qStar ∈ stdSimplex and identify the conditional mean), not the concentration conclusion — not load-bearing; the proof is sorryAx-free.

                        @audit:ok

                        Used by