# Weak continuity of K-L divergence function

If $P_n$ and $Q_n$ are two pmf's of a discrete set (say $A$) with common support and $P_n \to P$ and $Q_n \to Q$ where the convergence is pointwise here (even weak would be fine here I guess), then $$D(P_n\|Q_n) \to D(P\|Q)$$ follows from continuity and the fact that it is a finite sum. To recall, for finite/countable sets, KL Divergence is given by $$D(P\|Q) = \sum_{k=1}^{|A|}P(k)\log_2\left(\frac{P(k)}{Q(k)}\right)$$

Now for uncountable sets, one would use a slightly different definition of divergence (if $A$ here were uncountable but a measurable space with a Borel Sigma algebra). For any two measures $P$ and $Q$ on $A$ where $P \ll Q$ ($P$ is absolutely continuous wrt $Q$), we have $$D(P\|Q) = \int_A \frac{dP}{dQ}\log\left(\frac{dP}{dQ}\right)dQ$$ where $\frac{dP}{dQ}$ is the Radon Nikodym derivative of $P$ wrt $Q$. My question is, Suppose $P_n \to^w P$ and $Q_n \to^w Q$, and $P_n \ll Q_n ~ \forall n$, does it follow that $$D(P_n\|Q_n) \to D(P\|Q)$$ ? (Here "$\to^w$" denotes weak convergence).

My attempt: My guess was that it would not hold every time but in certain cases. To characterize them, I started with understanding $D(P_n\|Q)$. This is simply $$D(P_n\|Q) = \int_A \frac{dP_n}{dQ}\log\left(\frac{dP_n}{dQ}\right)dQ$$. Only now I am not sure how to show $\frac{dP_n}{dQ} \to \frac{dP}{dQ} ~ a.e$

Source and References: While one would encounter these terms in any good information theory book, I would recommend Csiszar and Korner "Coding theorems for discrete memoryless systems". There are also quite a few papers that deal with this kind of divergence. However the source of the problem is not from these books but was on a research problem I was tackling years back and am now revisiting.

Hence I appreciate ideas and tips on proceeding rather than outright answers. Feel free to request further clarification.

Update1: I had mentioned above that $P \ll Q$. If it helps we may also let $Q \ll P$.

• Question has been downvoted. Is something wrong? Jul 3, 2015 at 6:18
• I think, in general, all one can have is lower semi-continuity (lsc). For a proof of lsc, see, for example, Theorem 1 of the paper "Random Coding Strategies for Minimum Entropy" by Edward C. Posner appeared in IT Transactions Jul 25, 2015 at 12:56
• This might also be useful: mathoverflow.net/questions/84531/… Jul 25, 2015 at 12:58

@Ashok comment resolved this completely, so I am rewriting it as an answer. Posner, "Random Coding Strategies for Minimum Entropy", IEEE Trans Info Theory, 1975 showed that KL divergence is lower-semicontinuous in the topology of weak convergence. In particular, if $$P_n \to P$$ and $$Q_n \to Q$$ weakly, then $$\lim_n D(P_n\Vert Q_n) \ge D(P\Vert Q)$$. A very nice summary is provided in the excellent Y. Polyanskiy, Y. Wu, "Lecture notes on Information Theory" (see Theorem 3.6)
Note that the first claim in your question is incorrect: it is not the case that $$\lim_n D(P_n \Vert Q_n) = D(P\Vert Q)$$ for all countable/discrete alphabets, even if all the distributions have the same support, because the continuity property you state only holds for finite alphabets. Here is a counterexample.
Let $$P(i)=\frac{1}{Z}e^{-i^2}$$, where $$Z=\sum_{i=1}^\infty e^{-i^2}$$ is finite normalization constant, and let $$P=Q=Q_n$$, so that $$D(P\Vert Q)=0$$. Let $$\alpha_n=\sum_{i=1}^n P(i)$$ indicate partial sums, and define $$P_n$$ in the following manner: \begin{align} P_n(i) = \begin{cases} (1-n^{-2}) P(i) & \text{for i\in\{1,\dots,n-1\}}\\ 1-(1-n^{-2})\alpha_{n-1} & \text{for i=n}\\ 0 & \text{otherwise} \end{cases} \end{align} It is easy to see that $$P_n$$ is a valid probability distribution and that $$P_n \to P$$ in total variation, hence also in the topology of weak convergence. Now write $$D(P_n\Vert Q_n)=D(P_n\Vert P)=\alpha_{n-1}(1-n^{-2})\ln(1-n^{-2})+P_n(n)\ln\frac{P_n(n)}{P(n)}.$$ Since $$\lim_{n} \alpha_{n-1}=1$$ and $$\lim_n (1-n^{-2})\ln(1-n^{-2})=0$$, \begin{align} \lim_n D(P_n\Vert Q_n) &= \lim_n P_n(n)\ln\frac{P_n(n)}{P(n)}\\ &= \lim_n -P_n(n)\ln{P(n)}\\ &=\lim_n P_n(n)(n^2 + \ln Z)= \lim_n \frac{P_n(n)}{n^{-2}} \end{align} where we used that $$\lim_n P_n(n)=0$$ and the definition of $$P(n)$$. Finally, a simple application of L'Hospital's rule shows that $$\lim_n P_n(n)/n^{-2}=1$$. Combining gives $$\lim_n D(P_n\Vert Q_n) =1 > 0 = D(P\Vert Q).$$