Theorem 10.8.1 (Pinsker Inequality) —
ProvedWildeQIT.PinskerRefined.theorem_10_8_1entropy-inequalitiesinformation-theoryp2o-gran-per-chapterp2o-plan-bookp2o-v1pinskerrelative-entropy
Let be a probability distribution on a finite alphabet and let satisfy . Then
where is the relative entropy in bits (Definition 10.5.2) and (Definition 10.7.1).
Pinsker's inequality turns a small relative entropy into a small trace distance. It strengthens the non-negativity of relative entropy, and it is the tool behind the lower bounds of Theorems 10.8.2 and 10.8.3.
Formalization Note is relEntropy with values in the extended reals ( off support). The bound is not a separate hypothesis because it follows from and .
Differences from the source:
- encoding: q : X → [0, 1] with Σ_x q(x) ≤ 1 → q ≥ 0 and Σ_x q(x) ≤ 1; reason: q(x) ≤ 1 follows from these two hypotheses, so the set of admissible q is the same
Preamble
import Definitions.Def_WildeQIT_relEntropy import Definitions.Def_WildeQIT_classicalTraceDist
Formal statement
namespace WildeQIT.PinskerRefined
open WildeQIT
/-- **Theorem 10.8.1 (Pinsker Inequality)**, Wilde, *From Classical to Quantum Shannon Theory*, arXiv:1106.1445v8, p. 311: let `p` be a probability distribution
on a finite alphabet `𝒳` and `q : 𝒳 → [0, 1]` with `∑_x q(x) ≤ 1`. Then
`D(p‖q) ≥ (1 / (2 ln 2)) ‖p − q‖₁²` (10.127).
**Formalization Note** `D` is the published `relEntropy` (bits, `EReal`, `+∞` off support,
Definition 10.5.2) and `‖p − q‖₁ = ∑_x |p(x) − q(x)|` is the published `classicalTraceDist`
(Definition 10.7.1). The book's `q(x) ≤ 1` is not a separate hypothesis: it follows from
`q ≥ 0` and `∑_x q(x) ≤ 1`. -/
theorem theorem_10_8_1 {α : Type} [Fintype α] (p : FinDist α) (q : α → ℝ)
(hq0 : ∀ x, 0 ≤ q x) (hq1 : ∑ x, q x ≤ 1) :
((1 / (2 * Real.log 2) * classicalTraceDist p.prob q ^ 2 : ℝ) : EReal) ≤
relEntropy p q := by sorry
end WildeQIT.PinskerRefined
Source
Wilde, From Classical to Quantum Shannon Theory, arXiv:1106.1445v8, Theorem 10.8.1, p. 311, Eq. (10.127)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.