Proof of Measures on a Finite Set Given by Point Masses: the Measure, Integrals as Finite Sums, and Relative Entropy

Each result cited is universally quantified over the data in its own statement.

Throughout, $p:Y\to\mathbb{R}$ is a map with $0\le p(s)$ for every $s\in Y$. For nonempty $A\subseteq Y$ the set $A$ is finite by claim 3 of Basic Properties of Finite Sets, and $0\le\lambda_{p}(A)$ by Real Sums over a Finite Index Set: Comparison, Nonnegativity, Monotonicity, Term Bounds, Absolute Values, Counting and Limits §nonnegative; with $\lambda_{p}(\emptyset)=0$, every value of $\lambda_{p}$ is a nonnegative real number, so $\lambda_{p}$ is a map $\mathcal{P}(Y)\to[0,\infty]$. For every $s\in Y$, claim 1 of Peeling, Splitting, and Interchange for Sums over a Finite Index Set gives $\lambda_{p}(\{s\})=\sum_{x\in\{s\}}p(x)=p(s)$.

Step 0 (finite sets of natural numbers are bounded). For every nonempty finite $B\subseteq\mathbb{N}$ there is $N_{0}\in\mathbb{N}$ with $B\subseteq[N_{0}]$. Let $Q$ be the set of those $q\in\mathbb{N}$ such that every $B\subseteq\mathbb{N}$ with $q$ elements lies in $[N_{0}]$ for some $N_{0}\in\mathbb{N}$; we show $Q=\mathbb{N}$ by Principle of Induction for the Natural Numbers. If $B$ has $1$ element, then $B=\{b\}$ for some $b$, because $[1]=\{1\}$ by claim 2 of Basic Properties of Initial Segments of the Natural Numbers; and $B\subseteq[b]$ since $b\in[b]$ by claim 1 of that lemma; so $1\in Q$. Let $q\in Q$ and let $B\subseteq\mathbb{N}$ have $S(q)$ elements. By claim 2 of Peeling an Element off a Finite Set, and Unions of Finite Sets, $B=B'\cup\{x\}$ with $B'$ having $q$ elements, so $B'\subseteq[N_{1}]$ for some $N_{1}$. Put $N_{0}=N_{1}+x$. By Properties of the Order on the Natural Numbers §addition and the commutativity in claim 4 of Arithmetic of Addition on the Natural Numbers, $N_{1}<N_{0}$ and $x<x+N_{1}=N_{0}$, so $N_{1}\le N_{0}$ and $x\le N_{0}$ by Properties of the Order on the Natural Numbers §basic. Hence claim 4 of Basic Properties of Initial Segments of the Natural Numbers gives $B'\subseteq[N_{1}]\subseteq[N_{0}]$ and, with $x\in[x]$ from claim 1 of that lemma, $x\in[x]\subseteq[N_{0}]$. So $B\subseteq[N_{0}]$ and $S(q)\in Q$. Thus $Q=\mathbb{N}$, and the claim follows because a nonempty finite set has $q$ elements for some $q$, by Finite Set.

Claim 1 (Measure). By the first paragraph $\lambda_{p}(\emptyset)=0$ and $\lambda_{p}$ takes values in $[0,\infty]$. Let $(A_{m})_{m\in\mathbb{N}}$ be a sequence of pairwise disjoint members of $\mathcal{P}(Y)$ and $U=\bigcup_{m\in\mathbb{N}}A_{m}$. Every $\lambda_{p}(A_{m})$ is real, and the partial sums are $s_{N}=\sum_{m=1}^{N}\lambda_{p}(A_{m})=\sum_{m\in[N]}\lambda_{p}(A_{m})$ by claim 1 of Properties of a Sum over a Finite Index Set. By the definition of the sum of a sequence in Measure, Measure Space, and Probability Measure, it suffices to show that the partial sums are bounded above by $\lambda_{p}(U)$ and that some partial sum equals $\lambda_{p}(U)$: then $\lambda_{p}(U)$ is their least upper bound, which is $\sum_{m}\lambda_{p}(A_{m})$.

