Perrone measures information in a Markov Category by how far an equation fails to hold. Choose a divergence on each hom-set, then:
- mutual information is the divergence from independence;
- entropy is the divergence from determinism.
A morphism is deterministic when copying its output is the same as running it twice, . So its entropy is
the divergence between the two sides of the determinism equation. With the Kullback–Leibler divergence on finite stochastic maps this is Shannon entropy; with other divergences it is Rényi entropy or a total-variation entropy. All of them satisfy the data processing inequality automatically.
Sources: Perrone arXiv:2212.11719 (notes) Definitions 2.1, 2.5, 2.9, 3.1, 4.1, Remark 2.2, Theorem 2.7, Propositions 2.10, 3.2, 4.2, Theorems 4.6, 4.10, Corollary 4.7; St Clere Smithe & Perin, AutoBayes arXiv:2503.18608 (notes) Remark 26.
Divergences on a Markov category
A divergence on a set (Definition 2.1) is a function with . It need not be symmetric or satisfy the triangle inequality, and it is strict if forces . A divergence is to a Lawvere metric what a reflexive relation is to a preorder (Remark 2.2).
A divergence on a Markov category (Definition 2.5) is a divergence on every hom-set such that composition and tensor are non-expanding:
By Theorem 2.7 this is equivalent to marginalising not increasing divergence, joint channels obeying a chain inequality, and discarding an unused input changing nothing. These are the data processing inequalities, built into the definition. Relative entropy on (Definition 2.9, Proposition 2.10), the Rényi divergences and total variation all qualify, and so do their extensions to .
Mutual information and entropy
- Mutual information (Definition 3.1): for , . This is the divergence between and the product of its marginals, i.e. from conditional independence given . It satisfies a data processing inequality under post-processing of either output (Proposition 3.2).
- Entropy (Definition 4.1): , the mutual information of an output with itself, as in . Deterministic morphisms have entropy zero, and if is strict only they do. Post-processing by a deterministic map cannot increase entropy (Proposition 4.2); a stochastic one can, since it adds randomness.
What comes out on
Theorem 4.6. For a probability measure on a standard Borel space, iff is discrete.
Corollary 4.7. if is discrete, and otherwise.
Theorem 4.10. With the total variation divergence, : the probability that two independent draws differ.
So the categorical KL entropy of a Gaussian is infinite, not the differential entropy . Copying a continuous variable produces a measure on the diagonal, which is singular with respect to . Differential entropy is a relative quantity: it depends on the reference measure (Lebesgue) and changes under reparametrisation. It is not intrinsic to the morphism, and Perrone’s construction only sees intrinsic quantities.
In AutoBayes and Lenticulum
- Laxness of parallel composition. For a Statistical Game, the gap between the loss of a parallel composite and the sum of the parts’ losses is a mutual information (AutoBayes Remark 26). Definition 3.1 reads such a quantity as a divergence from independence. Writing AutoBayes’s gap exactly as an of a morphism in Perrone’s sense is a natural next step, not done here.
- Lenticulum’s entropies. The free energies of Lenticulum.jl’s Gaussian factors use differential entropies (Scalar and Multivariate Energy §8). They are finite because they are taken relative to Lebesgue measure. Corollary 4.7 explains why that choice is needed and not given by the category: the intrinsic KL entropy of every continuous belief is infinite.
Docs: Julia manual: multi-dimensional arrays — finite stochastic maps as arrays; copy ∘ p is a diagonal matrix.
# Entropy as the divergence from determinism (Perrone, Definition 4.1) on FinStoch
kl(P, Q) = sum(P[i] > 0 ? P[i] * log(P[i] / Q[i]) : 0.0 for i in eachindex(P)) # Definition 2.9
copy_of(p) = [i == j ? p[i] : 0.0 for i in eachindex(p), j in eachindex(p)] # copy ∘ p
twice(p) = [p[i] * p[j] for i in eachindex(p), j in eachindex(p)] # (p ⊗ p) ∘ copy
H_KL(p) = kl(copy_of(p), twice(p))
p = [0.5, 0.25, 0.125, 0.125]
H_KL(p) ≈ -sum(x * log(x) for x in p) # true: Shannon entropy (Corollary 4.7)
H_KL([0.0, 1.0, 0.0]) == 0 # true: deterministic ⇒ entropy 0
# Total variation entropy (Theorem 4.10): probability that two independent draws differ
tv(P, Q) = sum(abs.(P .- Q)) / 2
tv(copy_of(p), twice(p)) ≈ 1 - sum(p .^ 2) # true
# Mutual information (Definition 3.1) as the divergence from independence
h = [0.3 0.1; 0.1 0.5] # a joint state on X ⊗ Y
I = kl(h, sum(h, dims = 2) * sum(h, dims = 1))
I > 0 # true: X and Y are dependentimport Mathlib
open Real
/-- `copy ∘ p` and `(p ⊗ p) ∘ copy` for a finite distribution `p`, as joint masses. -/
def copyState {n : ℕ} (p : Fin n → ℝ) : Fin n × Fin n → ℝ := fun ij => if ij.1 = ij.2 then p ij.1 else 0
def twiceState {n : ℕ} (p : Fin n → ℝ) : Fin n × Fin n → ℝ := fun ij => p ij.1 * p ij.2
/-- The KL divergence on finite masses (Definition 2.9), written with `Real.log`. -/
noncomputable def klFin {α : Type*} [Fintype α] (P Q : α → ℝ) : ℝ := ∑ a, P a * log (P a / Q a)
/-- Definition 4.1 with `D = KL`: the divergence from determinism. -/
noncomputable def entropyKL {n : ℕ} (p : Fin n → ℝ) : ℝ := klFin (copyState p) (twiceState p)
#check @InformationTheory.klDiv -- Mathlib's KL divergence between measures (Stoch)
#check @Real.negMulLog -- x ↦ -x log x, the summand of Shannon entropy-- Perrone's entropy and mutual information on finite distributions
kl :: [Double] -> [Double] -> Double
kl ps qs = sum [ p * log (p / q) | (p, q) <- zip ps qs, p > 0 ]
copyOf, twice :: [Double] -> [Double] -- flattened n × n joint masses
copyOf p = [ if i == j then pi' else 0 | (i, pi') <- zip [0 :: Int ..] p, (j, _) <- zip [0 ..] p ]
twice p = [ a * b | a <- p, b <- p ]
entropyKL :: [Double] -> Double
entropyKL p = kl (copyOf p) (twice p)
main :: IO ()
main = do
let p = [0.5, 0.25, 0.125, 0.125]
print (entropyKL p, negate (sum [ x * log x | x <- p ])) -- equal: Shannon entropy
print (entropyKL [0, 1, 0]) -- 0: deterministic