Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Discrete entropy, conditional entropy and mutual information over finite alphabets

Definition
TranscendenceTowerFiniteInformation

by mateoej12 · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

entropyformalizationinformation-theoryprobability

Shannon's finite information quantities, over arbitrary finite alphabets.

Let α\alphaα and β\betaβ be finite types and let ppp be a real-valued mass function. All quantities below are plain finite sums measured in nats, and every logarithm is natural.

The Shannon summand is s(p)=plog⁡p−1s(p)=p\log p^{-1}s(p)=plogp−1, and the entropy of a mass function on α\alphaα is H(p)=∑x∈αs(p(x))H(p)=\sum_{x\in\alpha}s(p(x))H(p)=∑x∈α​s(p(x)). The usual convention 0log⁡0=00\log 0=00log0=0 is not imposed by a side condition; it is inherited from the Lean convention log⁡0=0\log 0=0log0=0, which makes s(0)=0s(0)=0s(0)=0 definitionally.

For a joint mass function JJJ on α×β\alpha\times\betaα×β the bundle defines the two marginals

p(a)=∑b∈βJ(a,b),m(b)=∑a∈αJ(a,b),p(a)=\sum_{b\in\beta}J(a,b), \qquad m(b)=\sum_{a\in\alpha}J(a,b),p(a)=b∈β∑​J(a,b),m(b)=a∈α∑​J(a,b),

the joint entropy H(α,β)=∑a∑bs(J(a,b))H(\alpha,\beta)=\sum_{a}\sum_{b}s(J(a,b))H(α,β)=∑a​∑b​s(J(a,b)), the conditional entropy

H(β∣α)=∑a∑bJ(a,b)log⁡p(a)J(a,b),H(\beta\mid\alpha)=\sum_{a}\sum_{b}J(a,b)\log\frac{p(a)}{J(a,b)},H(β∣α)=a∑​b∑​J(a,b)logJ(a,b)p(a)​,

and the mutual information

I(α;β)=∑a∑bJ(a,b)log⁡J(a,b)p(a) m(b).I(\alpha;\beta)=\sum_{a}\sum_{b}J(a,b)\log\frac{J(a,b)}{p(a)\,m(b)} .I(α;β)=a∑​b∑​J(a,b)logp(a)m(b)J(a,b)​.

In the last two, a cell with J(a,b)=0J(a,b)=0J(a,b)=0 contributes 000 by an explicit guard rather than by a limiting argument. Finally, a mass function is a distribution when it is nonnegative and sums to one.

These definitions are the discrete counterparts of quantities Mathlib currently provides only in measure-theoretic form: it supplies the binary entropy function and a Kullback-Leibler divergence on measures, but no discrete entropy, conditional entropy or mutual information. Stating anything about product alphabets -- for instance I(αn;βn)I(\alpha^n;\beta^n)I(αn;βn) for a memoryless channel -- requires the definitions to be polymorphic in the alphabet, which is the point of this bundle.

Formalization note. Mass functions are bare functions α → ℝ over a Fintype rather than elements of a probability-mass type, and normalization appears as a hypothesis on the theorems rather than as a bundled invariant. The explicit zero-mass guard, rather than a positivity hypothesis, is what allows the identities to be stated for every nonnegative joint law.

Definition code
/-
Generic finite Shannon information theory over arbitrary finite alphabets.

Mathlib supplies `Real.binEntropy` and a measure-theoretic Kullback-Leibler
divergence, but no discrete entropy, conditional entropy or mutual information.
This bundle supplies them over any `Fintype`, as plain finite sums in nats,
with zero-mass cells contributing zero by convention.

Definitions only; every claim about these objects is proved in the theorem
that imports this bundle.
-/

import Mathlib.Analysis.SpecialFunctions.BinaryEntropy
import Mathlib.Analysis.MeanInequalities

set_option autoImplicit false

open scoped BigOperators

namespace TranscendenceTower.FiniteInformation

noncomputable section

variable {α β : Type} [Fintype α] [Fintype β]

/-- A finite mass function is a distribution when it is nonnegative and sums
to one. -/
def IsDist (mass : α → ℝ) : Prop :=
  (∀ x, 0 ≤ mass x) ∧ ∑ x, mass x = 1

/-- The Shannon summand, in nats, with the standard `0 log 0 = 0` convention
supplied by `Real.log 0 = 0`. -/
def shannon (p : ℝ) : ℝ := p * Real.log p⁻¹

@[simp] theorem shannon_zero : shannon (0 : ℝ) = 0 := by simp [shannon]

@[simp] theorem shannon_one : shannon (1 : ℝ) = 0 := by simp [shannon]

/-- Shannon entropy of a finite mass function, in nats. -/
def entropy (mass : α → ℝ) : ℝ := ∑ x, shannon (mass x)

/-- The first marginal of a joint law. -/
def fstMarginal (joint : α → β → ℝ) : α → ℝ := fun a => ∑ b, joint a b

/-- The second marginal of a joint law. -/
def sndMarginal (joint : α → β → ℝ) : β → ℝ := fun b => ∑ a, joint a b

/-- Joint entropy of a law on `α × β`. -/
def jointEntropy (joint : α → β → ℝ) : ℝ :=
  ∑ a, ∑ b, shannon (joint a b)

/-- Conditional entropy `H(β ∣ α)`, as the joint sum
`∑ p(a,b) log (p(a) / p(a,b))`.  Cells of zero mass contribute zero. -/
def condEntropy (joint : α → β → ℝ) : ℝ :=
  ∑ a, ∑ b,
    if joint a b = 0 then 0
    else joint a b * Real.log (fstMarginal joint a / joint a b)

/-- Mutual information of a joint law against its own marginals, in nats.
Cells of zero mass contribute zero. -/
def mutualInfo (joint : α → β → ℝ) : ℝ :=
  ∑ a, ∑ b,
    if joint a b = 0 then 0
    else joint a b *
      Real.log (joint a b / (fstMarginal joint a * sndMarginal joint b))

end

end TranscendenceTower.FiniteInformation
Source
Mateo Estrada, Harmless and Pointless: Consistency, rigidity, and the indeterminacy of context transfer in McCarthy's formalization of context, 7 September 2026, Section 8, supporting infrastructure (not a numbered result); cf. Cover and Thomas, Elements of Information Theory, 2nd ed., Ch. 2.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me