How much can KL divergence decrease by diluting the reference distribution

Question

Let $\Omega$ be a countable set and $\mu,\nu\colon\Omega\to[0,1]$ be distributions on $\Omega$, that is we have $\sum_{x\in\Omega}\mu(x)=1$ and likewise for $\nu$. The Kullback-Leibler divergence of $\mu$ from $\nu$ is given by \begin{align*} {\mathbf D}(\mu\,\|\,\nu):=\sum_{x\in\Omega}\mu(x)\log\frac{\mu(x)}{\nu(x)}. \end{align*}

I am interested in lower bounding quantities of the form ${\mathbf D}(\mu\,\|\,\epsilon\mu+(1-\epsilon)\nu)$ for some $\epsilon\in[0,1]$. What are the keywords to search for such expressions in the literature? I was guessing 'hypothesis testing' would take me there, but to no avail so far.

I am guessing something like the following should hold \begin{align*} {\mathbf D}(\mu\,\|\,\epsilon\mu+(1-\epsilon)\nu) \geq \frac{1}{2} {\mathbf D}(\mu\,\|\,\nu) \end{align*} whenever $\epsilon < 2^{-10({\mathbf D}(\mu\,\|\,\nu)+1)}$.

In words, if $\mu$ is not too divergent from $\nu$ then diluting $\nu$ a little should not decrease the divergence more than a constant factor.

Please let me know if this has been studied somewhere, has a name, or related to well known principles, or false.

Thanks

Answer 1

Your conjecture is incorrect. Let $\sum:=\sum_{x\in\Omega}$, \begin{equation*} f:=\mu/\nu,\quad t:=\epsilon, \end{equation*} \begin{equation*} G(z):=z\ln\frac z{(1-t+t z)^2}. \end{equation*} Then \begin{equation*} 2{\mathbf D}(\mu\,\|\,\epsilon\mu+(1-\epsilon)\nu)-{\mathbf D}(\mu\,\|\,\nu) =\sum\nu(x)G(f(x))=:\sum\nu G(f). \end{equation*} So, the conjecture can be restated as follows: $\sum\nu G(f)\ge0$ if ${\mathbf D}(\mu\,\|\,\nu)$ is less than a certain bound depending on $t$, which latter is a small enough positive number.

Let us show that no upper bound on ${\mathbf D}(\mu\,\|\,\nu)$, however small, will do. Namely, we shall show that for any real $d>0$, any $t\in(0,1/2)$, and any (say finite) set $\Omega$ of cardinality $\ge2$ there are probability measures $\mu$ and $\nu$ on $\Omega$ such that ${\mathbf D}(\mu\,\|\,\nu)<d$ while $\sum\nu G(f)<0$.

Indeed, without loss of generality $\Omega=\{0,1\}$. Take any real $d>0$ and any $t\in(0,1/2)$. Then $G(z)<0$ if $0<z<1$ or $z>z_t:=(\frac{1-t}t)^2>1$. Take any real $v>z_t\vee e^d>1$. Then \begin{equation} q:=\frac d{v\ln v}\in(0,1),\quad qv\in(0,1), \end{equation} \begin{equation} p:=1-q\in(0,1),\quad u:=\frac{1-qv}{1-q}\in(0,1), \end{equation} \begin{equation} p+q=1,\quad pu+qv=1, \end{equation} \begin{equation} G(u)<0,\quad G(v)<0. \end{equation}

Let now \begin{equation} \nu(\{0\}):=p,\quad \nu(\{1\}):=q,\quad \mu(\{0\}):=pu,\quad \mu(\{1\}):=qv. \end{equation} Then $\nu$ and $\mu$ are probability measures on $\Omega=\{0,1\}$, such that for $f=\mu/\nu$ one has $f(\{0\})=u$, $f(\{1\})=v$, and $G(f(x))<0$ for $x\in\Omega=\{0,1\}$, whence $\sum\nu G(f)<0$. On the other hand, ${\mathbf D}(\mu\,\|\,\nu)=pu\ln u+qv\ln v<qv\ln v=d$, since $u\in(0,1)$ and $q=\frac d{v\ln v}$.