Proof of Relative Entropy over a Finite Partition: the Chain Rule, Images of the Pieces, Refinement and Approximation by Partition Entropies

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

Preliminaries. Let $\phi$ be the function $s\mapsto s\log s$ of The Function $s\log s$: Continuity, Young's Inequality and Lower Bounds, with the Elementary Bounds for the Exponential and the Logarithm, so $\phi(0)=0$ and $\phi(t)=t\log t$ for positive $t$. By Relative Entropy of Probability Measures §relative-entropy fix a density $f$ of $\nu$ with respect to $\gamma$ such that $\phi\circ f$ is integrable with respect to $\gamma$; then $H(\nu\,|\,\gamma)=\int_{S}\phi\circ f\,d\gamma$. By the convention of The Radon-Nikodym Theorem for a Finite Measure and a Sigma-Finite Measure, and Uniqueness of Densities, $\nu$ is the measure with density $f$ with respect to $\gamma$ of claim 3 of Image Measures, Measures with Densities, and Change of Variables; thus $f$ is measurable, $0\le f$, and $\nu(A)=\int_{S}\mathbf{1}_{A}f\,d\gamma$ for every $A\in\mathcal{S}$. The function $\phi\circ f$ is measurable by The Function $s\log s$: Continuity, Young's Inequality and Lower Bounds, with the Elementary Bounds for the Exponential and the Logarithm §continuous, so $|\phi\circ f|$ is measurable by claim 4 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions, and $\int_{S}|\phi\circ f|\,d\gamma<\infty$ by the integrability criterion of Measure Spaces and the Lebesgue Integral: Standing Notation §integral, $\phi\circ f$ being integrable. For $A\in\mathcal{S}$ the functions $\mathbf{1}_{A}f$ and $\mathbf{1}_{A}(\phi\circ f)$ are measurable by claims 1 and 3 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions; the first is nonnegative with $\int_{S}\mathbf{1}_{A}f\,d\gamma=\nu(A)\le1$, so it is integrable with integral $\nu(A)$; for the second, $|\mathbf{1}_{A}(\phi\circ f)|$ is measurable by claim 4 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions and satisfies $|\mathbf{1}_{A}(\phi\circ f)|\le|\phi\circ f|$, so $\int_{S}|\mathbf{1}_{A}(\phi\circ f)|\,d\gamma\le\int_{S}|\phi\circ f|\,d\gamma<\infty$ by the monotonicity in Linearity and Monotonicity of the Lebesgue Integral §nonnegative, and $\mathbf{1}_{A}(\phi\circ f)$ is integrable by the criterion of Measure Spaces and the Lebesgue Integral: Standing Notation §integral; we write $I(A)=\int_{S}\mathbf{1}_{A}(\phi\circ f)\,d\gamma$. Properties of $\log$ used below: $\log(st)=\log s+\log t$ for positive $s,t$ by The Natural Logarithm, hence $\log1=\log(\exp0)=0$ by claim 1 of Basic Properties of the Exponential Function and $\log(s/t)=\log s-\log t$; $\log$ is increasing, being the inverse of the strictly increasing function $\exp$ (claim 4 of Basic Properties of the Exponential Function); and $\log t\le t-1$ for positive $t$ by The Function $s\log s$: Continuity, Young's Inequality and Lower Bounds, with the Elementary Bounds for the Exponential and the Logarithm §log.

Claim 1, Step 1 (Positivity of $q_{i}$). Let $i\in[m]$. If $q_{i}=\gamma(A_{i})=0$, then $p_{i}=\nu(A_{i})=0$ by Relative Entropy on a Measurable Space: the Gibbs Inequality, the Variational Criterion and Formula, the Entropy Inequality, Small Sets and Data Processing §small-sets. Hence $0<q_{i}$ whenever $0<p_{i}$, which is the hypothesis of The Partition Entropy of a Probability Measure Relative to Another over a Finite Measurable Partition §partition-entropy, so $h_{\mathcal{A}}(\nu\,|\,\gamma)$ is defined. Let $I_{\mathcal{A}}=\{i\in[m]:0<p_{i}\}$, nonempty as recorded in the preamble of The Partition Entropy of a Probability Measure Relative to Another over a Finite Measurable Partition.

