mutual_hellinger_information_not_subadditive
Subadditivity fails in the Hellinger case β = 1/2: there are binary random variables X, Y, Z with Y ← X → Z and Ĩ_{f_{1/2}}(X; YZ) > Ĩ_{f_{1/2}}(X; Y) + Ĩ_{f_{1/2}}(X; Z). Instance: P(X = 0) = 1/300; P(Y = 0 | X = 0) = 1/3, P(Y = 0 | X = 1) = 1/300; Z is Y's channel mirrored, P(Z = z | x) = P(Y = 1 − z | x).
Statement
theorem mutual_hellinger_information_not_subadditive : ∃ (pX : Fin 2 → ℝ) (PY PZ : Fin 2 → Fin 2 → ℝ), (∀ x, 0 ≤ pX x) ∧ ∑ x, pX x = 1 ∧ (∀ x y, 0 ≤ PY x y) ∧ (∀ x, ∑ y, PY x y = 1) ∧ (∀ x z, 0 ≤ PZ x z) ∧ (∀ x, ∑ z, PZ x z = 1) ∧ mutual_f_information (power_divergence_generator (1 / 2)) (fun x y => pX x * PY x y) + mutual_f_information (power_divergence_generator (1 / 2)) (fun x z => pX x * PZ x z) < mutual_f_information (power_divergence_generator (1 / 2)) (fun x (yz : Fin 2 × Fin 2) => pX x * PY x yz.1 * PZ x yz.2)
- Related work
- List entry OP-332, a question proposed here from arXiv:2610.21231 (On the subadditivity of mutual f-information), Theorem 1 (a sufficient condition for subadditivity, toward the open question of Polyanskiy and Wu on further subadditive examples); the paper does not discuss the Hellinger case. Answered in the negative at β = 1/2.
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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}…
- power_divergence_generatorThe power-divergence generator f_β(x) = (x^β − βx + β − 1)/(β(β − 1)), for β ∉ {0, 1} and x ≥ 0 (β = 1/2 gives 2(√x − 1)², the squared…
- power_divergence_half_root_boundsFor x ≥ 0 and b ≥ 0, if a^2 ≤ x ≤ b^2 then a ≤ x^(1/2) ≤ b.
- Used by 1
- not_mutual_f_information_subadditive_hellingerThe mutual f-information is not subadditive for the Hellinger generator (power divergence with parameter 1/2).
The proof, explained
Subadditivity of mutual f-information is shown to fail for the Hellinger case β = 1/2 via an explicit binary counterexample: X has prior distribution (1/300, 299/300), Y is obtained through a channel with conditional distributions (1/3, 2/3) and (1/300, 299/300), and Z is Y's channel mirrored. After verifying that these define valid probability distributions, the subadditivity defect reduces to an algebraic inequality involving ten square roots of rational numbers. The proof establishes sharp two-sided rational bounds on each square root and completes the verification by real linear arithmetic.
We instantiate the random variables with explicit probability distributions.
We choose the prior distribution pX = (1/300, 299/300) and transition channels PY = [[1/3, 2/3], [1/300, 299/300]] and PZ = [[2/3, 1/3], [299/300, 1/300]], leaving seven subgoals: checking nonnegativity and normalization for each distribution, and verifying the strict failure of subadditivity.
refine ⟨![1/300, 299/300], ![![1/3, 2/3], ![1/300, 299/300]], ![![2/3, 1/3], ![299/300, 1/300]], ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩The chosen distributions and channels are nonnegative and normalize to 1.
For each distribution (pX, PY, PZ), nonnegativity is checked by enumerating the elements of Fin 2 and evaluating the entries with norm_num. Normalization is verified by expanding the sums over Fin 2 using Fin.sum_univ_two and computing the rational sums.
uses
Fin.sum_univ_two· intro x; fin_cases x <;> norm_num · norm_num [Fin.sum_univ_two] · intro x y; fin_cases x <;> fin_cases y <;> norm_num · intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num · intro x y; fin_cases x <;> fin_cases y <;> norm_num · intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num
Sharp rational lower and upper bounds are obtained for ten square roots.
For the power divergence parameter β = 1/2, evaluating mutual f-information involves square roots x^(1/2). Ten distinct square roots of rational numbers arise. For each root, power_divergence_half_root_bounds establishes rational lower and upper bounds a ≤ x^(1/2) ≤ b by verifying a² ≤ x and x ≤ b² with norm_num.
uses
power_divergence_half_root_bounds· obtain ⟨l0, u0⟩ := power_divergence_half_root_bounds (100 / 3433) (170672322461 / 1000000000000) (85336161231 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l1, u1⟩ := power_divergence_half_root_bounds (4000000 / 8923633) (669513202051 / 1000000000000) (167378300513 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l2, u2⟩ := power_divergence_half_root_bounds (20000 / 29867) (818312521921 / 1000000000000) (409156260961 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l3, u3⟩ := power_divergence_half_root_bounds (100 / 133) (216777492381 / 250000000000) (34684398781 / 40000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l4, u4⟩ := power_divergence_half_root_bounds (29900 / 36467) (90549399731 / 100000000000) (905493997311 / 1000000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l5, u5⟩ := power_divergence_half_root_bounds (29900 / 29867) (40022091867 / 40000000000) (250138074169 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l6, u6⟩ := power_divergence_half_root_bounds (8940100 / 8923633) (1000922237067 / 1000000000000) (250230559267 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l7, u7⟩ := power_divergence_half_root_bounds (2000000 / 36467) (7405680632443 / 1000000000000) (1851420158111 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l8, u8⟩ := power_divergence_half_root_bounds (10000 / 133) (8671099695241 / 1000000000000) (4335549847621 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l9, u9⟩ := power_divergence_half_root_bounds (1000000 / 3433) (17067232246187 / 1000000000000) (4266808061547 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
The mutual information inequality expands to a linear inequality in the bounded square roots.
We unfold the definitions of mutual f-information and the power divergence generator for β = 1/2, expand the product and finite sums with Fintype.sum_prod_type and Fin.sum_univ_two, evaluate matrix indexing via Matrix.cons_val_zero and Matrix.cons_val_one, and normalize all rational coefficients in the bounds and goal using norm_num.
uses
Fintype.sum_prod_type,Fin.sum_univ_two,Matrix.cons_val_zero,Matrix.cons_val_onesimp only [mutual_f_information, power_divergence_generator, Fintype.sum_prod_type, Fin.sum_univ_two, Fin.isValue, Matrix.cons_val_zero, Matrix.cons_val_one] norm_num at l0 u0 l1 u1 l2 u2 l3 u3 l4 u4 l5 u5 l6 u6 l7 u7 l8 u8 l9 u9 ⊢
Subadditivity fails: the mutual information with the pair strictly exceeds the sum of the individual mutual informations.
Linear arithmetic (linarith) combines the rational lower and upper bounds on the ten square roots with the normalized linear expression to conclude that I_{f_{1/2}}(X; Y) + I_{f_{1/2}}(X; Z) < I_{f_{1/2}}(X; YZ).
linarith
Fin.sum_univ_two- The sum of a function over a two-element type Fin 2 equals f 0 + f 1.
Fintype.sum_prod_type- The sum over a product type α₁ × α₂ is equal to the double sum over α₁ and α₂.
Matrix.cons_val_zero- The 0-th element of a vector constructed with Matrix.vecCons is the prepended head element.
Matrix.cons_val_one- The 1-st element of a vector constructed with Matrix.vecCons is the head of the remaining tail vector.
power_divergence_half_root_bounds- If 0 ≤ x, 0 ≤ b, a² ≤ x, and x ≤ b², then a ≤ x^(1/2) ≤ b.
- Because Lean cannot directly evaluate real square roots to verify numerical inequalities, the formal proof explicitly brackets each of the ten irrational square roots by rational bounds and reduces the verification to linear arithmetic.
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_hellinger_information_not_subadditive : ∃ (pX : Fin 2 → ℝ) (PY PZ : Fin 2 → Fin 2 → ℝ), (∀ x, 0 ≤ pX x) ∧ ∑ x, pX x = 1 ∧ (∀ x y, 0 ≤ PY x y) ∧ (∀ x, ∑ y, PY x y = 1) ∧ (∀ x z, 0 ≤ PZ x z) ∧ (∀ x, ∑ z, PZ x z = 1) ∧ mutual_f_information (power_divergence_generator (1 / 2)) (fun x y => pX x * PY x y) + mutual_f_information (power_divergence_generator (1 / 2)) (fun x z => pX x * PZ x z) < mutual_f_information (power_divergence_generator (1 / 2)) (fun x (yz : Fin 2 × Fin 2) => pX x * PY x yz.1 * PZ x yz.2) := by refine ⟨![1/300, 299/300], ![![1/3, 2/3], ![1/300, 299/300]], ![![2/3, 1/3], ![299/300, 1/300]], ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · intro x; fin_cases x <;> norm_num · norm_num [Fin.sum_univ_two] · intro x y; fin_cases x <;> fin_cases y <;> norm_num · intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num · intro x y; fin_cases x <;> fin_cases y <;> norm_num · intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num · obtain ⟨l0, u0⟩ := power_divergence_half_root_bounds (100 / 3433) (170672322461 / 1000000000000) (85336161231 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l1, u1⟩ := power_divergence_half_root_bounds (4000000 / 8923633) (669513202051 / 1000000000000) (167378300513 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l2, u2⟩ := power_divergence_half_root_bounds (20000 / 29867) (818312521921 / 1000000000000) (409156260961 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l3, u3⟩ := power_divergence_half_root_bounds (100 / 133) (216777492381 / 250000000000) (34684398781 / 40000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l4, u4⟩ := power_divergence_half_root_bounds (29900 / 36467) (90549399731 / 100000000000) (905493997311 / 1000000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l5, u5⟩ := power_divergence_half_root_bounds (29900 / 29867) (40022091867 / 40000000000) (250138074169 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l6, u6⟩ := power_divergence_half_root_bounds (8940100 / 8923633) (1000922237067 / 1000000000000) (250230559267 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l7, u7⟩ := power_divergence_half_root_bounds (2000000 / 36467) (7405680632443 / 1000000000000) (1851420158111 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l8, u8⟩ := power_divergence_half_root_bounds (10000 / 133) (8671099695241 / 1000000000000) (4335549847621 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) obtain ⟨l9, u9⟩ := power_divergence_half_root_bounds (1000000 / 3433) (17067232246187 / 1000000000000) (4266808061547 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num) simp only [mutual_f_information, power_divergence_generator, Fintype.sum_prod_type, Fin.sum_univ_two, Fin.isValue, Matrix.cons_val_zero, Matrix.cons_val_one] norm_num at l0 u0 l1 u1 l2 u2 l3 u3 l4 u4 l5 u5 l6 u6 l7 u7 l8 u8 l9 u9 ⊢ linarith