InformationTheory

InformationTheory.Shannon.CramerCltBoundaryClosure

source

Cramér / Chernoff CLT-boundary closure #

This file closes the boundary case a = m (= tilted mean = deriv (cgf Y μ₀) lam) of the residual window predicate IsTiltedWindowEventuallyLarge, the only piece left after the change-of-measure machinery is discharged. The interior case a < m < a + ε is handled by the existing two-sided LLN squeeze (tiltedWindow_eventually_large_of_interior); the boundary case requires a CLT refinement, supplied here.

Main statements #

Implementation notes #

At the boundary the window mass is supplied by the central limit theorem: the CLT tendstoInDistribution_inv_sqrt_mul_sum_sub applied to the tilted ambient, a portmanteau half-line bridge (frontier (Ici 0) = {0} is null under the non-degenerate Gaussian), and the scaling that identifies the window event with the S_n-preimage of Ici 0. The lower half-line mass tends to the Gaussian median 1/2 while the upper half-line at m + ε vanishes by the one-sided LLN, so the window mass tends to 1/2 ≥ 1/4. The sharp exponent is recovered by the ε → 0⁺ collapse of the per-ε boundary bounds.

theorem

InformationTheory.Shannon.CramerCltBoundary.gaussianReal_Ici_eq_half

source
{v : NNReal} (hv : v 0) :

The centered Gaussian 𝒩(0, v) (with v ≠ 0) assigns mass exactly 1/2 to the half-line {x | 0 ≤ x}.

@audit:ok (symmetry-by-map).

