8
$\begingroup$

The Kullback-Leibler Divergence (KLD) of two PMF's $P(x)$ and $Q(x)$ is $D(P||Q)=\sum_x P(x)\log(P(x)/Q(x))$, with the provisos that $0\cdot \log (0/p)=0$ and $p\cdot \log (p/0)=+\infty$ whenever $p>0$.

It is known that KLD is continuous at $(P,Q)$ if $Q$ is strictly positive over all $x$'s. What can be said otherwise?

To be more specific, assume we are given a sequence of PMF $\{(P_n,Q_n)\}_{n\geq 0}$ s.t. $(P_n,Q_n)\rightarrow (P,Q)$ in the simplex of PFM's (with the topology induced by, say, norm-1 distance).

Is it correct to deduce that

$\lim \inf_{n\rightarrow \infty} D(P_n||Q_n) \geq D(P||Q)$ ?

This would follows if KLD is lower-semicontinuous, right?

Many thanks.

$\endgroup$
5
$\begingroup$

In addition to the conventions you have mentioned, it is also assumed that $0\log(0/0)=0$.

With these conventions, I think, in the finite case, it is always true that $$\lim_{n\to \infty} D(P_n||Q_n)=D(P||Q)$$ As you said, if $Q(x)>0$ for all $x$, its immediate from the Dominated Convergence theorem. The problem is only when for some $y$, $Q(y)=0$ whereas $P(y)>0$.

In which case $P(y)\log(P(y)/Q(y))=\infty$ and $D(P\|Q)=\infty$

But since $(P_n,Q_n)\to (P,Q)$, we have $P_n(y)\to P(y)$ and $Q_n(y)\to Q(y)$, whence $$P_n(y)\log(P_n(y)/Q_n(y))\to P(y)\log(P(y)/Q(y))=\infty.$$ Hence $D(P_n||Q_n)\to \infty$

So in any case we have $\lim_{n\to \infty} D(P_n||Q_n)=D(P||Q)$.

In a general measurable space (i.e., if $P_n, Q_n, P, Q$ are probability measures on some general measure space say $(\mathbb{X}, \mathcal{X})$), I think, we have only lower semicontinuity.

Pardon me, if something is wrong.

$\endgroup$
4
  • $\begingroup$ Surely it is not always the case that if $(P_n,Q_n)\rightarrow (P,Q)$ then $\lim_{n\rightarrow \infty} D(P_n||Q_n)= D(P||Q)$, as you say. If $Q$ is the frontier of the PMF simplex (that is, $Q(x)=0$ for some $x$), consider a sequence $(P_n,Q_n)$ with $Q_n=Q$ and $P_n\rightarrow P$, where $P(x)=0$ whenever $Q(x)=0$. Moreover, assume all the $P_n$'s are in the interior of the simplex, that is they are all strictly positive on every $x$. Then, for each $n$, $D(P_n||Q_n)=+\infty$, hence $\lim_{n\rightarrow \infty} D(P_n||Q_n)=+\infty$, whereas $D(P||Q)<+\infty$. $\endgroup$
    – Michele
    Dec 30 '11 at 12:49
  • $\begingroup$ Yes Michele, you are right. My proof would not work in the case you have stated. But I am sure that its lower semi continuous. $\endgroup$
    – Ashok
    Dec 30 '11 at 13:27
  • $\begingroup$ For example, you can find a proof in the paper (see section III) titled "Random coding strategies for minimum entropy" published in IT Transactions. $\endgroup$
    – Ashok
    Dec 30 '11 at 13:45
  • $\begingroup$ Ashok, I found the paper, man thanks. Michele $\endgroup$
    – Michele
    Dec 30 '11 at 13:55
2
$\begingroup$

I believe that the lower semicontinuity of KBD is proved in Cover-Thomas Information Theory book. Also in Kullback's information theory book.

$\endgroup$
2
  • $\begingroup$ why the down-vote? $\endgroup$ Dec 29 '11 at 20:59
  • $\begingroup$ Couldn't find a proof of lower semicontinuity in Cover & Thomas. $\endgroup$
    – Shlomi A
    Nov 23 '20 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.