I am trying to understand if the following claim is true:



> 
> Let $P$, $Q$ be probability measures on $\mathcal{X}$. For any $\sigma$-algebra $\mathcal{G}$, with countably many atoms (sets with $\emptyset$ as their only subset in $\mathcal{G}$), let
> $$D(P||Q|\mathcal{G}) = \sum\_{A\in atom(\mathcal{G})} P(A)\log\frac{P(A)}{Q(A)}.$$
> Then for any $\sigma$-algebra $\mathcal{H} \subset \mathcal{G}$ we have $D(P||Q|\mathcal{H}) \leq D(P||Q|\mathcal{G})$.
> 
> 
> 


First of all, I think there should be some assumption regarding the measurability of atoms of $\mathcal{G}$ with respect to $P$ and $Q$.


Apart from that, I cannot see why the inequality would necessarily holds. To build a counterexample, let $\lambda$ be the counting measure on $\{0\}$ and let $(\mathcal{Y},\mathcal{F},\mu)$ be a probability space with an atomless $\sigma$-algebra. For $\alpha\in[0,1]$, There is a probability space on $\mathcal{X} = Y\cup \{0\}$ with probability measure $a\mu' + (1-a)\lambda'$, where the prime measures act as $\mu'(A) = \mu(A\cap \mathcal{Y})$ and $\lambda'(A) = \lambda(A\cap \{0\})$. Take $\mathcal{G}$ to be the $\sigma$-algebra generated in $\mathcal{X}$ by $\mathcal{F}$ and let $\mathcal{H} = \{\emptyset,\mathcal{Y},\{0\},\mathcal{X}\}$. Now $\mathcal{H} \subset \mathcal{G}$ and they both contain finitely many atoms, but we have
$$D\left(\frac{1}{2}\mu' + \frac{1}{2}\lambda'||a\mu' + (1-a)\lambda'|\mathcal{G}\right) - D\left(\frac{1}{2}\mu' + \frac{1}{2}\lambda'||a\mu' + (1-a)\lambda'|\mathcal{H}\right) = -\frac{1}{2}\log\left(\frac{a}{2}\right)$$
which is $\leq0$ as long as $a\geq$2.


Having said that, if I assume $\mathcal{X} = \cup atom(\mathcal{G})$ in the original statement, this argument would collapse and the inequality could hold.


Is there a flaw in my argument? I have assumed the existence of measures with various properties (most notably a probability measure with an atomless sigma algebra), but if I remember my measure theoretic basics correctly, all of these existences can be proven.



KL-divergence and sub-$\sigma$-algebras
$\newcommand{\G}{\mathcal G}\newcommand{\HH}{\mathcal H}\newcommand{\A}{\mathcal A}\newcommand{\X}{\mathcal X}$First here, a *nonempty* member $A$ of a sigma-algebra $\G$ is an atom of $\G$ if the only *proper* subset of $A$ in $\G$ is empty.


Let now $\A(\G)$ denote the set of all atoms of $\G$. Without the condition
\begin{equation\*}
 \X=\cup\A(\G),\tag{1}
\end{equation\*}
it is of course easy to construct counterexamples to the inequality
\begin{equation\*}
 D(P||Q|\HH)\le D(P||Q|\G),\tag{2}
\end{equation\*}
as was done in your post.


On the other hand, assuming that (1) holds and that $\A(\G)$ is (at most) countable, inequality (2) holds. Indeed, then every atom $B$ of $\HH$ is a disjoint countable union of atoms of $\G$:
\begin{equation\*}
 B=\cup\A\_B(\G),
\end{equation\*}
where
\begin{equation\*}
 \A\_B(\G):=\{A\in\A(\G)\colon A\subseteq B\}. 
\end{equation\*}
So,
\begin{align\*}
 D(P||Q|\G)&=\sum\_{A\in\A(\G)}P(A)\log\frac{P(A)}{Q(A)} \\ 
 &=\sum\_{B\in\A(\HH)}\sum\_{A\in\A\_B(\G)}P(A)\log\frac{P(A)}{Q(A)}, 
\end{align\*}
\begin{align\*}
 D(P||Q|\HH)&=\sum\_{B\in\A(\HH)}P(B)\log\frac{P(B)}{Q(B)} \\ 
& =\sum\_{B\in\A(\HH)}\sum\_{A\in\A\_B(\G)}P(A)\log\frac{P(B)}{Q(B)}, 
\end{align\*}
\begin{align\*}
 D(P||Q|\G)-D(P||Q|\HH)
 &=\sum\_{B\in\A(\HH)}\sum\_{A\in\A\_B(\G)}P(A)\log\frac{P(A|B)}{Q(A|B)} \\ 
 &=\sum\_{B\in\A(\HH)}P(B)\sum\_{A\in\A\_B(\G)}P(A|B)\log\frac{P(A|B)}{Q(A|B)} \\ 
 &=\sum\_{B\in\A(\HH)}P(B)D\big(P(\cdot|B)||Q(\cdot|B)\big)\ge0, 
\end{align\*}
since $D\big(P(\cdot|B)||Q(\cdot|B)\big):=\sum\_{A\in\A\_B(\G)}P(A|B)\log\frac{P(A|B)}{Q(A|B)}\ge0$.


Thus, (2) holds.


