InformationTheory

InformationTheory.Shannon.CramerBoundaryUpstream

source

Cramér boundary-closure upstream module #

The IsMeasureInfinitePiTiltedEq predicate together with the change-of-measure and tilted-LLN-window theorems behind the Cramér lower bound: the cylinder lift from the infinite product to Measure.pi (Fin n), the finite-level density-bound change-of-measure inequality, and the interior-case window-mass concentration.

Main definitions #

  • IsMeasureInfinitePiTiltedEq μ₀ Y lam — the n-letter change-of-measure predicate identifying the tilted infinite product with the cylinder tilt of the un-tilted product.
  • IsTiltedWindowEventuallyLarge μ₀ Y lam — the tilted infinite-product window mass is eventually ≥ 1/2.

Main statements #

n-letter RN-deriv identification predicate (hoisted) #

def

InformationTheory.Shannon.Cramer.TiltedLLN.IsMeasureInfinitePiTiltedEq

source
{Ω₀ : Type u_1} [MeasurableSpace Ω₀] (μ₀ : MeasureTheory.Measure Ω₀) (Y : Ω₀) (lam : ) :

The Cramér n-letter change-of-measure predicate.

Captures the cylinder-n compatibility between Measure.infinitePi (fun _ => μ₀.tilted (lam * Y ·)) and (Measure.infinitePi μ₀).tilted (∑ lam * Y ∘ eval i), in the form usable as input to Cramér's lower-bound change-of-measure step.

