Theorem 10.2.1 (Conditioning Does Not Increase Entropy): , with equality iff independent
ProvedWildeQIT.ZhangAudenaert.condEntropy_le_entropyentropyinformation-theoryp2o-gran-per-chapterp2o-plan-bookp2o-v1wilde-qit
Let and be random variables on finite alphabets and with joint distribution , marginal , entropy and conditional entropy (in bits). Then
and equality holds if and only if and are independent, that is, for all .
Side information never increases uncertainty on average. The inequality is used in the proof of Fano's inequality (10.87), and it is equivalent to the non-negativity of mutual information.
Formalization Note The pair is represented by its joint distribution on a product of finite types; independence is FinDist.Indep.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_WildeQIT_entropy import Definitions.Def_WildeQIT_condEntropy
Formal statement
namespace WildeQIT.ZhangAudenaert
/-- **Theorem 10.2.1 (Conditioning Does Not Increase Entropy).**
Wilde, *From Classical to Quantum Shannon Theory*, arXiv:1106.1445v8, Theorem 10.2.1, (10.20),
pp. 293–294: "The entropy `H(X)` is greater than or equal to the conditional entropy `H(X|Y)`:
`H(X) ≥ H(X|Y)`, and equality occurs if and only if `X` and `Y` are independent random
variables."
**Formalization Note.** The pair `(X, Y)` is its joint distribution `p` on `α × β` (finite
alphabets); `H(X) = entropy p.fst`, `H(X|Y) = condEntropy p` (bits), and independence is
`FinDist.Indep`: `p(x, y) = p_X(x) p_Y(y)` for all `x, y`. -/
theorem condEntropy_le_entropy {α β : Type} [Fintype α] [Fintype β] (p : FinDist (α × β)) :
condEntropy p ≤ entropy p.fst ∧ (condEntropy p = entropy p.fst ↔ p.Indep) := by sorry
end WildeQIT.ZhangAudenaert
Source
Wilde, From Classical to Quantum Shannon Theory, arXiv:1106.1445v8, Theorem 10.2.1, eq. (10.20), pp. 293–294
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.