AFTD Auto-Formalizing Theoretical Domains

mutual_f_information_markov_sub_eq_sum_theta

theoremverified

For a full-support Markov chain Y → X → Z, Ĩ_f(X;YZ) - Ĩ_f(X;Z) = Σ_z p_Z(z) Θ_{p_X,p_{Y|X}}(p_{X|Z=z}) (eq. (13) of arXiv:2610.21231).

Statement

theorem mutual_f_information_markov_sub_eq_sum_theta {X Y Z : Type*} [Fintype X] [Fintype Y]
    [Fintype Z] (f : ℝ → ℝ) (pX : X → ℝ) (PY : X → Y → ℝ) (PZ : X → Z → ℝ)
    (hpX : ∀ x, 0 < pX x) (hsX : ∑ x, pX x = 1)
    (hPY : ∀ x y, 0 < PY x y) (hsY : ∀ x, ∑ y, PY x y = 1)
    (hPZ : ∀ x z, 0 < PZ x z) (hsZ : ∀ x, ∑ z, PZ x z = 1) :
    mutual_f_information f (fun x (yz : Y × Z) => pX x * PY x yz.1 * PZ x yz.2) -
        mutual_f_information f (fun x z => pX x * PZ x z) =
      ∑ z, (∑ x, pX x * PZ x z) *
        mutual_f_theta f pX PY (fun x => pX x * PZ x z / ∑ x', pX x' * PZ x' z)
Source
arXiv:2610.21231 (On the subadditivity of mutual f-information), Appendix B, proof of Theorem 1, eq. (13)
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • mutual_f_thetaThe function Θ_{p_X,p_{Y|X}}(r_X) of eq. (14)/(19) of arXiv:2610.21231: Σ_y r_Y(y) D_f(r_{X|y} ‖ p_X) - D_f(r_X ‖ p_X), with r_{YX} = r_X…
  • mutual_f_informationFor a joint probability mass function p_{XY} on finite sets, the mutual f-information is Ĩ_f(X; Y) = D_f(p_{XY} ‖ p_X p_Y) = Σ_{x,y}…
Used by 1

The proof, explained

The proof establishes the Markov chain decomposition identity for mutual f-information by expanding both sides into explicit sums and verifying that corresponding terms match. Using the column-stochasticity of the transition kernels P_{Y|X} and P_{Z|X}, the marginal distributions over X simplify to p_X. After unfolding the definitions of mutual f-information and the functional Θ, both sides decompose into a difference A - B. By congruence, the equality reduces to two independent subgoals: matching the triple sums over (x, y, z) and matching the double sums over (x, z). In both cases, the result follows from elementary fraction cancellations and exchanging the order of summation.

  1. The type X is non-empty.

    If X were empty, the sum ∑ x, pX x would be an empty sum and equal 0. But by hypothesis hsX, this sum equals 1, giving a contradiction.

    lines 10–13

    uses not_nonempty_iff

      have hX : Nonempty X := by
        by_contra h
        rw [not_nonempty_iff] at h
        simp at hsX
  2. The marginal distributions of (X, Y, Z) and (X, Z) with respect to the first coordinate reduce to pX x.

    Unfolding the definitions of mutual f-information and Θ, we compute the marginal sums over (Y, Z) and over Z for a fixed x. Factoring out pX x, the remaining sums over Y and Z equal 1 by the stochasticity of the transition kernels PY and PZ. Substituting these row sums simplifies the X-marginals in the f-information definitions directly to pX x.

    lines 14–21

    uses Fintype.sum_prod_type, Finset.mul_sum, mul_one

      unfold mutual_f_information mutual_f_theta
      have rowYZ : ∀ x, ∑ yz : Y × Z, pX x * PY x yz.1 * PZ x yz.2 = pX x := by
        intro x
        rw [Fintype.sum_prod_type]
        simp only [← Finset.mul_sum, hsZ, mul_one, hsY]
      have rowZ : ∀ x, ∑ z, pX x * PZ x z = pX x := by
        intro x; rw [← Finset.mul_sum, hsZ, mul_one]
      simp only [rowYZ, rowZ]
  3. The marginal distributions pZ z := ∑ x, pX x * PZ x z and q y z := ∑ x, pX x * PY x y * PZ x z are strictly positive everywhere.

    Because all probabilities pX x, PY x y, and PZ x z are strictly positive and X is non-empty, the finite sums defining pZ z and q y z are non-empty sums of strictly positive numbers, hence strictly positive.

    lines 22–28

    uses Finset.sum_pos, mul_pos, Classical.arbitrary, Finset.mem_univ

      set pZ : Z → ℝ := fun z => ∑ x, pX x * PZ x z with hpZ
      set q : Y → Z → ℝ := fun y z => ∑ x, pX x * PY x y * PZ x z with hq
      have hpZpos : ∀ z, 0 < pZ z := fun z =>
        Finset.sum_pos (fun x _ => mul_pos (hpX x) (hPZ x z)) ⟨Classical.arbitrary X, Finset.mem_univ _⟩
      have hqpos : ∀ y z, 0 < q y z := fun y z =>
        Finset.sum_pos (fun x _ => mul_pos (mul_pos (hpX x) (hPY x y)) (hPZ x z))
          ⟨Classical.arbitrary X, Finset.mem_univ _⟩
  4. For all y and z, ∑ x, (pX x * PZ x z / pZ z) * PY x y = q y z / pZ z.

    Factoring the common denominator pZ z out of the sum yields (∑ x, pX x * PY x y * PZ x z) / pZ z, which matches q y z / pZ z by definition of q.

    lines 29–33

    uses Finset.sum_div, Finset.sum_congr

      have hA : ∀ y z, ∑ x, pX x * PZ x z / pZ z * PY x y = q y z / pZ z := by
        intro y z
        simp only [hq, Finset.sum_div]
        refine Finset.sum_congr rfl (fun x _ => ?_)
        ring
  5. The theorem's goal decomposes into an equality of differences between the (Y, Z)-related sums and the Z-related sums.

    We express both sides in terms of pZ and q. Substituting the identity from the previous step replaces the inner sum over X in the first term of the right-hand side with q y z / pZ z. Distributing the factor pZ z and the summation over z across the subtraction decomposes both sides into a difference of two sums, A₁ - B₁ = A₂ - B₂.

    lines 34–41

    uses mul_sub, Finset.sum_sub_distrib

      change ∑ x : X, ∑ yz : Y × Z, pX x * q yz.1 yz.2 *
            f (pX x * PY x yz.1 * PZ x yz.2 / (pX x * q yz.1 yz.2)) -
          ∑ x : X, ∑ z : Z, pX x * pZ z * f (pX x * PZ x z / (pX x * pZ z)) =
        ∑ z : Z, pZ z * (∑ y : Y, (∑ x : X, pX x * PZ x z / pZ z * PY x y) *
            ∑ x : X, pX x * f (pX x * PZ x z / pZ z * PY x y /
              (∑ x' : X, pX x' * PZ x' z / pZ z * PY x' y) / pX x) -
          ∑ x : X, pX x * f (pX x * PZ x z / pZ z / pX x))
      simp only [hA, mul_sub, Finset.sum_sub_distrib]
  6. It suffices to prove equality for the first terms (A₁ = A₂) and the second terms (B₁ = B₂) separately.

    By congruence for subtraction, the equation A₁ - B₁ = A₂ - B₂ follows directly from proving A₁ = A₂ and B₁ = B₂ independently.

    line 42

      congr 1
  7. The first terms are equal: the triple sum over (x, y, z) in Ĩ_f(X; YZ) equals the first sum in the expansion.

    First, the sum over the product type Y × Z is split into iterated sums over y and z. Next, a pointwise identity hT verifies that for each (x, y, z), the factor pZ z cancels with 1 / pZ z, and the argument of f simplifies using field arithmetic, justified by the positivity of pZ z, q y z, and pX x. Finally, reordering the summations via commutativity of finite sums aligns the left- and right-hand sides.

    lines 43–57

    uses Fintype.sum_prod_type, Finset.mul_sum, Finset.sum_comm, Finset.sum_congr

      · simp only [Fintype.sum_prod_type]
        have hT : ∀ x y z, pZ z * (q y z / pZ z * (pX x * f (pX x * PZ x z / pZ z * PY x y /
            (q y z / pZ z) / pX x))) = pX x * q y z * f (pX x * PY x y * PZ x z / (pX x * q y z)) := by
          intro x y z
          have h1 := (hpZpos z).ne'
          have h2 := (hqpos y z).ne'
          have h3 := (hpX x).ne'
          have harg : pX x * PZ x z / pZ z * PY x y / (q y z / pZ z) / pX x =
              pX x * PY x y * PZ x z / (pX x * q y z) := by
            field_simp
          rw [harg]
          field_simp
        simp only [Finset.mul_sum, hT]
        exact Finset.sum_comm.trans ((Finset.sum_congr rfl fun y _ => Finset.sum_comm).trans
          Finset.sum_comm)
  8. The second terms are equal: the double sum over (x, z) in Ĩ_f(X; Z) equals the second sum in the expansion.

    We exchange the summation order over x and z on the left-hand side, push the factor pZ z into the inner sum over x on the right-hand side, and rewrite the argument of f using (a / b) / c = a / (c * b) = a / (b * c).

    lines 58–64

    uses Finset.sum_comm, Finset.sum_congr, Finset.mul_sum, div_div, mul_comm

      · rw [Finset.sum_comm]
        refine Finset.sum_congr rfl (fun z _ => ?_)
        rw [Finset.mul_sum]
        refine Finset.sum_congr rfl (fun x _ => ?_)
        have hd : pX x * PZ x z / pZ z / pX x = pX x * PZ x z / (pX x * pZ z) := by
          rw [div_div, mul_comm (pZ z)]
        rw [hd]; ring
not_nonempty_iff
A type is not non-empty if and only if it is empty: ¬Nonempty α ↔ IsEmpty α.
Fintype.sum_prod_type
A sum over a product type equals the iterated sum over each component: ∑ x : α × β, f x = ∑ a, ∑ b, f (a, b).
Finset.mul_sum
Multiplication distributes over a finite sum: a * ∑ i, f i = ∑ i, a * f i.
mul_one
Multiplying by 1 leaves any element unchanged: a * 1 = a.
Finset.sum_pos
A finite sum of strictly positive terms over a non-empty set is strictly positive.
mul_pos
The product of two strictly positive real numbers is strictly positive: 0 < a → 0 < b → 0 < a * b.
Classical.arbitrary
Produces an arbitrary element of an inhabited type.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.sum_div
Division distributes over a finite sum: (∑ i, f i) / a = ∑ i, f i / a.
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their summands agree on every element.
mul_sub
Multiplication distributes over subtraction: a * (b - c) = a * b - a * c.
Finset.sum_sub_distrib
A sum of differences equals the difference of the two sums: ∑ i, (f i - g i) = ∑ i, f i - ∑ i, g i.
Finset.sum_comm
The order of summation in a finite double sum can be exchanged: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
div_div
Iterated division satisfies (a / b) / c = a / (b * c).
mul_comm
Multiplication is commutative: a * b = b * a.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem mutual_f_information_markov_sub_eq_sum_theta {X Y Z : Type*} [Fintype X] [Fintype Y]    [Fintype Z] (f : ℝ → ℝ) (pX : X → ℝ) (PY : X → Y → ℝ) (PZ : X → Z → ℝ)    (hpX : ∀ x, 0 < pX x) (hsX : ∑ x, pX x = 1)    (hPY : ∀ x y, 0 < PY x y) (hsY : ∀ x, ∑ y, PY x y = 1)    (hPZ : ∀ x z, 0 < PZ x z) (hsZ : ∀ x, ∑ z, PZ x z = 1) :    mutual_f_information f (fun x (yz : Y × Z) => pX x * PY x yz.1 * PZ x yz.2) -        mutual_f_information f (fun x z => pX x * PZ x z) =      ∑ z, (∑ x, pX x * PZ x z) *        mutual_f_theta f pX PY (fun x => pX x * PZ x z / ∑ x', pX x' * PZ x' z) := by  have hX : Nonempty X := by    by_contra h    rw [not_nonempty_iff] at h    simp at hsX  unfold mutual_f_information mutual_f_theta  have rowYZ : ∀ x, ∑ yz : Y × Z, pX x * PY x yz.1 * PZ x yz.2 = pX x := by    intro x    rw [Fintype.sum_prod_type]    simp only [← Finset.mul_sum, hsZ, mul_one, hsY]  have rowZ : ∀ x, ∑ z, pX x * PZ x z = pX x := by    intro x; rw [← Finset.mul_sum, hsZ, mul_one]  simp only [rowYZ, rowZ]  set pZ : Z → ℝ := fun z => ∑ x, pX x * PZ x z with hpZ  set q : Y → Z → ℝ := fun y z => ∑ x, pX x * PY x y * PZ x z with hq  have hpZpos : ∀ z, 0 < pZ z := fun z =>    Finset.sum_pos (fun x _ => mul_pos (hpX x) (hPZ x z)) ⟨Classical.arbitrary X, Finset.mem_univ _⟩  have hqpos : ∀ y z, 0 < q y z := fun y z =>    Finset.sum_pos (fun x _ => mul_pos (mul_pos (hpX x) (hPY x y)) (hPZ x z))      ⟨Classical.arbitrary X, Finset.mem_univ _⟩  have hA : ∀ y z, ∑ x, pX x * PZ x z / pZ z * PY x y = q y z / pZ z := by    intro y z    simp only [hq, Finset.sum_div]    refine Finset.sum_congr rfl (fun x _ => ?_)    ring  change ∑ x : X, ∑ yz : Y × Z, pX x * q yz.1 yz.2 *        f (pX x * PY x yz.1 * PZ x yz.2 / (pX x * q yz.1 yz.2)) -      ∑ x : X, ∑ z : Z, pX x * pZ z * f (pX x * PZ x z / (pX x * pZ z)) =    ∑ z : Z, pZ z * (∑ y : Y, (∑ x : X, pX x * PZ x z / pZ z * PY x y) *        ∑ x : X, pX x * f (pX x * PZ x z / pZ z * PY x y /          (∑ x' : X, pX x' * PZ x' z / pZ z * PY x' y) / pX x) -      ∑ x : X, pX x * f (pX x * PZ x z / pZ z / pX x))  simp only [hA, mul_sub, Finset.sum_sub_distrib]  congr 1  · simp only [Fintype.sum_prod_type]    have hT : ∀ x y z, pZ z * (q y z / pZ z * (pX x * f (pX x * PZ x z / pZ z * PY x y /        (q y z / pZ z) / pX x))) = pX x * q y z * f (pX x * PY x y * PZ x z / (pX x * q y z)) := by      intro x y z      have h1 := (hpZpos z).ne'      have h2 := (hqpos y z).ne'      have h3 := (hpX x).ne'      have harg : pX x * PZ x z / pZ z * PY x y / (q y z / pZ z) / pX x =          pX x * PY x y * PZ x z / (pX x * q y z) := by        field_simp      rw [harg]      field_simp    simp only [Finset.mul_sum, hT]    exact Finset.sum_comm.trans ((Finset.sum_congr rfl fun y _ => Finset.sum_comm).trans      Finset.sum_comm)  · rw [Finset.sum_comm]    refine Finset.sum_congr rfl (fun z _ => ?_)    rw [Finset.mul_sum]    refine Finset.sum_congr rfl (fun x _ => ?_)    have hd : pX x * PZ x z / pZ z / pX x = pX x * PZ x z / (pX x * pZ z) := by      rw [div_div, mul_comm (pZ z)]    rw [hd]; ring
See it in the graphDiscuss this resultChallenge it