9
$\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$

2 Answers 2

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, 2011 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, 2011 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, 2011 at 13:45
  • $\begingroup$ Ashok, I found the paper, man thanks. Michele $\endgroup$
    – Michele
    Dec 30, 2011 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, 2011 at 20:59
  • $\begingroup$ Couldn't find a proof of lower semicontinuity in Cover & Thomas. $\endgroup$
    – Shlomi A
    Nov 23, 2020 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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