Skip to main content
teorth/PFR
Source indexedlemma · leanprover/lean4:v4.33.0-rc1

multiDist_chainRule

PFR.MoreRuzsaDist · PFR/MoreRuzsaDist.lean:1784 to 1845

Source documentation

Let π : G → H be a homomorphism of abelian groups and let X_[m] be a tuple of jointly independent G-valued random variables. Then D[X_[m]] is equal to D[X_[m] | π(X_[m])] + D[π(X_[m])] + I[∑ i, X_i : π(X_[m]) ; | ; π(∑ i, X_i)] where π(X_[m]) := (π(X_1), ..., π(X_m)).

Exact Lean statement

lemma multiDist_chainRule {G H : Type*} [hG : MeasurableSpace G] [MeasurableSingletonClass G]
    [AddCommGroup G] [Finite G] [hH : MeasurableSpace H]
    [MeasurableSingletonClass H] [AddCommGroup H]
    [Fintype H] (π : G →+ H) {m : ℕ} {Ω : Type*} (hΩ : MeasureSpace Ω)
    {X : Fin m → Ω → G} (hmes : ∀ i, Measurable (X i))
    (h_indep : iIndepFun X) :
    D[X; fun _ ↦ hΩ] = D[X | fun i ↦ π ∘ X i; fun _ ↦ hΩ]
      + D[fun i ↦ π ∘ X i; fun _ ↦ hΩ]
      + I[∑ i, X i : fun ω ↦ (fun i ↦ π (X i ω)) | π ∘ (∑ i, X i)]

Complete declaration

Lean source

Canonical source
Full Lean sourceLean 4
lemma multiDist_chainRule {G H : Type*} [hG : MeasurableSpace G] [MeasurableSingletonClass G]    [AddCommGroup G] [Finite G] [hH : MeasurableSpace H]    [MeasurableSingletonClass H] [AddCommGroup H]    [Fintype H] (π : G →+ H) {m : } {Ω : Type*} (hΩ : MeasureSpace Ω)    {X : Fin m  Ω  G} (hmes :  i, Measurable (X i))    (h_indep : iIndepFun X) :    D[X; fun _  hΩ] = D[X | fun i  π ∘ X i; fun _  hΩ]      + D[fun i  π ∘ X i; fun _  hΩ]      + I[∑ i, X i : fun ω  (fun i  π (X i ω)) | π ∘ (∑ i, X i)] := by  have : IsProbabilityMeasure (ℙ : Measure Ω) := h_indep.isProbabilityMeasure  set S := ∑ i, X i  set piX := fun ω  (fun i  π (X i ω))  set avg_HX := (∑ i, H[X i]) / m  set avg_HpiX := (∑ i, H[π ∘ X i])/m  set avg_HXpiX := (∑ i, H[X i | π ∘ X i])/m  have hSmes : Measurable S := by fun_prop  have hpiXmes : Measurable piX := by    rw [measurable_pi_iff]    intro i    exact Measurable.comp .of_discrete (hmes i)  have eq1 : I[S : piX | π ∘ S] = H[S | π ∘ S] + H[piX | π ∘ S] - H[S, piX | π ∘ S] := by    rw [condMutualInfo_eq hSmes hpiXmes (Measurable.comp .of_discrete hSmes)]  have eq1a : H[S | π ∘ S] = H[S] - H[π ∘ S] :=    condEntropy_comp_self hSmes .of_discrete  have eq1b : H[piX | π ∘ S] = H[piX] - H[π ∘ S] := by    set g := fun (y : Fin m  H)  ∑ i, y i    have : π ∘ S = g ∘ piX := by      ext x      simp only [comp_apply, Finset.sum_apply, _root_.map_sum, S, g, piX]    rw [this]    exact condEntropy_comp_self hpiXmes .of_discrete  have eq1c : H[S, piX | π ∘ S] = H[S, piX] - H[π ∘ S] := by    set g := fun (x : G × (Fin m  H))  π x.1    have : π ∘ S = g ∘ S, piX := by      ext x      simp only [comp_apply, Finset.sum_apply, _root_.map_sum, S, g, piX]    rw [this]    apply condEntropy_comp_self (Measurable.prodMk hSmes hpiXmes) .of_discrete  have eq2 : H[S, piX] = H[piX] + H[S | piX] := chain_rule _ hSmes hpiXmes  have eq3 : D[X; fun _  hΩ] = H[S] - avg_HX := multiDist_indep _ hmes h_indep  have eq4 : D[X | fun i  π ∘ X i; fun _  hΩ] = H[S | piX] - avg_HXpiX := by    dsimp [S, piX]    convert! condMultiDist_eq (S := H) hmes _ _    · exact Fintype.sum_apply _ _    · intro i      exact Measurable.comp .of_discrete (hmes i)    set g : G  G × H := fun x  x, π x    change iIndepFun (fun i  g ∘ X i) ℙ    exact h_indep.comp _ fun _  .of_discrete  have eq5 : D[fun i  π ∘ X i; fun _  hΩ] = H[π ∘ S] - avg_HpiX := by    convert multiDist_indep _ (X := fun i  π ∘ X i) (by fun_prop) _    · ext _      simp only [comp_apply, Finset.sum_apply, _root_.map_sum, S]    apply iIndepFun.comp h_indep    exact fun _  .of_discrete  have eq6 : avg_HX = avg_HpiX + avg_HXpiX := by    dsimp [avg_HX, avg_HpiX, avg_HXpiX]    rw [ add_div,  Finset.sum_add_distrib]    congr with i    rw [condEntropy_comp_self (hmes i) .of_discrete]    abel  linarith only [eq1, eq1a, eq1b, eq1c, eq2, eq3, eq4, eq5, eq6]