5
$\begingroup$

The following question was asked and then deleted by the post author:

Let $P$ and $Q$ be two probability distributions defined over the same space, with $KL(P \parallel Q) < \infty$. For $\epsilon > 0$, is it possible to choose an $n \in \mathbb{N}$ and a sequence of distributions $R_1, \dots, R_n$ such that $KL(P \parallel R_1) + \dots + KL(R_n \parallel Q) < \epsilon$?

Due to the strict convexity of the KL divergence in either one of its arguments (fixing the other), for each $i$ we have (assuming $R_i \neq R_{i+1}$ and $\lambda \in (0, 1)$) $$KL(R_i \parallel \lambda R_i + (1-\lambda)R_{i+1}) + KL(\lambda R_i + (1-\lambda)R_{i+1} \parallel R_{i+1}) < (1 - \lambda) KL(R_i \parallel R_{i+1}) + \lambda KL(R_i \parallel R_{i+1}) = KL(R_i \parallel R_{i+1}).$$ Therefore it would seem we can always just insert $\lambda R_i + (1-\lambda)R_{i+1}$ into the sequence of distributions, between $i$ and $i+1$, and push down the sum of the KL divergences. But maybe there are diminishing returns from repeating this procedure and there is some limit to how low you can go.

This question may be of interest for some users and is therefore being revived here, accompanied with a (positive) answer.

$\endgroup$

1 Answer 1

3
$\begingroup$

$\newcommand{\ep}{\epsilon}\newcommand{\de}{\delta}$The Kullback--Leibler (KL) divergence may be defined by the formula \begin{equation*} D(P\parallel Q):=KL(P\parallel Q):=\int p\ln\frac pq=\int q\,g(p/q), \tag{0} \end{equation*} where $P$ and $Q$ are probability measures on a measurable space; $p$ and $q$ are, respectively, densities of $P$ and $Q$ with respect to a measure $\mu$ such that $P$ and $Q$ are absolutely continuous with respect to $\mu$; $\int f:=\int f\,d\mu$; and $$g(u):=u\ln u$$ for $u\in(0,\infty)$, with $g(0):=0$ and $g(\infty):=\infty$. Here we are using the standard conventions $a/0:=\infty$ for $a>0$ and $0\times\text{anything}=\text{anything}\times0:=0$. For $\mu$, one can always take e.g. $P+Q$. It is easy to see and very well known that we always have $D(P\parallel Q)\in[0,\infty]$.

Here, it is given that \begin{equation*} c:=D(P\parallel Q)<\infty. \end{equation*} Without loss of generality $c>0$ (otherwise, there is nothing to prove). Take any $\ep\in(0,3c/2]$, so that \begin{equation*} \de:=\ep/(3c)\in(0,1/2]. \end{equation*} Take now any natural $n\ge2$ and for $j\in[n]:=\{1,\dots,n\}$ let \begin{equation*} R_j:=P_{t_j}, \end{equation*} where \begin{equation*} P_t:=(1-t)P+tQ \end{equation*} and \begin{equation*} t_j:=\de+\frac{j-1}{n-1}\,(1-2\de), \end{equation*} so that $t_1=\de\le1-\de=t_n$, $P_0=P$, $R_1=P_\de$, $R_n=P_{1-\de}$, and $P_1=Q$.

In view of (0), $D(P\parallel Q)$ is convex in $P$ (because the function $g$ is convex) and in $Q$ (because $\ln\frac pq$ is convex in $q$). So, for all $t\in[0,1]$ \begin{equation*} D(P\parallel P_t)\le(1-t)D(P\parallel P_0)+tD(P\parallel P_1)=tc \end{equation*} and \begin{equation*} D(P_t\parallel Q)\le(1-t)D(P_0\parallel Q)+tD(P_1\parallel Q)=(1-t)c. \end{equation*} So, \begin{equation*} D(P\parallel R_1)\le\ep/3,\quad D(R_n\parallel Q)\le\ep/3. \end{equation*}

To bound $D(R_j\parallel R_{j+1})$ for $j\in[n-1]$, we will use

Lemma 1: For any $s$ and $t$ in $[\de,1-\de]$, \begin{equation} D(P_s\parallel P_t)\le\frac{2(s-t)^2}\de. \end{equation}

This lemma will be proved at the end of the answer. At this point, just note that, by Lemma 1, \begin{equation} D(R_j\parallel R_{j+1})\le\frac{2(1-2\de)^2}{(n-1)^2\de} \end{equation} for $j\in[n-1]$, whence \begin{equation} D(P\parallel R_1)+D(R_1\parallel R_2)+\dots+D(R_{n-1}\parallel R_n)+D(R_n\parallel Q) \\ \le\ep/3+\frac{2(1-2\de)^2}{(n-1)\de}+\ep/3<\ep, \end{equation} as desired, if $n$ is taken to be large enough.

It remains to provide

Proof of Lemma 1: Note that $g(u)\le u-1+(u-1)^2$ for all real $u>0$. So, letting $p_t:=(1-t)p+tq$ for $t\in[0,1]$, so that $p_t$ is the density of $P_t$, we have \begin{align*} D(P_s\parallel P_t)&=\int p_t g(p_s/p_t) \\ &\le\int p_t \Big[\frac{p_s}{p_t}-1+\Big(\frac{p_s}{p_t}-1\Big)^2\Big] \\ &\le\int p_t \Big(\frac{p_s}{p_t}-1\Big)^2 \\ &=\int \frac{(p_s-p_t)^2}{p_t} \\ &=(s-t)^2\int \frac{(p-q)^2}{(1-t)p+tq} \\ &\le\frac{(s-t)^2}\de\,\int \frac{(p-q)^2}{p+q} \\ &\le\frac{(s-t)^2}\de\,\int(p+q)=\frac{2(s-t)^2}\de. \quad\Box \end{align*}

$\endgroup$

You must log in to answer this question.

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