Claim 1, Step 2 (A density of the piece). Fix $i\in I_{\mathcal{A}}$, so $0<p_{i}$ and $0<q_{i}$. By The Conditioned Probability Measure Given a Set of Positive Measure §conditioned, the piece $\gamma_{i}=\gamma(\cdot\,|\,A_{i})$ is the measure with density $k_{i}=q_{i}^{-1}\mathbf{1}_{A_{i}}$ with respect to $\gamma$ of claim 3 of Image Measures, Measures with Densities, and Change of Variables. Let $c_{i}=q_{i}/p_{i}$, a positive real number, and $f_{i}=c_{i}\mathbf{1}_{A_{i}}f$, a nonnegative measurable function by claims 1, 2 and 3 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions. For $B\in\mathcal{S}$, claim 3 of Image Measures, Measures with Densities, and Change of Variables (measure space $(S,\mathcal{S},\gamma)$, density $k_{i}$, nonnegative measurable function $\mathbf{1}_{B}f_{i}$) gives $\int_{S}\mathbf{1}_{B}f_{i}\,d\gamma_{i}=\int_{S}\mathbf{1}_{B}f_{i}k_{i}\,d\gamma$. Pointwise $\mathbf{1}_{B}f_{i}k_{i}=p_{i}^{-1}\mathbf{1}_{B\cap A_{i}}f$, because $\mathbf{1}_{A_{i}}\mathbf{1}_{A_{i}}=\mathbf{1}_{A_{i}}$ and $c_{i}q_{i}^{-1}=p_{i}^{-1}$. By the homogeneity in Linearity and Monotonicity of the Lebesgue Integral §nonnegative and the Preliminaries,

$$\int_{S}\mathbf{1}_{B}f_{i}\,d\gamma_{i}=p_{i}^{-1}\int_{S}\mathbf{1}_{B\cap A_{i}}f\,d\gamma=\frac{\nu(B\cap A_{i})}{p_{i}}=\nu_{i}(B),$$

the last equality being The Conditioned Probability Measure Given a Set of Positive Measure §conditioned for the piece $\nu_{i}=\nu(\cdot\,|\,A_{i})$. So $f_{i}$ is a density of the probability measure $\nu_{i}$ with respect to $\gamma_{i}$ in the sense of The Radon-Nikodym Theorem for a Finite Measure and a Sigma-Finite Measure, and Uniqueness of Densities.

Claim 1, Step 3 (Entropy of the piece). Keep $i\in I_{\mathcal{A}}$. We claim that, pointwise on $S$,

$$\phi\circ f_{i}=c_{i}\mathbf{1}_{A_{i}}(\phi\circ f)+c_{i}\log(c_{i})\,\mathbf{1}_{A_{i}}f .$$

At $x\notin A_{i}$ both sides are $\phi(0)=0$. At $x\in A_{i}$ with $f(x)=0$ both sides are $0$. At $x\in A_{i}$ with $0<f(x)$, $\phi(c_{i}f(x))=c_{i}f(x)\log(c_{i}f(x))=c_{i}\phi(f(x))+c_{i}\log(c_{i})f(x)$. Multiplying by $k_{i}$ and using $\mathbf{1}_{A_{i}}\mathbf{1}_{A_{i}}=\mathbf{1}_{A_{i}}$ and $c_{i}q_{i}^{-1}=p_{i}^{-1}$,

$$(\phi\circ f_{i})\,k_{i}=p_{i}^{-1}\mathbf{1}_{A_{i}}(\phi\circ f)+p_{i}^{-1}\log(c_{i})\,\mathbf{1}_{A_{i}}f .$$

By the Preliminaries and Linearity and Monotonicity of the Lebesgue Integral §integrable, the right-hand side is integrable with respect to $\gamma$ with integral $p_{i}^{-1}I(A_{i})+p_{i}^{-1}\log(c_{i})\,p_{i}=p_{i}^{-1}I(A_{i})-\log(p_{i}/q_{i})$, since $\log(c_{i})=\log(q_{i}/p_{i})=-\log(p_{i}/q_{i})$. The function $\phi\circ f_{i}$ is measurable by The Function $s\log s$: Continuity, Young's Inequality and Lower Bounds, with the Elementary Bounds for the Exponential and the Logarithm §continuous, so claim 3 of Image Measures, Measures with Densities, and Change of Variables (density $k_{i}$, real-valued function $\phi\circ f_{i}$) shows that $\phi\circ f_{i}$ is integrable with respect to $\gamma_{i}$ with $\int_{S}\phi\circ f_{i}\,d\gamma_{i}=p_{i}^{-1}I(A_{i})-\log(p_{i}/q_{i})$. By Step 2 and Relative Entropy of Probability Measures §relative-entropy, $\nu_{i}$ has finite relative entropy with respect to $\gamma_{i}$ and

