mutual_f_information_subadditive_full_support_of_weight_bound
Theorem 1 of arXiv:2610.21231, on full-support distributions. Let f with f(1) = 0 be convex and four times continuously differentiable on (0, ∞), and g(x) = x² f''(x). If g''(x) < 0 for all x > 0 and there are constants η > 0 and ℓ with g(x) + 2(g'(x) - η)²/(-g''(x)) ≤ 2η + (x - 1)ℓ for all x > 0, then Ĩ_f(X; YZ) ≤ Ĩ_f(X; Y) + Ĩ_f(X; Z) for every full-support Markov chain Y → X → Z on finite sets.
Statement
theorem mutual_f_information_subadditive_full_support_of_weight_bound (f : ℝ → ℝ)
(hf1 : f 1 = 0) (hconv : ConvexOn ℝ (Set.Ioi 0) f)
(hsmooth : ContDiffOn ℝ 4 f (Set.Ioi 0))
(hg2 : ∀ x > 0, deriv (deriv (subadditive_f_weight f)) x < 0)
(hbound : ∃ η ℓ : ℝ, 0 < η ∧ ∀ x > 0,
subadditive_f_weight f x + 2 * (deriv (subadditive_f_weight f) x - η) ^ 2 /
(-deriv (deriv (subadditive_f_weight f)) x) ≤ 2 * η + (x - 1) * ℓ) :
mutual_f_information_subadditive_full_support f- Formalizes
- arXiv:2610.21231 (On the subadditivity of mutual f-information), Theorem 1. Differs: the conclusion is for full-support distributions (the case the proof in Appendix B reduces to), and f is only constrained on (0, ∞) (the paper also asks continuity of f on [0, ∞), which full-support distributions never use).
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- subadditive_f_weightThe weight g(x) = x² f''(x) attached to a generator f in Theorem 1 of arXiv:2610.21231 (f'' is the iterated derivative
deriv (deriv f)). - mutual_f_information_subadditive_full_supportSubadditivity of mutual f-information on full-support distributions: for all finite X, Y, Z, every p_X > 0 and channels p_{Y|X} > 0,…
- 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_theta_concaveOn_of_weight_boundLemma 4 of arXiv:2610.21231: under the assumptions of Theorem 1 (g = x² f'' with g'' < 0 and g + 2(g' - η)²/(-g'') ≤ 2η + (x-1)ℓ), for…
- 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}…
- mutual_f_theta_selfΘ_{p_X,p_{Y|X}}(p_X) = Ĩ_f(X;Y) when f(1) = 0 (step (17)-(18) of the proof of Theorem 1 of arXiv:2610.21231).
- mutual_f_information_markov_sub_eq_sum_thetaFor 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).
- subadditive_f_weightThe weight g(x) = x² f''(x) attached to a generator f in Theorem 1 of arXiv:2610.21231 (f'' is the iterated derivative
- Used by 1
- subadditive_mutual_f_information_family_full_supportCorollary 1 of arXiv:2610.21231, on full-support distributions: let s be twice continuously differentiable, positive and concave on (0, ∞)…
The proof, explained
The proof establishes the subadditivity of mutual $f$-information along the Markov chain $Y \to X \to Z$ by rewriting it as $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z) \le \tilde{I}_f(X; Y)$. A conditioning identity decomposes the difference into an expectation over $z$ of an auxiliary functional $\theta_f$ evaluated at the posterior distributions $r_z$. Under the differential inequality hypothesis on $f$, $\theta_f$ is concave, so Jensen's inequality bounds this average above by $\theta_f$ at the mixture $\sum_z p_Z(z) r_z = p_X$, which is precisely $\tilde{I}_f(X; Y)$.
Decompose the difference $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z)$ as the average of the functional $\theta_f$ over posterior distributions, and establish that $\theta_f$ is concave.
We introduce the finite sets $X, Y, Z$, the prior distribution $p_X$, and the transition kernels $P_Y, P_Z$, all assumed strictly positive and normalized. Lemma `mutual_f_information_markov_sub_eq_sum_theta` writes $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z)$ as $\sum_z p_Z(z) \theta_f(r_z)$, where $p_Z(z) = \sum_x p_X(x) P_Z(x, z)$ and $r_z(x) = p_X(x) P_Z(x, z) / p_Z(z)$. Under the differential weight bound on $f$, lemma `mutual_f_theta_concaveOn_of_weight_bound` shows that $\theta_f$ is concave on the simplex of strictly positive distributions on $X$.
uses
mutual_f_information_markov_sub_eq_sum_theta,mutual_f_theta_concaveOn_of_weight_boundintro X Y Z _ _ _ pX PY PZ hpX hsX hPY hsY hPZ hsZ have hdec := mutual_f_information_markov_sub_eq_sum_theta f pX PY PZ hpX hsX hPY hsY hPZ hsZ have hcc := mutual_f_theta_concaveOn_of_weight_bound f hf1 hconv hsmooth hg2 hbound pX PY hpX hsX hPY hsY
The set $X$ is nonempty. automation
Suppose, for contradiction, that $X$ were empty (`not_nonempty_iff`). Then the sum $\sum_{x \in X} p_X(x)$ would be empty and therefore equal to $0$, contradicting the assumption $\sum_x p_X(x) = 1$. Simplification closes the resulting contradiction $0 = 1$.
uses
not_nonempty_iffhave hX : Nonempty X := by by_contra h rw [not_nonempty_iff] at h simp at hsX
The marginal distribution $p_Z(z) = \sum_x p_X(x) P_Z(x, z)$ is strictly positive for every $z$ and sums to $1$.
Each term $p_X(x) P_Z(x, z)$ is strictly positive by `mul_pos`, and since $X$ is nonempty, the sum defining $p_Z(z)$ is strictly positive by `Finset.sum_pos`. Swapping the order of summation (`Finset.sum_comm`) and using $\sum_z P_Z(x, z) = 1$ and $\sum_x p_X(x) = 1$ via `Finset.mul_sum` and `mul_one` shows that $\sum_z p_Z(z) = 1$.
uses
Finset.sum_pos,mul_pos,Classical.arbitrary,Finset.mem_univ,Finset.sum_comm,Finset.mul_sum,mul_oneset pZ : Z → ℝ := fun z => ∑ x, pX x * PZ x z with hpZ 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 hsZ1 : ∑ z, pZ z = 1 := by simp only [hpZ] rw [Finset.sum_comm] simp only [← Finset.mul_sum, hsZ, mul_one, hsX]
For every $z \in Z$, the posterior distribution $r_z(x) = p_X(x) P_Z(x, z) / p_Z(z)$ is strictly positive and sums to $1$ over $x$.
For each $z$, $r_z(x) > 0$ for all $x$ because both the numerator and denominator are positive (`div_pos`, `mul_pos`). Factoring out the denominator with `Finset.sum_div`, the sum $\sum_x r_z(x)$ evaluates to $(\sum_x p_X(x) P_Z(x, z)) / p_Z(z) = p_Z(z) / p_Z(z) = 1$ by `div_self`.
uses
div_pos,mul_pos,Finset.sum_div,div_selfset rz : Z → X → ℝ := fun z x => pX x * PZ x z / pZ z with hrz have hmem : ∀ z ∈ (Finset.univ : Finset Z), rz z ∈ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} := by intro z _ refine ⟨fun x => div_pos (mul_pos (hpX x) (hPZ x z)) (hpZpos z), ?_⟩ simp only [hrz, ← Finset.sum_div] exact div_self (hpZpos z).ne'
By Jensen's inequality, $\sum_z p_Z(z) \theta_f(r_z) \le \theta_f\left(\sum_z p_Z(z) r_z\right)$.
Because $\theta_f$ is concave on the simplex of strictly positive probability distributions, $p_Z$ is a non-negative probability vector summing to $1$, and each $r_z$ belongs to that simplex, Jensen's inequality for concave functions (`ConcaveOn.le_map_sum`, invoked via `hcc.le_map_sum`) bounds the weighted average of function values by the function value at the convex combination.
have hj := hcc.le_map_sum (t := Finset.univ) (w := pZ) (p := rz) (fun z _ => (hpZpos z).le) hsZ1 hmem
The mixture of posteriors recovers the prior: $\sum_z p_Z(z) r_z = p_X$.
Evaluating at each $x \in X$, the sum is $\sum_z p_Z(z) \cdot \frac{p_X(x) P_Z(x, z)}{p_Z(z)}$. Cancelling $p_Z(z)$ (`mul_div_cancel₀`) leaves $\sum_z p_X(x) P_Z(x, z) = p_X(x) \sum_z P_Z(x, z) = p_X(x) \cdot 1 = p_X(x)$ using `Finset.mul_sum` and `mul_one`.
uses
Finset.sum_apply,Pi.smul_apply,smul_eq_mul,mul_div_cancel₀,Finset.mul_sum,mul_onehave hsum : ∑ z, pZ z • rz z = pX := by funext x simp only [Finset.sum_apply, Pi.smul_apply, smul_eq_mul, hrz] have : ∀ z, pZ z * (pX x * PZ x z / pZ z) = pX x * PZ x z := fun z => mul_div_cancel₀ _ (hpZpos z).ne' simp only [this, ← Finset.mul_sum, hsZ, mul_one]
$\tilde{I}_f(X; YZ) \le \tilde{I}_f(X; Y) + \tilde{I}_f(X; Z)$. automation
Substituting $\sum_z p_Z(z) r_z = p_X$ into Jensen's inequality and using lemma `mutual_f_theta_self` (which identifies $\theta_f(p_X)$ with $\tilde{I}_f(X; Y)$) yields $\sum_z p_Z(z) \theta_f(r_z) \le \tilde{I}_f(X; Y)$. Combining this with the decomposition $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z) = \sum_z p_Z(z) \theta_f(r_z)$, linear arithmetic (`linarith`) completes the proof of subadditivity.
uses
mutual_f_theta_self,smul_eq_mulrw [hsum, mutual_f_theta_self f hf1 pX PY hpX hsY] at hj simp only [smul_eq_mul] at hj linarith
mutual_f_information_markov_sub_eq_sum_theta- For a Markov chain $Y \to X \to Z$, the difference $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z)$ equals the expectation over $z$ of the conditional mutual $f$-information functional $\theta_f(r_z)$ evaluated at the posterior distributions $r_z(x) = p_X(x) P_Z(x, z) / p_Z(z)$.
mutual_f_theta_concaveOn_of_weight_bound- Under the differential inequality hypothesis on $f$, the functional $r \mapsto \theta_f(r)$ is concave on the simplex of strictly positive probability distributions on $X$.
not_nonempty_iff- A type is not nonempty if and only if it is empty.
Finset.sum_pos- The sum of strictly positive elements over a nonempty finite set is strictly positive.
mul_pos- The product of two strictly positive real numbers is strictly positive.
Classical.arbitrary- Chooses an arbitrary element from a nonempty type.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.sum_comm- Double summation over finite sets can be interchanged: $\sum_{x \in s} \sum_{y \in t} f(x, y) = \sum_{y \in t} \sum_{x \in s} f(x, y)$.
Finset.mul_sum- Multiplication distributes over finite sums: $a \sum_{i \in s} f(i) = \sum_{i \in s} a f(i)$.
mul_one- Multiplying by 1 leaves any element unchanged: $a \cdot 1 = a$.
div_pos- The quotient of two strictly positive real numbers is strictly positive.
Finset.sum_div- Division distributes over finite sums: $(\sum_{i \in s} f(i)) / a = \sum_{i \in s} (f(i) / a)$.
div_self- Any non-zero real number divided by itself equals 1: $a / a = 1$.
Finset.sum_apply- A sum of functions evaluated at an argument equals the sum of their values: $(\sum_{c \in s} g(c))(a) = \sum_{c \in s} g(c)(a)$.
Pi.smul_apply- Scalar multiplication of a function evaluated at an index equals the scalar multiple of the value: $(a \cdot f)(i) = a \cdot f(i)$.
smul_eq_mul- Scalar multiplication of real numbers coincides with ordinary multiplication: $a \cdot b = a * b$.
mul_div_cancel₀- Multiplying by $b$ cancels a division by $b$ when $b \neq 0$: $b \cdot (a / b) = a$.
mutual_f_theta_self- The auxiliary functional $\theta_f$ evaluated at the prior $p_X$ itself equals the mutual $f$-information $\tilde{I}_f(X; Y)$.
- Jensen's inequality is applied via `hcc.le_map_sum` (dot notation for Mathlib's `ConcaveOn.le_map_sum`), using the concavity of the functional $\theta_f$ established in `mutual_f_theta_concaveOn_of_weight_bound`.
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_subadditive_full_support_of_weight_bound (f : ℝ → ℝ) (hf1 : f 1 = 0) (hconv : ConvexOn ℝ (Set.Ioi 0) f) (hsmooth : ContDiffOn ℝ 4 f (Set.Ioi 0)) (hg2 : ∀ x > 0, deriv (deriv (subadditive_f_weight f)) x < 0) (hbound : ∃ η ℓ : ℝ, 0 < η ∧ ∀ x > 0, subadditive_f_weight f x + 2 * (deriv (subadditive_f_weight f) x - η) ^ 2 / (-deriv (deriv (subadditive_f_weight f)) x) ≤ 2 * η + (x - 1) * ℓ) : mutual_f_information_subadditive_full_support f := by intro X Y Z _ _ _ pX PY PZ hpX hsX hPY hsY hPZ hsZ have hdec := mutual_f_information_markov_sub_eq_sum_theta f pX PY PZ hpX hsX hPY hsY hPZ hsZ have hcc := mutual_f_theta_concaveOn_of_weight_bound f hf1 hconv hsmooth hg2 hbound pX PY hpX hsX hPY hsY have hX : Nonempty X := by by_contra h rw [not_nonempty_iff] at h simp at hsX set pZ : Z → ℝ := fun z => ∑ x, pX x * PZ x z with hpZ 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 hsZ1 : ∑ z, pZ z = 1 := by simp only [hpZ] rw [Finset.sum_comm] simp only [← Finset.mul_sum, hsZ, mul_one, hsX] set rz : Z → X → ℝ := fun z x => pX x * PZ x z / pZ z with hrz have hmem : ∀ z ∈ (Finset.univ : Finset Z), rz z ∈ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} := by intro z _ refine ⟨fun x => div_pos (mul_pos (hpX x) (hPZ x z)) (hpZpos z), ?_⟩ simp only [hrz, ← Finset.sum_div] exact div_self (hpZpos z).ne' have hj := hcc.le_map_sum (t := Finset.univ) (w := pZ) (p := rz) (fun z _ => (hpZpos z).le) hsZ1 hmem have hsum : ∑ z, pZ z • rz z = pX := by funext x simp only [Finset.sum_apply, Pi.smul_apply, smul_eq_mul, hrz] have : ∀ z, pZ z * (pX x * PZ x z / pZ z) = pX x * PZ x z := fun z => mul_div_cancel₀ _ (hpZpos z).ne' simp only [this, ← Finset.mul_sum, hsZ, mul_one] rw [hsum, mutual_f_theta_self f hf1 pX PY hpX hsY] at hj simp only [smul_eq_mul] at hj linarith