The intended interpretation: for every n and every measurable event E ⊆ {ω | a·n ≤ ∑ i ∈ Finset.range n, Y (ω i)}, the un-tilted product measure of E admits the Chernoff-style lower bound exp(-n · (lam · a − Λ(lam))) · μ_tilt(E) − o(1) ≤ μ.real E, where μ_tilt := Measure.infinitePi (fun _ => μ₀.tilted (lam * Y ·)) and Λ := cgf Y μ₀. This is the textbook density identity (dμ_tilt / dμ)|_{cylinder n} = exp(lam · ∑ Y(ω_i) − n·Λ(lam)).

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

      Cylinder lift (hoisted) #

      theorem

      InformationTheory.Shannon.Cramer.TiltedLLN.infinitePi_partialSum_event_eq_pi

      source
      {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {ν : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure ν] {Y : Ω₀} (hY : Measurable Y) (n : ) (P : Prop) (hP : MeasurableSet {r : | P r}) :
      (MeasureTheory.Measure.infinitePi fun (x : ) => ν) {ω : Ω₀ | P (∑ iFinset.range n, Y (ω i))} = (MeasureTheory.Measure.pi fun (x : Fin n) => ν) {x : Fin nΩ₀ | P (∑ i : Fin n, Y (x i))}

      The cylinder lift: an event over the first n coordinates of the infinite product, expressed via a predicate on the partial sum, has infinitePi mass equal to the corresponding Measure.pi (Fin n) mass. Works for any constant factor ν (apply with ν = μ₀ and ν = μ₀.tilted ...).

      Used by

        Finite change-of-measure lower bound (hoisted) #

        theorem

        InformationTheory.Shannon.Cramer.TiltedLLN.change_of_measure_lower_bound_pi

        source
        {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {n : } {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (a ε lam : ) (hlam : 0 lam) :
        ENNReal.ofReal (Real.exp (-n * (lam * a - ProbabilityTheory.cgf Y μ₀ lam + lam * ε))) * (MeasureTheory.Measure.pi fun (x : Fin n) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω) {x : Fin nΩ₀ | a * n i : Fin n, Y (x i) i : Fin n, Y (x i) < (a + ε) * n} (MeasureTheory.Measure.pi fun (x : Fin n) => μ₀) {x : Fin nΩ₀ | a * n i : Fin n, Y (x i)}

        The finite change-of-measure lower bound (Measure.pi level).

        For lam ≥ 0, on the window W_n := {x | a·n ≤ ∑ Y(x i) < (a+ε)·n} the un-tilted product mass of the half-line event E_n := {x | a·n ≤ ∑ Y(x i)} is bounded below by exp(-n·(lam·a − Λ + lam·ε)) times the tilted product mass of W_n, where Λ = cgf Y μ₀ lam. The density d(pi μ₀)/d(pi μ_tilt) is exp(−lam·∑Y + n·Λ), bounded below on W_n by exp(−lam(a+ε)n + nΛ).

        @audit:ok (genuine density-bound proof)

        Used by

          Residual predicate + reduction to IsMeasureInfinitePiTiltedEq (hoisted) #

          def

          InformationTheory.Shannon.Cramer.TiltedLLN.IsTiltedWindowEventuallyLarge

          source
          {Ω₀ : Type u_1} [MeasurableSpace Ω₀] (μ₀ : MeasureTheory.Measure Ω₀) (Y : Ω₀) (lam : ) :

          The residual predicate: the tilted infinite-product window mass is eventually at least 1/2. It holds precisely when the tilted mean ∫ Y ∂μ₀.tilted lies in the window [a, a+ε), which is the Cramér optimality condition ∫ Y ∂μ₀.tilted = a.

          See also tilted_lln_in_probability_real.

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

              InformationTheory.Shannon.Cramer.TiltedLLN.isMeasureInfinitePiTiltedEq_of_tiltedWindowLarge

              source
              {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (lam : ) (hlam : 0 lam) (h_res : IsTiltedWindowEventuallyLarge μ₀ Y lam) :

              The residual reduction: the residual window predicate implies the full n-letter RN-deriv predicate IsMeasureInfinitePiTiltedEq.

              @audit:ok (h_res is genuinely consumed (filter_upwards [h_res a ε hε]) to supply the window-mass input, not a vacuous bundle.)

              Used by

                Per-instance window largeness from interior of the tilted mean (hoisted) #

                theorem

                InformationTheory.Shannon.Cramer.TiltedLLN.tiltedWindow_eventually_tendsto_one

                source
                {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (lam : ) {a ε : } (h_lo : a < (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) (h_hi : ( (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) < a + ε) :
                Filter.Tendsto (fun (n : ) => (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω).real {ω : Ω₀ | a * n iFinset.range n, Y (ω i) iFinset.range n, Y (ω i) < (a + ε) * n}) Filter.atTop (nhds 1)

                The per-instance tilted window mass tends to 1 (interior case).

                The ∀a∀ε predicate IsTiltedWindowEventuallyLarge is false in general (for a far from the tilted mean the window has vanishing mass). The meaningful statement is the per-instance one: when the tilted mean m := ∫ Y ∂(μ₀.tilted (lam·Y)) lies strictly inside the window (a, a+ε), the tilted infinite-product mass of {ω | a·n ≤ ∑_{i<n} Y(ω i) < (a+ε)·n} tends to 1.

                Used by
                  theorem

                  InformationTheory.Shannon.Cramer.TiltedLLN.tiltedWindow_eventually_large_of_interior

                  source
                  {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (lam : ) {a ε : } (h_lo : a < (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) (h_hi : ( (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) < a + ε) :
                  ∀ᶠ (n : ) in Filter.atTop, 1 / 2 (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω).real {ω : Ω₀ | a * n iFinset.range n, Y (ω i) iFinset.range n, Y (ω i) < (a + ε) * n}

                  The per-instance tilted window mass is eventually ≥ 1/2 (interior case). This is the per-instance replacement for the (generally false) ∀a∀ε IsTiltedWindowEventuallyLarge predicate.

                  See also tiltedWindow_eventually_tendsto_one.

                  Used by

                    cgf-calculus form of the interior window condition (hoisted) #

                    theorem

                    InformationTheory.Shannon.Cramer.TiltedLLN.tiltedMean_eq_deriv_cgf

                    source
                    {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (lam : ) :
                    ( (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) = deriv (ProbabilityTheory.cgf Y μ₀) lam

                    The tilted mean equals the cgf derivative (cgf-derivative bridge).

                    For a bounded measurable Y under a probability measure μ₀, the tilted mean ∫ Y ∂(μ₀.tilted (lam·Y)) equals the first derivative of the cgf at lam: ∫ ω, Y ω ∂(μ₀.tilted (fun ω => lam * Y ω)) = deriv (cgf Y μ₀) lam.

                    The interior side condition lam ∈ interior (integrableExpSet Y μ₀) holds because boundedness of Y makes exp (t·Y) integrable for every t, so integrableExpSet Y μ₀ = Set.univ and its interior is again Set.univ.

                    @audit:ok

                    Used by