Skip to main content
added 4 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

$\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*}

$\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 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*}

$\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*}

added 90 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

$\newcommand{\ep}{\epsilon}\newcommand{\de}{\delta}$The Kullback–LeiblerKullback--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), \end{equation*}\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 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$.

By the obvious convexityIn 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 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*}

$\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), \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 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$.

By the obvious convexity of $D(P\parallel Q)$ in $P$ and in $Q$, 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*}

$\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 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*}

deleted 1 character in body
Source Link
David Roberts
  • 35.4k
  • 11
  • 124
  • 349

$\newcommand{\ep}{\epsilon}\newcommand{\de}{\delta}$The Kullback--LeiblerKullback–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), \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 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$.

By the obvious convexity of $D(P\parallel Q)$ in $P$ and in $Q$, 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\p arallelQ)\le(1-t)D(P_0\parallel Q)+tD(P_1\parallel Q)=(1-t)c. \end{equation*}\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*}

$\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), \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 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$.

By the obvious convexity of $D(P\parallel Q)$ in $P$ and in $Q$, 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\p arallelQ)\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*}

$\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), \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 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$.

By the obvious convexity of $D(P\parallel Q)$ in $P$ and in $Q$, 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*}

added 168 characters in body
Source Link
Michael Hardy
  • 1
  • 12
  • 85
  • 126
Loading
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Loading