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



How much can KL divergence decrease by diluting the reference distribution
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}$. 