$$p_{i}\,H(\nu_{i}\,|\,\gamma_{i})=I(A_{i})-p_{i}\log\frac{p_{i}}{q_{i}} .$$

Claim 1, Step 4 (Cells of $\nu$-measure $0$). Let $i\in[m]$ with $p_{i}=0$. Then $\int_{S}\mathbf{1}_{A_{i}}f\,d\gamma=0$, so $\mathbf{1}_{A_{i}}f=0$ $\gamma$-almost everywhere by The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §vanishing. At every $x$ with $\mathbf{1}_{A_{i}}(x)f(x)=0$ one has $\mathbf{1}_{A_{i}}(x)\phi(f(x))=0$, either because $x\notin A_{i}$ or because $f(x)=0$ and $\phi(0)=0$. Thus $\mathbf{1}_{A_{i}}(\phi\circ f)$ equals the zero function almost everywhere, and The Lebesgue Integral and Null Sets: Almost-Everywhere Comparison, Markov's Inequality, and Dominated Convergence Almost Everywhere §comparison gives $I(A_{i})=0$.

Claim 1, Step 5 (Summation). The cells are pairwise disjoint with union $S$ (Finite Measurable Partitions and Their Refinements §partition), so $\sum_{i=1}^{m}\mathbf{1}_{A_{i}}(x)=1$ for every $x\in S$ and $\phi\circ f=\sum_{i=1}^{m}\mathbf{1}_{A_{i}}(\phi\circ f)$. Applying Linearity and Monotonicity of the Lebesgue Integral §integrable once for each additional summand (induction on the number of summands) and then Step 4 with Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing and claim 1 of Properties of a Sum over a Finite Index Set,

$$H(\nu\,|\,\gamma)=\sum_{i=1}^{m}I(A_{i})=\sum_{i\in I_{\mathcal{A}}}I(A_{i}).$$

Summing the identity of Step 3 over $i\in I_{\mathcal{A}}$ (claims 3 and 4 of Properties of a Sum over a Finite Index Set) gives $\sum_{i\in I_{\mathcal{A}}}p_{i}H(\nu_{i}\,|\,\gamma_{i})=H(\nu\,|\,\gamma)-h_{\mathcal{A}}(\nu\,|\,\gamma)$, which is the chain rule. This proves claim 1.

