Measure theory

Measure theory is the branch of mathematics that formalises the idea of assigning a size to a set. Only a small part of it is needed here, but that part is needed exactly, because the properties of a measure are what let the arithmetic of the later pages go through.

What a measure is

A measure is a function that maps each set in a collection of measurable sets to a non-negative real number. Area is a measure. Length, volume and mass are measures. Probability is a measure, distinguished only by the extra requirement that the whole space is assigned the value one.

Calling probability a measure is not a formality. It means the theorems about measures apply to it, and it explains why probabilities behave as they do: they add over disjoint alternatives because measures add over disjoint sets, not because of anything peculiar to chance.

The two precepts that do the work

Additivity. The measure of a union of disjoint sets is the sum of the measures of the individual sets. Two non-overlapping regions have a combined area equal to the sum of their areas; two mutually exclusive states have a combined probability equal to the sum of theirs.

The empty set has measure nil. Nothing occupies no size. Trivial as it looks, this is what anchors the scale and what makes differences of measure behave sensibly.

From these two, the familiar identity for overlapping sets follows: the measure of a union equals the sum of the measures less the measure of the intersection, because the overlap would otherwise be counted twice. That identity, applied to Shannon's measure rather than to area, is precisely what produces the relation between entropy, mutual information and conditional entropy set out under missing information.

Which sets are measurable

The collection of measurable sets is not arbitrary; it is governed by closure rules. If the collection contains sets A, B, C, … then it contains their union. If it contains a pair A and B, it contains the set differences A − B and B − A and the intersection A ∩ B. A collection closed in this way is called an algebra of sets — a σ-algebra when closure extends to countably infinite unions.

The reason for the rules is that a measure must be usable. Having assigned sizes to some sets, one immediately wants the size of their union, of what remains when one is removed from another, of what they share. Unless those combinations are themselves measurable the theory stalls at the first step. In the setting of this primer the collection contains the observed state-space X, the unobserved state-space Y, and everything constructible from them by union, difference and intersection — which is all that the later derivations require.

Set differences carry the meaning

One combination deserves emphasis in advance. The set difference Y − X contains the elements of Y not in X: what remains of the unobserved space once the overlap with the observed space is taken out. Under Shannon's measure that residue turns out to be interpretable as an inference, and its measure as the information the inference still lacks. The whole of the next page consists of taking that seriously.

How much of this is needed

For following this primer, the two precepts and the closure rules are enough; no integration theory, no convergence theorems, no pathological sets. Readers who want the real subject — Lebesgue measure, measurable functions, the dominated convergence theorem — will find a complete undergraduate development in MIT OpenCourseWare's Measure and Integration course. The point of the abbreviated version here is that a reader can see exactly which properties are being relied on, and can therefore see what would break if they failed.