11
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Question has been downvoted. Is something wrong? $\endgroup$ Jul 3, 2015 at 6:18
  • 2
    $\begingroup$ 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 $\endgroup$
    – Ashok
    Jul 25, 2015 at 12:56
  • $\begingroup$ This might also be useful: mathoverflow.net/questions/84531/… $\endgroup$
    – Ashok
    Jul 25, 2015 at 12:58

1 Answer 1

6
$\begingroup$

@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).$$

$\endgroup$
1
  • $\begingroup$ Thanks. Looks like I completely missed that. I will accept your solution. $\endgroup$ Mar 20, 2021 at 17:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .