/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import Mathlib.Analysis.SpecialFunctions.BinaryEntropy public import Mathlib.MeasureTheory.Measure.Prod public import Mathlib.MeasureTheory.Measure.Real public import Mathlib.Tactic.FunProp

Shannon entropy of finite-valued random variables

This file defines Shannon entropy and mutual information, in bits, for finite-valued random variables.

For a probability measure μ and a function U with measurable fibers, write q_U(a) = μ.real (U ⁻¹' {a}) for the probability that U = a. For a probability q, Real.negMulLog q is -q ln q when q > 0 and 0 when q = 0, so

H(U) = (∑ a, Real.negMulLog (q_U a)) / Real.log 2 = -∑ a, q_U(a) log₂ q_U(a),

with the convention 0 log₂ 0 = 0; dividing by Real.log 2 converts nats to bits. Mutual information is I(U; V) = H(U) + H(V) - H(U, V).

Measurable fibers are automatic when U is measurable and its finite target has measurable singletons, in particular for finite discrete targets. The definitions are total expressions for arbitrary measures and functions; without normalization and measurable fibers they need not have their usual probabilistic interpretation.

The main results are invariance under measurable pushforward and the formula for the mutual information of the coordinate projections of a finite joint law.

@[expose] public sectionopen MeasureTheoryopen scoped BigOperatorsnamespace InformationTheoryvariable {Ω : Type*} [MeasurableSpace Ω]

Shannon entropy, in bits, of a finite-valued random variable.

For a probability measure μ, this is the usual Shannon entropy when every fiber U ⁻¹' {a} is measurable. In particular, this holds when U is measurable and its target has measurable singletons.

Zero-probability values contribute zero. The expression is also defined without these hypotheses, but then need not have a probabilistic interpretation.

noncomputable def shannonEntropyBits {α : Type*} [Fintype α] (μ : Measure Ω) (U : Ω → α) : ℝ := (∑ a, Real.negMulLog (μ.real (U ⁻¹' {a}))) / Real.log 2

Mutual information, in bits, of two finite-valued random variables, defined by I(U; V) = H(U) + H(V) - H(U, V).

For a probability measure μ, this is the usual mutual information when the fibers of both U and V are measurable. In particular, this holds for measurable functions into finite targets with measurable singletons.

The expression is also defined without these hypotheses, but then need not have a probabilistic interpretation.

noncomputable def mutualInformationBits {α : Type*} {β : Type*} [Fintype α] [Fintype β] (μ : Measure Ω) (U : Ω → α) (V : Ω → β) : ℝ := shannonEntropyBits μ U + shannonEntropyBits μ V - shannonEntropyBits μ (fun ω => (U ω, V ω))section Mapvariable {Ω' : Type*} {α : Type*} {β : Type*} [MeasurableSpace Ω'] [Fintype α] [MeasurableSpace α] [MeasurableSingletonClass α] [Fintype β] [MeasurableSpace β] [MeasurableSingletonClass β]

Entropy commutes with measurable pushforward of the sample-space measure. No normalization assumption on the measure is required.

Ω:Type u_1inst✝⁴:MeasurableSpace ΩΩ':Type u_2α:Type u_3inst✝³:MeasurableSpace Ω'inst✝²:Fintype αinst✝¹:MeasurableSpace αinst✝:MeasurableSingletonClass αμ:Measure ΩT:Ω → Ω'hT:Measurable TU:Ω' → αhU:Measurable Ua:αa✝:a ∈ Finset.univ⊢ (μ (T ⁻¹' U ⁻¹' {a})).toReal = (μ (U ∘ T ⁻¹' {a})).toReal All goals completed! 🐙

Mutual information commutes with measurable pushforward of the sample-space measure. No normalization assumption on the measure is required.

Ω:Type u_1inst✝⁷:MeasurableSpace ΩΩ':Type u_2α:Type u_3β:Type u_4inst✝⁶:MeasurableSpace Ω'inst✝⁵:Fintype αinst✝⁴:MeasurableSpace αinst✝³:MeasurableSingletonClass αinst✝²:Fintype βinst✝¹:MeasurableSpace βinst✝:MeasurableSingletonClass βμ:Measure ΩT:Ω → Ω'hT:Measurable TU:Ω' → αV:Ω' → βhU:Measurable UhV:Measurable VhUV:Measurable fun ω ↦ (U ω, V ω)⊢ shannonEntropyBits μ (U ∘ T) + shannonEntropyBits μ (V ∘ T) - shannonEntropyBits μ ((fun ω ↦ (U ω, V ω)) ∘ T) = shannonEntropyBits μ (U ∘ T) + shannonEntropyBits μ (V ∘ T) - shannonEntropyBits μ fun ω ↦ ((U ∘ T) ω, (V ∘ T) ω) All goals completed! 🐙end Map

The mutual information of the coordinate projections, written using the singleton masses of a finite measure on a finite product.

α:Type u_2β:Type u_3inst✝⁶:Fintype αinst✝⁵:MeasurableSpace αinst✝⁴:MeasurableSingletonClass αinst✝³:Fintype βinst✝²:MeasurableSpace βinst✝¹:MeasurableSingletonClass βν:Measure (α × β)inst✝:IsFiniteMeasure νhsum:∀ (s : Set (α × β)), ν.real s = ∑ w, if w ∈ s then ν.real {w} else 0hfst:∀ (a : α), ν.real (Prod.fst ⁻¹' {a}) = ∑ b, ν.real {(a, b)}hsnd:∀ (b : β), ν.real (Prod.snd ⁻¹' {b}) = ∑ a, ν.real {(a, b)}⊢ mutualInformationBits ν Prod.fst Prod.snd = (∑ a, (∑ b, ν.real {(a, b)}).negMulLog) / Real.log 2 + (∑ b, (∑ a, ν.real {(a, b)}).negMulLog) / Real.log 2 - (∑ ab, (ν.real {ab}).negMulLog) / Real.log 2 All goals completed! 🐙end InformationTheory