InformationTheory

InformationTheory.Probability.TwoSidedExtension.Core

source

Shifted finite-dimensional marginals #

noncomputable def

InformationTheory.Shannon.TwoSided.shiftAmount

source
(J : Finset ) :

The minimal non-negative integer N that makes every element of J non-negative after shifting by N. For empty J we return 0.

Equations
Instances For
    Used by
      theorem

      InformationTheory.Shannon.TwoSided.zero_le_shiftAmount_add

      source
      (J : Finset ) {j : } (hj : j J) :
      0 j + (shiftAmount J)

      For any sufficient shift N, every j ∈ J satisfies 0 ≤ j + N.

      Used by
        noncomputable def

        InformationTheory.Shannon.TwoSided.obsZ

        source
        {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) (N : ) (J : Finset ) :
        ΩJα

        The joint observation at -indexed times, parametrized by a shift N: obsZ μ p N J ω j := X (T^[(j + N).toNat] ω). When N ≥ shiftAmount J, this records the genuine block (X_{j₀+N}, X_{j₁+N}, …) evaluated at the points of J.

        Equations
        Instances For
          Used by
            theorem

            InformationTheory.Shannon.TwoSided.measurable_obsZ

            source
            {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) (N : ) (J : Finset ) :
            Measurable (obsZ μ p N J)

            The joint observation obsZ μ p N J is measurable.

            Used by
              noncomputable def

              InformationTheory.Shannon.TwoSided.shiftedMarginal

              source
              {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) (J : Finset ) :
              MeasureTheory.Measure (Jα)

              The finite-dimensional marginal of the (yet-to-be-built) two-sided extension at the index set J : Finset. Defined as the law of obsZ at the canonical shift shiftAmount J; the value is independent of the chosen shift by stationarity (shiftedMarginal_eq_of_shift).

              Equations
              Instances For
                Used by
                  theorem

                  InformationTheory.Shannon.TwoSided.obsZ_succ_shift

                  source
                  {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) {J : Finset } (N k : ) (hN : jJ, 0 j + N) :
                  obsZ μ p (N + k) J = obsZ μ p N J p.T^[k]

                  For two non-negative shifts N₁ ≤ N₂ both valid for J, the joint observation under N₂ is the same as under N₁ precomposed with T^[N₂ - N₁].

                  Used by
                    theorem

                    InformationTheory.Shannon.TwoSided.map_obsZ_succ

                    source
                    {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) {J : Finset } (N k : ) (hN : jJ, 0 j + N) :

                    N-invariance of obsZ under push-forward (stationarity, single-shift step). For any valid shift N, pushing forward by obsZ μ p (N + k) J agrees with pushing forward by obsZ μ p N J.

                    Used by
                      theorem

                      InformationTheory.Shannon.TwoSided.map_obsZ_eq_of_shift

                      source
                      {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) {J : Finset } (N₁ N₂ : ) (h₁ : jJ, 0 j + N₁) (h₂ : jJ, 0 j + N₂) :

                      N-invariance of the pushforward law (general form): any two valid shifts yield the same pushforward measure.

                      Used by
                        theorem

                        InformationTheory.Shannon.TwoSided.shiftedMarginal_eq_of_shift

                        source
                        {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) (J : Finset ) (N : ) (hN : jJ, 0 j + N) :

                        The shifted marginal coincides with the pushforward of obsZ for any valid shift, not just the canonical shiftAmount J.

                        Used by
                          instance

                          InformationTheory.Shannon.TwoSided.instIsProbabilityMeasure_shiftedMarginal

                          source

                          Each shifted marginal is a probability measure (pushforward of a probability measure under a measurable map).

                          Used by
                            theorem

                            InformationTheory.Shannon.TwoSided.isProjectiveMeasureFamily_shiftedMarginal

                            source

                            Projective consistency: for J ⊆ I, restricting shiftedMarginal μ p I along the inclusion gives shiftedMarginal μ p J.

                            Used by

                              Projective consistency + σ-additivity #

                              noncomputable def

                              InformationTheory.Shannon.TwoSided.stationaryContent

                              source

                              The AddContent on measurable cylinders of ℤ → α induced by the shifted finite-dimensional marginals.

                              Equations
                              Instances For
                                Used by
                                  theorem

                                  InformationTheory.Shannon.TwoSided.stationaryContent_tendsto_zero

                                  source
                                  {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [Fintype α] [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) {A : Set (α)} (A_mem : ∀ (n : ), A n MeasureTheory.measurableCylinders fun (x : ) => α) (A_anti : Antitone A) (A_inter : ⋂ (n : ), A n = ) :
                                  Filter.Tendsto (fun (n : ) => (stationaryContent μ p) (A n)) Filter.atTop (nhds 0)

                                  σ-additivity input: for any antitone sequence of measurable cylinders with empty intersection, the content tends to 0.

                                  The proof uses the finite-type Cantor argument: equipping α with the discrete topology turns ℤ → α into a compact Hausdorff space (Pi.compactSpace from finite discrete factors), every cylinder cylinder I S is closed (preimage of a finite, hence closed, set), and every closed subset of a compact space is compact. Cantor's intersection theorem for sequences (IsCompact.nonempty_iInter_of_sequence_…) then gives ∃ N, A N = ∅, after which stationaryContent (A n) = 0 for n ≥ N.

                                  Used by
                                    theorem

                                    InformationTheory.Shannon.TwoSided.stationaryContent_isSigmaSubadditive

                                    source

                                    stationaryContent is σ-subadditive (from tendsto_zero).

                                    Used by

                                      Carathéodory extension μZ #

                                      noncomputable def

                                      InformationTheory.Shannon.TwoSided.μZ

                                      source

                                      The two-sided extension μ_ℤ : Measure (ℤ → α) obtained from the stationary process (Ω, T, μ, X) by Carathéodory extension of the stationaryContent.

                                      Equations
                                      Instances For
                                        Used by
                                          theorem

                                          InformationTheory.Shannon.TwoSided.μZ_cylinder

                                          source
                                          {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [Fintype α] [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) [MeasureTheory.IsProbabilityMeasure μ] (p : StationaryProcess μ α) {I : Finset } {S : Set (Iα)} (hS : MeasurableSet S) :

                                          On measurable cylinders, μZ agrees with shiftedMarginal.

                                          Used by
                                            theorem

                                            InformationTheory.Shannon.TwoSided.isProjectiveLimit_μZ

                                            source

                                            μZ is the projective limit of the shifted marginals.

                                            Used by
                                              instance

                                              InformationTheory.Shannon.TwoSided.instIsProbabilityMeasure_μZ

                                              source

                                              μZ is a probability measure.

                                              Used by

                                                Shift MeasurePreserving + Ergodic #

                                                def

                                                InformationTheory.Shannon.TwoSided.shiftZ

                                                source
                                                {α : Type u_2} :
                                                (α)α

                                                The two-sided shift σ : (ℤ → α) → (ℤ → α), σ x i := x (i + 1).

                                                Equations
                                                Instances For
                                                  Used by
                                                    def

                                                    InformationTheory.Shannon.TwoSided.shiftZSymm

                                                    source
                                                    {α : Type u_2} :
                                                    (α)α

                                                    The inverse shift, σ⁻¹ x i := x (i - 1).

                                                    Equations
                                                    Instances For
                                                      Used by
                                                        theorem

                                                        InformationTheory.Shannon.TwoSided.measurable_shiftZ

                                                        source

                                                        The shift is measurable.

                                                        Used by
                                                          theorem

                                                          InformationTheory.Shannon.TwoSided.measurable_shiftZSymm

                                                          source

                                                          The inverse shift is measurable.

                                                          Used by
                                                            theorem

                                                            InformationTheory.Shannon.TwoSided.measurePreserving_shiftZ

                                                            source

                                                            The two-sided shift preserves μZ.

                                                            Proof outline: both μZ μ p and (μZ μ p).map shiftZ are projective limits of the family shiftedMarginal μ p of finite-dimensional marginals. By IsProjectiveLimit.unique they are equal. The projective property of the pushforward reduces to the shift-invariance of the marginals: for any I : Finset, the marginal at I + 1 (relabeled through the bijection · + 1) equals the marginal at I, which is exactly shiftedMarginal_eq_of_shift.

                                                            Used by
                                                              theorem

                                                              InformationTheory.Shannon.TwoSided.leftInverse_shiftZSymm

                                                              source

                                                              shiftZSymm is the left-inverse of shiftZ.

                                                              Used by
                                                                theorem

                                                                InformationTheory.Shannon.TwoSided.rightInverse_shiftZSymm

                                                                source

                                                                shiftZSymm is the right-inverse of shiftZ.

                                                                Used by

                                                                  Coupling with the one-sided side #

                                                                  def

                                                                  InformationTheory.Shannon.TwoSided.forwardEmbed

                                                                  source
                                                                  {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) :
                                                                  Ωα

                                                                  The forward (one-sided) embedding Ω → (ℕ → α), ω ↦ (X (T^[i] ω))_i.

                                                                  Equations
                                                                  Instances For
                                                                    Used by
                                                                      theorem

                                                                      InformationTheory.Shannon.TwoSided.measurable_forwardEmbed

                                                                      source
                                                                      {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) (p : StationaryProcess μ α) :

                                                                      The forward embedding is measurable.

                                                                      Used by
                                                                        theorem

                                                                        InformationTheory.Shannon.TwoSided.μZ_nat_proj_eq

                                                                        source
                                                                        {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [Fintype α] [MeasurableSpace α] (μ : MeasureTheory.Measure Ω) [MeasureTheory.IsProbabilityMeasure μ] (p : StationaryProcess μ α) :
                                                                        MeasureTheory.Measure.map (fun (x : α) (i : ) => x i) (μZ μ p) = MeasureTheory.Measure.map (forwardEmbed μ p) μ

                                                                        The ℕ-projection of μZ agrees with the law of forwardEmbed.

                                                                        Both sides are probability measures on ℕ → α. We verify equality on the π-system of measurable cylinders using MeasureTheory.ext_of_generate_finite, then compute each cylinder's measure: on the LHS via μZ_cylinder after rewriting the preimage as a ℤ-cylinder, and on the RHS via the definition of forwardEmbed together with shiftedMarginal_eq_of_shift at shift 0.

                                                                        Used by
                                                                          theorem

                                                                          InformationTheory.Shannon.TwoSided.μZ_block_cylinder_eq

                                                                          source
                                                                          {Ω : Type u_1} [MeasurableSpace Ω] {α : Type u_2} [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] (μ : MeasureTheory.Measure Ω) [MeasureTheory.IsProbabilityMeasure μ] (p : StationaryProcess μ α) (n : ) (s : Fin nα) :
                                                                          (μZ μ p) {x : α | ∀ (i : Fin n), x i = s i} = (MeasureTheory.Measure.map (p.blockRV n) μ) {s}

                                                                          Block cylinder under μZ equals the block-law on the one-sided side.

                                                                          Used by

                                                                            ergodic_shiftZ #

                                                                            Two-sided shift ergodicity via cylinder approximation + ℕ-factor transfer.

                                                                            For a shiftZ-invariant measurable set A ⊆ (ℤ → α):

                                                                            1. Approximate A by a finite cylinder t (over some F ⊆ ℤ) up to ε in symmetric difference — via MeasureTheory.exists_measure_symmDiff_lt_of_generateFrom_isSetRing on measurableCylinders (a set ring generating the product σ-algebra).
                                                                            2. For k large enough that F + k ⊆ ℕ, the shifted cylinder shiftZ^[k]⁻¹' t is a cylinder over a nonnegative index set, hence lies in cylinderEvents {i : ℤ | 0 ≤ i}.
                                                                            3. By measure-preservation of shiftZ^[k] and shift-invariance of A, μZ(A Δ shiftZ^[k]⁻¹' t) = μZ(A Δ t) < ε, so A is approximable to within any ε by sets in cylinderEvents {i : ℤ | 0 ≤ i}.
                                                                            4. Hence A is μZ-a.e. equal to some A' = natProj⁻¹' B for measurable B, and B is shiftN-invariant mod-null on μ.map forwardEmbed.
                                                                            5. (ℕ → α, shiftN, μ.map forwardEmbed) is ergodic (forward ergodic_of_ergodic_semiconj from (Ω, T, μ) via forwardEmbed).
                                                                            6. Conclude μZ(A) = μN(B) ∈ {0, 1}.
                                                                            def

                                                                            InformationTheory.Shannon.TwoSided.shiftN

                                                                            source
                                                                            {α : Type u_2} :
                                                                            (α)α

                                                                            The one-sided (-indexed) shift σ_ℕ : (ℕ → α) → (ℕ → α), σ_ℕ y i := y (i+1).

                                                                            Equations
                                                                            Instances For
                                                                              Used by
                                                                                theorem

                                                                                InformationTheory.Shannon.TwoSided.measurable_shiftN

                                                                                source

                                                                                The forward shift on ℕ → α is measurable.

                                                                                Used by
                                                                                  theorem

                                                                                  InformationTheory.Shannon.TwoSided.forwardEmbed_semiconj

                                                                                  source

                                                                                  The forward embedding semiconjugates T and shiftN.

                                                                                  Used by
                                                                                    def

                                                                                    InformationTheory.Shannon.TwoSided.natProj

                                                                                    source
                                                                                    {α : Type u_2} :
                                                                                    (α)α

                                                                                    The ℕ-projection natProj : (ℤ → α) → (ℕ → α), natProj x i := x (i : ℤ).

                                                                                    Equations
                                                                                    Instances For
                                                                                      Used by
                                                                                        theorem

                                                                                        InformationTheory.Shannon.TwoSided.measurable_natProj

                                                                                        source

                                                                                        natProj is measurable.

                                                                                        Used by
                                                                                          theorem

                                                                                          InformationTheory.Shannon.TwoSided.natProj_semiconj

                                                                                          source

                                                                                          natProj semiconjugates shiftZ and shiftN.

                                                                                          Used by
                                                                                            theorem

                                                                                            InformationTheory.Shannon.TwoSided.measurePreserving_natProj

                                                                                            source

                                                                                            natProj is measure-preserving from μZ to μ.map forwardEmbed.

                                                                                            Used by
                                                                                              theorem

                                                                                              InformationTheory.Shannon.TwoSided.measurePreserving_forwardEmbed

                                                                                              source

                                                                                              forwardEmbed is measure-preserving from μ to its pushforward.

                                                                                              Used by
                                                                                                theorem

                                                                                                InformationTheory.Shannon.TwoSided.ergodic_shiftN

                                                                                                source

                                                                                                The forward shift on (ℕ → α, μ.map forwardEmbed) is ergodic when the underlying process is ergodic. Direct application of ergodic_of_ergodic_semiconj with forwardEmbed as the measure-preserving semiconjugacy from (Ω, T, μ).

                                                                                                Used by
                                                                                                  theorem

                                                                                                  InformationTheory.Shannon.TwoSided.shiftZ_iterate_apply

                                                                                                  source
                                                                                                  {α : Type u_2} (k : ) (x : α) (i : ) :
                                                                                                  shiftZ^[k] x i = x (i + k)

                                                                                                  shiftZ iterated k times: shiftZ^[k] x i = x (i + k).

                                                                                                  Used by
                                                                                                    theorem

                                                                                                    InformationTheory.Shannon.TwoSided.shiftZ_iterate_preimage_cylinder

                                                                                                    source
                                                                                                    {α : Type u_2} [MeasurableSpace α] (k : ) (F : Finset ) {S : Set (Fα)} (hS : MeasurableSet S) :
                                                                                                    ∃ (S' : Set ((Finset.image (fun (j : ) => j + k) F)α)), MeasurableSet S' shiftZ^[k] ⁻¹' MeasureTheory.cylinder F S = MeasureTheory.cylinder (Finset.image (fun (j : ) => j + k) F) S'

                                                                                                    Preimage of a measurable cylinder over F under shiftZ^[k] is a measurable cylinder over F + k = F.image (· + k).

                                                                                                    Used by
                                                                                                      theorem

                                                                                                      InformationTheory.Shannon.TwoSided.shiftZ_iterate_preimage_mem_measurableCylinders

                                                                                                      source
                                                                                                      {α : Type u_2} [MeasurableSpace α] (k : ) {t : Set (α)} (ht : t MeasureTheory.measurableCylinders fun (x : ) => α) :

                                                                                                      Preimage under shiftZ^[k] preserves measurable cylinders: the preimage of a measurableCylinders element is again in measurableCylinders.

                                                                                                      Used by
                                                                                                        theorem

                                                                                                        InformationTheory.Shannon.TwoSided.shiftZ_iterate_preimage_cylinder_in_pos

                                                                                                        source
                                                                                                        {α : Type u_2} [MeasurableSpace α] {F : Finset } {S : Set (Fα)} (hS : MeasurableSet S) {k : } (hk : jF, 0 j + k) :

                                                                                                        After shifting by k ≥ -F.min (when F is nonempty), the cylinder lies in cylinderEvents {i : ℤ | 0 ≤ i} (the positive-index σ-algebra). The witness index set is F.image (· + k), all of whose elements are ≥ 0.

                                                                                                        Used by
                                                                                                          def

                                                                                                          InformationTheory.Shannon.TwoSided.posSigma

                                                                                                          source
                                                                                                          @[reducible]
                                                                                                          {α : Type u_2} [MeasurableSpace α] :

                                                                                                          The positive-index σ-algebra on ℤ → α, i.e., the σ-algebra of events depending only on coordinates i ≥ 0.

                                                                                                          Equations
                                                                                                          Instances For
                                                                                                            Used by
                                                                                                              theorem

                                                                                                              InformationTheory.Shannon.TwoSided.posSigma_le_pi

                                                                                                              source

                                                                                                              posSigma ≤ pi.

                                                                                                              Used by
                                                                                                                theorem

                                                                                                                InformationTheory.Shannon.TwoSided.measurable_natProj_posSigma

                                                                                                                source

                                                                                                                natProj is measurable from posSigma to pi on ℕ → α.

                                                                                                                Used by
                                                                                                                  theorem

                                                                                                                  InformationTheory.Shannon.TwoSided.exists_preimage_natProj_of_posSigma

                                                                                                                  source
                                                                                                                  {α : Type u_2} [MeasurableSpace α] {A : Set (α)} (hA : MeasurableSet A) :
                                                                                                                  ∃ (B : Set (α)), MeasurableSet B A = natProj ⁻¹' B

                                                                                                                  A posSigma-measurable set is the natProj-preimage of a measurable set in ℕ → α. This is the factoring lemma: positive-index events factor through natProj.

                                                                                                                  Used by
                                                                                                                    theorem

                                                                                                                    InformationTheory.Shannon.TwoSided.ergodic_shiftZ

                                                                                                                    source

                                                                                                                    The two-sided shift is ergodic when the underlying process is ergodic.

                                                                                                                    By cylinder approximation + ℕ-factor transfer. For any shiftZ-invariant measurable set A, approximate A to within ε by a measurable cylinder, then shift to move the index set into the nonnegative half-line. This yields a posSigma-measurable approximation, so A is μZ-a.e. equal to a posSigma-measurable set A' = natProj⁻¹ B. By ergodicity of shiftN on μ.map forwardEmbed, B is either null or co-null, hence so is A.

                                                                                                                    Used by