Lemma A.10 (Yang–Barron), eq. (93):
ProvedHellingerSubadd.lemmaA10_klDiv_lehellinger-distanceinformation-theoryinteractive-decision-makingprobability
Let and be probability distributions over a measurable space , and let be a real number with
Then
This converts a bounded likelihood ratio into a comparison between KL divergence and squared Hellinger distance; in the proof of Lemma A.13 it is applied with (Term I) and (Term II).
Differences from the source:
- encoding: sup_{F∈F} P(F)/Q(F) ≤ V → ∀ F, MeasurableSet F → μ F ≤ ENNReal.ofReal V * ν F; reason: the same condition with 0/0 ignored and p/0 = ∞ for p > 0; F = univ forces V ≥ 1
- encoding: real-valued KL and (2 + log V) D²_H → klDiv and hellingerSq in ℝ≥0∞, factor ENNReal.ofReal (2 + Real.log V); reason: V ≥ 1 makes 2 + log V positive, so ofReal is exact; klDiv is the paper's KL for probability measures
Preamble
import Mathlib import Definitions.Def_HellingerSubadd_hellingerSq open MeasureTheory InformationTheory open scoped ENNReal
Formal statement
namespace HellingerSubadd
/-- **Lemma A.10 (Lemma 4 of Yang and Barron (1998)), eq. (93).**
Foster, Kakade, Qian & Rakhlin, *The Statistical Complexity of Interactive Decision Making*,
arXiv:2112.13487v3, Lemma A.10, eq. (93), p. 72: "Let P and Q be probability distributions over a
measurable space (X, F). If sup_{F∈F} P(F)/Q(F) ≤ V, then D_KL(P ∥ Q) ≤ (2 + log(V))D²_H(P, Q)."
For probability measures `μ, ν` and a real `V` with `μ(F) ≤ V · ν(F)` for every measurable `F`,
`D_KL(μ ∥ ν) ≤ (2 + log V) · D²_H(μ, ν)`.
**Formalization Note.** The ratio bound `sup_F P(F)/Q(F) ≤ V` is encoded multiplicatively,
`μ F ≤ ENNReal.ofReal V * ν F` for every measurable `F`: the same condition, with `0/0` ignored
and `p/0 = ∞` for `p > 0`. Taking `F = univ` forces `V ≥ 1`, so `2 + log V ≥ 2`. Values in `ℝ≥0∞`;
the real factor enters through `ENNReal.ofReal`; `log` is the natural logarithm. -/
theorem lemmaA10_klDiv_le {α : Type*} [MeasurableSpace α] (μ ν : Measure α)
[IsProbabilityMeasure μ] [IsProbabilityMeasure ν] (V : ℝ)
(hV : ∀ F, MeasurableSet F → μ F ≤ ENNReal.ofReal V * ν F) :
klDiv μ ν ≤ ENNReal.ofReal (2 + Real.log V) * hellingerSq μ ν := by sorry
end HellingerSubadd
Source
Foster, Kakade, Qian & Rakhlin, The Statistical Complexity of Interactive Decision Making, arXiv:2112.13487v3, Lemma A.10, eq. (93), p. 72