Chain rule, , and Gibbs' inequality over finite alphabets
ProvedTranscendenceTower.FiniteInformation.finite_information_basicsThe basic identities and inequalities of discrete Shannon information theory, over arbitrary finite alphabets and , in nats. Throughout, is a joint mass function on with nonnegative cells, and are its marginals, and normalization is assumed only where it is needed.
The statement collects eight facts.
- Marginals inherit normalization. If is a distribution then so are and .
- Chain rule. , requiring only nonnegativity.
- Mutual information from entropies. , again requiring only nonnegativity.
- Gibbs' inequality. for any joint distribution: a joint law is never less informative than the product of its own marginals.
- Subadditivity. , immediate from 3 and 4.
- Conditional entropy is nonnegative. .
- The standard form. .
- Information is bounded by output entropy. .
Items 6 through 8 are the single-letter ingredient of a weak converse to the channel coding theorem: they bound what one use of a channel can convey by the entropy of what is observed.
The mathematics is standard. What the statement establishes is that these identities hold for the guarded finite sums as defined -- with zero-mass cells contributing zero by an explicit case split rather than by a limit -- and for every nonnegative joint law, with no positivity hypothesis on the marginals. That is the form in which the definitions are actually usable.
Limits. These are single-letter facts about one joint law. Nothing here concerns product alphabets, conditional mutual information, Fano's inequality, or any asymptotic statement, and no channel coding theorem is proved or approached.
import Definitions.Def_TranscendenceTowerFiniteInformation set_option autoImplicit false open scoped BigOperators open TranscendenceTower.FiniteInformation
theorem TranscendenceTower.FiniteInformation.finite_information_basics (α β : Type) [Fintype α] [Fintype β] :
(∀ joint : α → β → ℝ, (∀ a b, 0 ≤ joint a b) →
(∑ a, ∑ b, joint a b = 1) →
IsDist (fstMarginal joint) ∧ IsDist (sndMarginal joint))
∧ (∀ joint : α → β → ℝ, (∀ a b, 0 ≤ joint a b) →
jointEntropy joint = entropy (fstMarginal joint) + condEntropy joint)
∧ (∀ joint : α → β → ℝ, (∀ a b, 0 ≤ joint a b) →
mutualInfo joint = entropy (fstMarginal joint)
+ entropy (sndMarginal joint) - jointEntropy joint)
∧ (∀ joint : α → β → ℝ, (∀ a b, 0 ≤ joint a b) →
(∑ a, ∑ b, joint a b = 1) → 0 ≤ mutualInfo joint)
∧ (∀ joint : α → β → ℝ, (∀ a b, 0 ≤ joint a b) →
(∑ a, ∑ b, joint a b = 1) →
jointEntropy joint
≤ entropy (fstMarginal joint) + entropy (sndMarginal joint))
∧ (∀ joint : α → β → ℝ, (∀ a b, 0 ≤ joint a b) → 0 ≤ condEntropy joint)
∧ (∀ joint : α → β → ℝ, (∀ a b, 0 ≤ joint a b) →
mutualInfo joint = entropy (sndMarginal joint) - condEntropy joint)
∧ (∀ joint : α → β → ℝ, (∀ a b, 0 ≤ joint a b) →
mutualInfo joint ≤ entropy (sndMarginal joint)) := by sorry