Claim 2. Let $i\in I_{\mathcal{A}}$. By claim 1, $\nu_{i}$ has finite relative entropy with respect to $\gamma_{i}$, so Relative Entropy on a Measurable Space: the Gibbs Inequality, the Variational Criterion and Formula, the Entropy Inequality, Small Sets and Data Processing §data-processing, applied to the probability measures $\nu_{i}$ and $\gamma_{i}$ and the measurable map $R$, shows that $R_{\#}\nu_{i}$ has finite relative entropy with respect to $R_{\#}\gamma_{i}$ and $H(R_{\#}\nu_{i}\,|\,R_{\#}\gamma_{i})\le H(\nu_{i}\,|\,\gamma_{i})$. Multiplying by $p_{i}>0$, summing over $I_{\mathcal{A}}$, adding $h_{\mathcal{A}}(\nu\,|\,\gamma)$ and using the chain rule of claim 1 gives the asserted inequality.

Claim 3, Step 1 (Notation). Write $\mathcal{B}=(B_{1},\dots,B_{l})$, $p'_{j}=\nu(B_{j})$, $q'_{j}=\gamma(B_{j})$, $J=\{j\in[l]:0<p'_{j}\}$, and let $\nu'_{j}$, $\gamma'_{j}$ be the pieces of $\nu$ and $\gamma$ on $B_{j}$ for $j\in J$; by claim 1 applied to $\mathcal{B}$, $0<q'_{j}$ for $j\in J$. Let $I_{\mathcal{A}}$ be as in claim 1.

Claim 3, Step 2 ($h_{\mathcal{B}}\le H$). By claim 1 applied to $\mathcal{B}$, each $\nu'_{j}$, $j\in J$, has finite relative entropy with respect to $\gamma'_{j}$, hence $0\le H(\nu'_{j}\,|\,\gamma'_{j})$ by Relative Entropy on a Measurable Space: the Gibbs Inequality, the Variational Criterion and Formula, the Entropy Inequality, Small Sets and Data Processing §gibbs, and $H(\nu\,|\,\gamma)=h_{\mathcal{B}}(\nu\,|\,\gamma)+\sum_{j\in J}p'_{j}H(\nu'_{j}\,|\,\gamma'_{j})$. The sum is a finite sum of nonnegative numbers, so $h_{\mathcal{B}}(\nu\,|\,\gamma)\le H(\nu\,|\,\gamma)$.

Claim 3, Step 3 (Assigning cells of $\mathcal{B}$ to cells of $\mathcal{A}$). Let $j\in J$. Then $B_{j}\neq\emptyset$, since the empty set has measure $0$. By Finite Measurable Partitions and Their Refinements §refines there is $i\in[m]$ with $B_{j}\subseteq A_{i}$, and it is unique: if also $B_{j}\subseteq A_{i'}$ with $i'\ne i$, the nonempty set $B_{j}$ would lie in the empty set $A_{i}\cap A_{i'}$. Call it $\iota(j)$. Then $0<p'_{j}\le p_{\iota(j)}$ by monotonicity of $\nu$, so $\iota(j)\in I_{\mathcal{A}}$. For $i\in[m]$ let $J_{i}=\{j\in J:\iota(j)=i\}$. For $i\in[m]$ and $j\in[l]$: if $j\in J_{i}$ then $B_{j}\cap A_{i}=B_{j}$; if $j\in J\setminus J_{i}$ then $B_{j}\cap A_{i}\subseteq A_{\iota(j)}\cap A_{i}=\emptyset$; if $j\notin J$ then $\nu(B_{j}\cap A_{i})\le p'_{j}=0$. Since $\mathcal{B}$ is a partition, $A_{i}$ is the union of the pairwise disjoint sets $B_{j}\cap A_{i}$, $j\in[l]$, and finite additivity of $\nu$ and $\gamma$ (Measure Spaces and the Lebesgue Integral: Standing Notation §space) gives $p_{i}=\sum_{j=1}^{l}\nu(B_{j}\cap A_{i})$ and $q_{i}=\sum_{j=1}^{l}\gamma(B_{j}\cap A_{i})$. In the first sum every term with $j\notin J_{i}$ vanishes, and the terms with $j\in J_{i}$ are $p'_{j}$; in the second the terms with $j\in J_{i}$ are $q'_{j}$ and all terms are nonnegative. Now let $i\in I_{\mathcal{A}}$. The set $J_{i}$ is nonempty, since otherwise every term of the first sum would vanish and $p_{i}=0$ by Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing and claim 1 of Properties of a Sum over a Finite Index Set; hence the same two results give $p_{i}=\sum_{j\in J_{i}}p'_{j}$. If $[l]\setminus J_{i}$ is empty, the second sum is $q_{i}=\sum_{j\in J_{i}}q'_{j}$; otherwise Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §disjoint-union splits it as $q_{i}=\sum_{j\in J_{i}}q'_{j}+\sum_{j\in[l]\setminus J_{i}}\gamma(B_{j}\cap A_{i})$, and dropping the nonnegative second summand gives $\sum_{j\in J_{i}}q'_{j}\le q_{i}$, which therefore holds in both cases. Finally the sets $J_{i}$, $i\in I_{\mathcal{A}}$, are pairwise disjoint with union $J$.

Claim 3, Step 4 (The log-sum inequality on one cell). Let $i\in I_{\mathcal{A}}$. For $j\in J_{i}$ put $t_{j}=\frac{p_{i}\,q'_{j}}{q_{i}\,p'_{j}}$, a positive real number, so that $\log(p_{i}/q_{i})-\log(p'_{j}/q'_{j})=\log t_{j}\le t_{j}-1$. Using $p_{i}=\sum_{j\in J_{i}}p'_{j}$ and $\sum_{j\in J_{i}}q'_{j}\le q_{i}$ from Step 3,

$$p_{i}\log\frac{p_{i}}{q_{i}}-\sum_{j\in J_{i}}p'_{j}\log\frac{p'_{j}}{q'_{j}}=\sum_{j\in J_{i}}p'_{j}\log t_{j}\le\sum_{j\in J_{i}}\Bigl(\frac{p_{i}}{q_{i}}q'_{j}-p'_{j}\Bigr)=\frac{p_{i}}{q_{i}}\sum_{j\in J_{i}}q'_{j}-p_{i}\le0 .$$

Claim 3, Step 5 ($h_{\mathcal{A}}\le h_{\mathcal{B}}$). Summing Step 4 over $i\in I_{\mathcal{A}}$,

$$h_{\mathcal{A}}(\nu\,|\,\gamma)\le\sum_{i\in I_{\mathcal{A}}}\Bigl(\sum_{j\in J_{i}}p'_{j}\log\frac{p'_{j}}{q'_{j}}\Bigr)=\sum_{j\in J}p'_{j}\log\frac{p'_{j}}{q'_{j}}=h_{\mathcal{B}}(\nu\,|\,\gamma).$$

The middle equality holds because, by Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs, the iterated sum is the sum over the set $P$ of pairs $(i,j)$ with $i\in I_{\mathcal{A}}$ and $j\in J_{i}$, and by Step 3 the map $(i,j)\mapsto j$ is a bijection of $P$ onto $J$, with inverse $j\mapsto(\iota(j),j)$, so that claim 2 of Properties of a Sum over a Finite Index Set applies. Together with Step 2 this proves claim 3.

Claim 4, Step 1 (Choice of a test function). Let $\varepsilon$ be a positive real number and put $\delta=\varepsilon/2$. By Relative Entropy on a Measurable Space: the Gibbs Inequality, the Variational Criterion and Formula, the Entropy Inequality, Small Sets and Data Processing §supremum, $H(\nu\,|\,\gamma)$ is the least upper bound of the numbers $\Lambda^{\gamma}_{w}(\nu)$, $w$ bounded measurable, so by Approximation Property of the Supremum and the Infimum in $\mathbb{R}$ §epsilon-above we first choose a bounded measurable $w:S\to\mathbb{R}$ with $H(\nu\,|\,\gamma)-\delta<\Lambda^{\gamma}_{w}(\nu)$, then a bound $M$ for $w$, and then, by The Archimedean Property of the Real Numbers, a natural number $N$ with $2M+\delta<N\delta$.

Claim 4, Step 2 (A level-set partition). For $k\in\{0,1,\dots,N\}$ let $a_{k}=-M-\delta+k\delta$, so $a_{k}-a_{k-1}=\delta$ for $k\in[N]$, $a_{0}<-M$ and $M<a_{N}$. For $k\in[N]$ let $E_{k}=\{x\in S:a_{k-1}<w(x)\le a_{k}\}$, which is the difference of the sets $\{w>a_{k-1}\}$ and $\{w>a_{k}\}$, both in $\mathcal{S}$ by Measure Spaces and the Lebesgue Integral: Standing Notation §measurable; so $E_{k}\in\mathcal{S}$. The sets $E_{k}$ are pairwise disjoint: if $x\in E_{k}\cap E_{k'}$ with $k<k'$, then $w(x)\le a_{k}\le a_{k'-1}<w(x)$. They cover $S$: given $x\in S$, the set of $k\in[N]$ with $w(x)\le a_{k}$ contains $N$ because $w(x)\le M<a_{N}$; let $k$ be its least element; if $k=1$ then $a_{0}<-M\le w(x)$, and if $1<k$ then $k-1$ is not in that set, so $a_{k-1}<w(x)$; in both cases $x\in E_{k}$. Thus $\mathcal{A}'=(E_{1},\dots,E_{N})$ is a finite measurable partition of $S$. Write $p_{k}=\nu(E_{k})$, $q_{k}=\gamma(E_{k})$ and $P=\{k\in[N]:0<p_{k}\}$; by claim 1 applied to $\mathcal{A}'$, $0<q_{k}$ for $k\in P$, and $h_{\mathcal{A}'}(\nu\,|\,\gamma)$ is defined. Moreover $P$ is nonempty and $\sum_{k\in P}p_{k}=\sum_{k=1}^{N}p_{k}=1$, as recorded in the preamble of The Partition Entropy of a Probability Measure Relative to Another over a Finite Measurable Partition.

Claim 4, Step 3 (A step function). Let $s=\sum_{k=1}^{N}a_{k}\mathbf{1}_{E_{k}}$, measurable by claims 1 and 2 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions. At $x\in E_{k}$ one has $s(x)=a_{k}$ and $\exp(s(x))=\exp(a_{k})$, since the other indicators vanish there; hence $\exp\circ s=\sum_{k=1}^{N}\exp(a_{k})\mathbf{1}_{E_{k}}$, and $w(x)\le s(x)<w(x)+\delta$ because $a_{k}-\delta=a_{k-1}<w(x)\le a_{k}$. In particular $|s|\le M+\delta$, so $s$ is bounded measurable.

Claim 4, Step 4 ($\Lambda^{\gamma}_{s}(\nu)\ge\Lambda^{\gamma}_{w}(\nu)-\delta$). By Relative Entropy on a Measurable Space: the Gibbs Inequality, the Variational Criterion and Formula, the Entropy Inequality, Small Sets and Data Processing §functional, $w$ and $s$ are integrable with respect to $\nu$, $\exp\circ w$ and $\exp\circ s$ are bounded measurable, hence integrable with respect to $\gamma$, and $Z_{w}=\int_{S}\exp\circ w\,d\gamma$ and $Z_{s}=\int_{S}\exp\circ s\,d\gamma$ are positive. Since $w\le s$, the monotonicity in Linearity and Monotonicity of the Lebesgue Integral §integrable gives $\int_{S}w\,d\nu\le\int_{S}s\,d\nu$. Since $s<w+\delta$, claims 4 and 1 of Basic Properties of the Exponential Function give $\exp\circ s\le\exp(\delta)\,(\exp\circ w)$ pointwise, so $Z_{s}\le\exp(\delta)Z_{w}$ by Linearity and Monotonicity of the Lebesgue Integral §integrable; as $\log$ is increasing, $\log Z_{s}\le\log(\exp(\delta)Z_{w})=\delta+\log Z_{w}$. Therefore

$$\Lambda^{\gamma}_{s}(\nu)=\int_{S}s\,d\nu-\log Z_{s}\ge\int_{S}w\,d\nu-\log Z_{w}-\delta=\Lambda^{\gamma}_{w}(\nu)-\delta>H(\nu\,|\,\gamma)-2\delta=H(\nu\,|\,\gamma)-\varepsilon .$$

Claim 4, Step 5 (Finite Gibbs inequality). By The Integral of an Indicator Function is the Measure of the Set each $\mathbf{1}_{E_{k}}$ has integral $p_{k}$ with respect to $\nu$ and $q_{k}$ with respect to $\gamma$, both finite, so it is integrable with these integrals; by Linearity and Monotonicity of the Lebesgue Integral §integrable and Step 3, $\int_{S}s\,d\nu=\sum_{k=1}^{N}a_{k}p_{k}$ and $Z_{s}=\sum_{k=1}^{N}\exp(a_{k})q_{k}$. In the first sum the terms with $k\notin P$ vanish, so $\int_{S}s\,d\nu=\sum_{k\in P}a_{k}p_{k}$ by claim 1 of Properties of a Sum over a Finite Index Set and Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §vanishing, $P$ being nonempty. The second sum dominates $\sum_{k\in P}\exp(a_{k})q_{k}$: it equals it if $P=[N]$, and otherwise Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §disjoint-union splits it into that sum plus the sum of the nonnegative terms with $k\in[N]\setminus P$. For $k\in P$ put $u_{k}=\frac{q_{k}\exp(a_{k})}{p_{k}Z_{s}}$, a positive real number with $\log u_{k}=a_{k}-\log Z_{s}-\log(p_{k}/q_{k})$, using $\log(\exp(a_{k}))=a_{k}$. Using $\sum_{k\in P}p_{k}=1$ and $\log u_{k}\le u_{k}-1$,

$$\Lambda^{\gamma}_{s}(\nu)-h_{\mathcal{A}'}(\nu\,|\,\gamma)=\sum_{k\in P}p_{k}\log u_{k}\le\sum_{k\in P}p_{k}(u_{k}-1)=\frac{1}{Z_{s}}\sum_{k\in P}q_{k}\exp(a_{k})-1\le0 .$$

Combining with Step 4, $H(\nu\,|\,\gamma)-\varepsilon<\Lambda^{\gamma}_{s}(\nu)\le h_{\mathcal{A}'}(\nu\,|\,\gamma)$, which proves claim 4.