Used by

    CLT applied to the tilted ambient #

    theorem

    InformationTheory.Shannon.CramerCltBoundary.gaussianReal_hasLaw_id

    source

    The Gaussian self-law witness: the identity map on has law gaussianReal 0 w under gaussianReal 0 w.

    Used by
      theorem

      InformationTheory.Shannon.CramerCltBoundary.tilted_halfline_tendsto_gaussian

      source
      {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (lam : ) (hVar : 0 < ProbabilityTheory.variance (fun (ω : Ω₀) => Y (ω 0)) (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω)) :
      Filter.Tendsto (fun (n : ) => (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω) {ω : Ω₀ | ( (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) * n iFinset.range n, Y (ω i)}) Filter.atTop (nhds ((ProbabilityTheory.gaussianReal 0 (ProbabilityTheory.variance (fun (ω : Ω₀) => Y (ω 0)) (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω)).toNNReal) (Set.Ici 0)))

      The half-line mass tends to the Gaussian median. The tilted-ambient mass (ℝ≥0∞-valued) of the half-line {ω | m·n ≤ ∑_{i<n} Y(ω i)} (at the tilted mean m = ∫ Y ∂tilted) converges to the Gaussian mass gaussianReal 0 v.toNNReal (Ici 0).

      @audit:ok (CLT + portmanteau + scaling assembly).

      Used by

        Half-line mass tends to 1/2 #

        theorem

        InformationTheory.Shannon.CramerCltBoundary.tilted_halfline_tendsto_half

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

        The half-line mass tends to 1/2: the tilted-ambient .real-mass of {ω | m·n ≤ ∑_{i<n} Y(ω i)} tends to 1/2.

        Used by

          Window mass eventually ≥ 1/4 at the boundary #

          theorem

          InformationTheory.Shannon.CramerCltBoundary.tiltedWindow_eventually_large_of_boundary

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

          Boundary window largeness. At the boundary a = m (= tilted mean), the tilted infinite-product window mass {ω | m·n ≤ ∑Y < (m+ε)·n} is eventually ≥ 1/4.

          @audit:ok (CLT + LLN assembly; hVar : 0 < Var is the non-degeneracy precondition required by the Gaussian median gaussianReal_Ici_eq_half (v=0 degeneracy is correctly excluded by spec).

          Used by

            Relaxed window predicate + boundary discharge #

            theorem

            InformationTheory.Shannon.CramerCltBoundary.tilted_window_lower_to_halfline

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

            A per-instance change-of-measure half-line lower bound. At a single threshold a and ε > 0, eventual largeness C ≤ tilted-window mass lifts to the un-tilted half-line lower bound C·exp(-n(λa - Λ + λε)) ≤ P{a·n ≤ ∑Y}.

            @audit:ok (change-of-measure lift via change_of_measure_lower_bound_pi (real density bound, not vacuous) + cylinder lift; no C=0/exp=0 vacuity — at the call site C = 1/4 > 0, exp(...) > 0 always).

            Used by

              Cramér end-to-end lower bound at the interior optimal tilt #

              theorem

              InformationTheory.Shannon.CramerCltBoundary.boundary_liminf_lower_of_eps

              source
              {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (lam : ) (hlam : 0 lam) (hVar : 0 < ProbabilityTheory.variance (fun (ω : Ω₀) => Y (ω 0)) (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω)) {ε : } ( : 0 < ε) (h_coboundedBelow : Filter.IsCoboundedUnder (fun (x1 x2 : ) => x1 x2) Filter.atTop fun (n : ) => 1 / n * Real.log ((MeasureTheory.Measure.infinitePi fun (x : ) => μ₀).real {ω : Ω₀ | ( (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) * n iFinset.range n, Y (ω i)})) :
              -((lam * (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) - ProbabilityTheory.cgf Y μ₀ lam + lam * ε) Filter.liminf (fun (n : ) => 1 / n * Real.log ((MeasureTheory.Measure.infinitePi fun (x : ) => μ₀).real {ω : Ω₀ | ( (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) * n iFinset.range n, Y (ω i)})) Filter.atTop

              A per-ε boundary liminf lower bound. At the boundary a = m (= tilted mean ∫ Y ∂tilted), for each ε > 0, -(λm - Λ + λε) ≤ liminf (1/n)·log P{m·n ≤ ∑Y}.

              @audit:ok (no degenerate-log exploit — hP_pos : 0 < P{...} is derived from the window lower bound (1/4)·exp(...) ≤ P{...}, so log is taken of a strictly positive real; h_coboundedBelow is the genuine liminf_le_liminf side-condition, not load-bearing).

              Used by
                theorem

                InformationTheory.Shannon.CramerCltBoundary.cramer_lower_boundary_at_tilted_mean

                source
                {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (lam : ) (hlam : 0 lam) (hVar : 0 < ProbabilityTheory.variance (fun (ω : Ω₀) => Y (ω 0)) (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω)) (h_coboundedBelow : Filter.IsCoboundedUnder (fun (x1 x2 : ) => x1 x2) Filter.atTop fun (n : ) => 1 / n * Real.log ((MeasureTheory.Measure.infinitePi fun (x : ) => μ₀).real {ω : Ω₀ | ( (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) * n iFinset.range n, Y (ω i)})) :
                -((lam * (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) - ProbabilityTheory.cgf Y μ₀ lam) Filter.liminf (fun (n : ) => 1 / n * Real.log ((MeasureTheory.Measure.infinitePi fun (x : ) => μ₀).real {ω : Ω₀ | ( (ω : Ω₀), Y ω μ₀.tilted fun (ω : Ω₀) => lam * Y ω) * n iFinset.range n, Y (ω i)})) Filter.atTop

                Cramér's theorem (lower bound, boundary closure). At the interior optimal tilt a = m = ∫ Y ∂tilted (= deriv (cgf Y μ₀) lam, the boundary of the residual window), the asymptotic upper-tail rate is bounded below by the per-lam Chernoff exponent -(λm - Λ). The residual largeness hypothesis is removed — the boundary window mass is supplied internally by the CLT. Only the regularity preconditions remain: boundedness, non-degeneracy 0 < Var, and the cobounded hypothesis on the rate sequence (a precondition shared with cramer_lower).

                @audit:ok (ε→0⁺ collapse via le_of_forall_sub_le; the CLT supplies the boundary window mass internally — no residual largeness hypothesis).

                Used by
                  theorem

                  InformationTheory.Shannon.CramerCltBoundary.cramer_lower_boundary

                  source
                  {Ω₀ : Type u_1} [MeasurableSpace Ω₀] {μ₀ : MeasureTheory.Measure Ω₀} [MeasureTheory.IsProbabilityMeasure μ₀] {Y : Ω₀} (hY : Measurable Y) (h_bdd : ∃ (M : ), ∀ (ω : Ω₀), |Y ω| M) (a lam : ) (hlam : 0 lam) (h_deriv : deriv (ProbabilityTheory.cgf (fun (ω : Ω₀) => Y (ω 0)) (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀)) lam = a) (hVar : 0 < ProbabilityTheory.variance (fun (ω : Ω₀) => Y (ω 0)) (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀.tilted fun (ω : Ω₀) => lam * Y ω)) (h_coboundedBelow : Filter.IsCoboundedUnder (fun (x1 x2 : ) => x1 x2) Filter.atTop fun (n : ) => 1 / n * Real.log ((MeasureTheory.Measure.infinitePi fun (x : ) => μ₀).real {ω : Ω₀ | a * n iFinset.range n, Y (ω i)})) :
                  -(lam * a - ProbabilityTheory.cgf (fun (ω : Ω₀) => Y (ω 0)) (MeasureTheory.Measure.infinitePi fun (x : ) => μ₀) lam) Filter.liminf (fun (n : ) => 1 / n * Real.log ((MeasureTheory.Measure.infinitePi fun (x : ) => μ₀).real {ω : Ω₀ | a * n iFinset.range n, Y (ω i)})) Filter.atTop

                  Cramér's theorem (lower bound, boundary closure, consumer form). The infinitePi-side restatement of cramer_lower_boundary_at_tilted_mean with the cgf written on the coordinate-eval family Y ∘ eval 0 under the un-tilted product, at the optimal tilt a = deriv (cgf (Y∘eval 0) (infinitePi μ₀)) lam. The optimal-tilt hypothesis h_deriv pins a = m = ∫ Y ∂tilted, so the residual largeness hypothesis is removed: the boundary window mass is supplied internally by the CLT.

                  See also cramer_lower_boundary_at_tilted_mean.

                  @audit:ok (h_deriv/hVar/h_coboundedBelow are all preconditions, not load-bearing — h_deriv pins a = m (the true-as-framed constraint), hVar is the non-degeneracy precondition, h_coboundedBelow is the standard liminf_le_liminf side-condition (satisfiable: rate terms ≤ 0 since P ≤ 1, not vacuous); matches consumer root cramer_lower_infinitePi signature verbatim).

                  Used by