Case $U=\emptyset$. Then every $A_{m}$ is empty, every term $\lambda_{p}(A_{m})$ is $0$, and every $s_{N}$ is $0$ by Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing; so all partial sums equal $0=\lambda_{p}(U)$.

Case $U\neq\emptyset$. $U\subseteq Y$ is nonempty and finite, so it has $u$ elements for some $u\in\mathbb{N}$ by claim 3 of Basic Properties of Finite Sets. For $x\in U$ there is an $m$ with $x\in A_{m}$, and it is unique since the $A_{m}$ are pairwise disjoint; call it $m(x)$. The set $I=\{m(x):x\in U\}$ is the image of $U$ under $x\mapsto m(x)$, so it is nonempty and finite by claim 4 of Basic Properties of Finite Sets, and $A_{m}\neq\emptyset$ exactly when $m\in I$ (if $x\in A_{m}$ then $m=m(x)$). By Step 0 there is $N_{0}$ with $I\subseteq[N_{0}]$.

We show that $s_{N'}=\lambda_{p}(U)$ for every $N'\in\mathbb{N}$ with $I\subseteq[N']$. For $m\in[N']\setminus I$ the term $\lambda_{p}(A_{m})=\lambda_{p}(\emptyset)$ is $0$, so Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing gives $s_{N'}=\sum_{m\in I}\lambda_{p}(A_{m})=\sum_{m\in I}\bigl(\sum_{x\in A_{m}}p(x)\bigr)$. Let $T_{0}$ be the set of pairs $(m,x)$ with $m\in I$ and $x\in A_{m}$; by Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs (each $A_{m}$, $m\in I$, being nonempty and finite) this double sum equals $\sum_{t\in T_{0}}p(t_{2})$, where $t_{2}$ is the second entry of $t$. The map $\theta:U\to T_{0}$, $\theta(x)=(m(x),x)$, is a bijection: it is injective because the second entry recovers $x$, and surjective because $(m,x)\in T_{0}$ forces $x\in A_{m}$, hence $m=m(x)$. By claim 2 of Properties of a Sum over a Finite Index Set, $\sum_{t\in T_{0}}p(t_{2})=\sum_{x\in U}p(x)=\lambda_{p}(U)$.

In particular $s_{N_{0}}=\lambda_{p}(U)$. For arbitrary $N\in\mathbb{N}$ put $N'=N+N_{0}$; by Properties of the Order on the Natural Numbers §addition and claim 4 of Arithmetic of Addition on the Natural Numbers, $N<N'$ and $N_{0}<N_{0}+N=N'$, so $N\le N'$ and $N_{0}\le N'$ by Properties of the Order on the Natural Numbers §basic, and claim 4 of Basic Properties of Initial Segments of the Natural Numbers gives $[N]\subseteq[N']$ and $I\subseteq[N_{0}]\subseteq[N']$. The terms being nonnegative, Real Sums over a Finite Index Set: Comparison, Nonnegativity, Monotonicity, Term Bounds, Absolute Values, Counting and Limits §monotone gives $s_{N}\le s_{N'}=\lambda_{p}(U)$. This proves countable additivity, so $\lambda_{p}$ is a measure on $(Y,\mathcal{P}(Y))$ by Measure, Measure Space, and Probability Measure, with $\lambda_{p}(\{s\})=p(s)$ by the first paragraph.

Since $Y\neq\emptyset$, $\lambda_{p}(Y)=\sum_{s\in Y}p(s)$, so $\lambda_{p}$ is a probability measure if and only if $\sum_{s\in Y}p(s)=1$.

Converse. Let $\lambda$ be a probability measure on $(Y,\mathcal{P}(Y))$. For $s\in Y$, Basic Properties of a Measure §monotone gives $\lambda(\{s\})\le\lambda(Y)=1$; since $1<\infty$ by the conventions of Measure, Measure Space, and Probability Measure, $\lambda(\{s\})\neq\infty$, so $p(s)=\lambda(\{s\})$ is a real number with $0\le p(s)$. We have $\lambda(\emptyset)=0=\lambda_{p}(\emptyset)$. Let $A\subseteq Y$ be nonempty; by claim 3 of Basic Properties of Finite Sets it has $r$ elements for some $r\in\mathbb{N}$, with a bijection $\beta:[r]\to A$. The sets $\{\beta(1)\},\dots,\{\beta(r)\}$ are pairwise disjoint ($\beta$ is injective) and their union is $A$ ($\beta$ is surjective), so Basic Properties of a Measure §additivity gives $\lambda(A)=\sum_{i=1}^{r}\lambda(\{\beta(i)\})$, a finite sum in $[0,\infty]$; all its terms $\lambda(\{\beta(i)\})=p(\beta(i))$ are real, so this is the real finite sum, and with Sum over a Finite Index Set we obtain

$$\lambda(A)=\sum_{i=1}^{r}\lambda(\{\beta(i)\})=\sum_{i=1}^{r}p(\beta(i))=\sum_{s\in A}p(s)=\lambda_{p}(A).$$

Hence $\lambda=\lambda_{p}$.

Claim 2 (Integrals). By claim 1, $(Y,\mathcal{P}(Y),\lambda_{p})$ is a measure space. Every map $f$ from $Y$ to $\mathbb{R}$ or to $[0,\infty]$ is measurable: every preimage $f^{-1}(B)$, in particular every set $\{s\in Y:f(s)>c\}$, is a subset of $Y$ and hence a member of $\mathcal{P}(Y)$, so $f$ is measurable in the sense of Measurable Function and Real-Valued Measurable Function and of Measure Spaces and the Lebesgue Integral: Standing Notation §measurable.

(a) Nonnegative maps. Let $g:Y\to\mathbb{R}$ satisfy $0\le g(s)$ for every $s\in Y$. We show that its integral in the sense of Lebesgue Integral of a Nonnegative Measurable Function is

$$\int_{Y}g\,d\lambda_{p}=\sum_{s\in Y}g(s)\,p(s),$$

a real number. The image $g(Y)$ is nonempty and has $r$ elements for some $r\in\mathbb{N}$, by claim 4 of Basic Properties of Finite Sets; so $g$ is measurable and takes finitely many values, that is, it is a nonnegative simple function. Let $c:[r]\to g(Y)$ be a bijection, write $c_{i}=c(i)$ for its distinct values and $A_{i}=g^{-1}(\{c_{i}\})$; each $A_{i}$ is nonempty since $c_{i}$ is a value of $g$, the $A_{i}$ are pairwise disjoint and cover $Y$, and $g(s)=c_{i}$ for $s\in A_{i}$. By Simple Function and Its Integral, whose integral agrees with that of Lebesgue Integral of a Nonnegative Measurable Function for nonnegative simple functions as recorded there, and by claim 4 of Properties of a Sum over a Finite Index Set,

$$\int_{Y}g\,d\lambda_{p}=\sum_{i=1}^{r}c_{i}\,\lambda_{p}(A_{i})=\sum_{i=1}^{r}\Bigl(\sum_{s\in A_{i}}c_{i}\,p(s)\Bigr)=\sum_{i=1}^{r}\Bigl(\sum_{s\in A_{i}}g(s)\,p(s)\Bigr).$$

By claim 1 of Properties of a Sum over a Finite Index Set the last expression is the sum over $i\in[r]$, and by Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs it equals $\sum_{t\in T_{1}}g(t_{2})\,p(t_{2})$, where $T_{1}$ is the set of pairs $(i,s)$ with $i\in[r]$ and $s\in A_{i}$ and $t_{2}$ is the second entry of $t$. For $s\in Y$ let $i(s)$ be the unique $i\in[r]$ with $c_{i}=g(s)$; the map $s\mapsto(i(s),s)$ from $Y$ to $T_{1}$ is injective (the second entry recovers $s$) and surjective ($(i,s)\in T_{1}$ forces $g(s)=c_{i}$, so $i=i(s)$). Claim 2 of Properties of a Sum over a Finite Index Set therefore gives $\sum_{t\in T_{1}}g(t_{2})p(t_{2})=\sum_{s\in Y}g(s)p(s)$, proving (a).

(b) Arbitrary maps. Let $f:Y\to\mathbb{R}$, with positive and negative parts $f^{+}$, $f^{-}$ as in Integrable Function and the Lebesgue Integral; these are nonnegative maps $Y\to\mathbb{R}$ with $f=f^{+}-f^{-}$. By (a), $\int_{Y}f^{+}\,d\lambda_{p}$ and $\int_{Y}f^{-}\,d\lambda_{p}$ are the real numbers $\sum_{s\in Y}f^{+}(s)p(s)$ and $\sum_{s\in Y}f^{-}(s)p(s)$, hence finite, so $f$ is integrable by Integrable Function and the Lebesgue Integral, and by claims 3 and 4 of Properties of a Sum over a Finite Index Set

$$\int_{Y}f\,d\lambda_{p}=\sum_{s\in Y}f^{+}(s)p(s)-\sum_{s\in Y}f^{-}(s)p(s)=\sum_{s\in Y}\bigl(f^{+}(s)-f^{-}(s)\bigr)p(s)=\sum_{s\in Y}f(s)\,p(s).$$

For nonnegative $f$ this agrees with the value in (a), so the two readings of the integral of a nonnegative real-valued map coincide here.

Claim 3 (Relative entropy). By claim 1, $\lambda_{p}$ and $\lambda_{p'}$ are probability measures on $(Y,\mathcal{P}(Y))$; in particular $\lambda_{p}$ is finite. Let $h:Y\to\mathbb{R}$, $h(s)=p(s)/p'(s)$, which is defined since $p'(s)\neq0$, and satisfies $0\le h(s)$; it is measurable by claim 2. Let $A\in\mathcal{P}(Y)$. The map $\mathbf{1}_{A}h$ is nonnegative, so by claim 2, in either reading of the integral,

$$\int_{Y}\mathbf{1}_{A}\,h\,d\lambda_{p'}=\sum_{s\in Y}\mathbf{1}_{A}(s)\,h(s)\,p'(s)=\sum_{s\in Y}\mathbf{1}_{A}(s)\,p(s),$$

since $h(s)p'(s)=p(s)$. If $A=\emptyset$, every term is $0$ and the sum is $0=\lambda_{p}(\emptyset)$ by Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing. If $A\neq\emptyset$, the terms vanish off $A$, so by the same clause the sum equals $\sum_{s\in A}\mathbf{1}_{A}(s)p(s)=\sum_{s\in A}p(s)=\lambda_{p}(A)$. Hence $\lambda_{p}(A)=\int_{Y}\mathbf{1}_{A}h\,d\lambda_{p'}$ for every $A\in\mathcal{P}(Y)$, that is, $h$ is a density of $\lambda_{p}$ with respect to $\lambda_{p'}$ in the sense of The Radon-Nikodym Theorem for a Finite Measure and a Sigma-Finite Measure, and Uniqueness of Densities.

The map $\phi\circ h:Y\to\mathbb{R}$ is integrable with respect to $\lambda_{p'}$ by claim 2, with

$$\int_{Y}\phi\circ h\,d\lambda_{p'}=\sum_{s\in Y}\phi\Bigl(\frac{p(s)}{p'(s)}\Bigr)p'(s).$$

So $\lambda_{p}$ has the density $h$ with respect to $\lambda_{p'}$ for which $\phi\circ h$ is integrable, which by Relative Entropy of Probability Measures §relative-entropy means that $\lambda_{p}$ has finite relative entropy with respect to $\lambda_{p'}$, and $H(\lambda_{p}\,|\,\lambda_{p'})$ is the displayed integral. This proves claim 3.