mutual_f_information_markov_sub_eq_sum_theta
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
- mutual_f_information_subadditive_full_support_of_weight_boundTheorem 1 of arXiv:2610.21231, on full-support distributions. Let f with f(1) = 0 be convex and four times continuously differentiable on…
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.
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.
uses
not_nonempty_iffhave hX : Nonempty X := by by_contra h rw [not_nonempty_iff] at h simp at hsX
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.
uses
Fintype.sum_prod_type,Finset.mul_sum,mul_oneunfold 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]
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.
uses
Finset.sum_pos,mul_pos,Classical.arbitrary,Finset.mem_univset 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 _⟩
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.
uses
Finset.sum_div,Finset.sum_congrhave 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
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₂.
uses
mul_sub,Finset.sum_sub_distribchange ∑ 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]
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.
congr 1The 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.
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)
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).
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.
- The proof establishes that $X$ is non-empty (`Nonempty X`) as an initial step; this is needed to ensure that the finite sums defining $p_Z(z)$ and $q(y, z)$ are non-empty and therefore strictly positive, justifying the division and field simplifications.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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