# An upper bound for chi-square divergence in terms of KL divergence for general alphabets

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ defined over a general alphabet $\mathcal{X}$, if $P\ll Q$, then $$\chi ^2(P||Q):=\int_{\mathcal{X}}\Big(\frac{dP}{dQ}\Big)^2dQ$$ and $$D(P||Q):=\int_{\mathcal{X}}dP\log\frac{dP}{dQ}.$$

I am looking for an upper bound of $\chi^2(P||Q)$ in terms of $D(P||Q)$ which works wven if $\mathcal{X}$ is uncountable. What I need is a special case where $P=P_{XY}$ and $Q=P_X\times P_Y$, for two random variables with joint and product distributions are $P_{XY}$ and $P_X\times P_Y$, respectively. Noticing that in this case KL divergence is equal to the mutual information , I need an upper bound of chi-square divergence in terms of mutual information.

• Is there a corresponding result for finite alphabets? Let $d(P,Q)$ be the $\ell_1$ distance in finite alphabets. Pinsker's inequality states that $$d(P,Q)\leq \sqrt{2 \ln 2 D(P||Q)}$$ in this case. – kodlu Mar 6 '15 at 2:32
• @kodlu, I am talking about chi-square distance and not total variation distance. In finite alphabet it is not very hard to show that $\chi^2(P||Q)\leq \frac{1}{Q_{min}}d(P,Q)\leq \frac{1}{Q_{min}}\sqrt{2\ln 2 D(P||Q)}$ where $Q_{min}:=\min_{x\in \mathcal{X}} Q(x)$. This bounds collapse for general alphabet. – SAmath Mar 6 '15 at 23:35
• @SAmath, have you found an answer to this question after all? – odea Jul 28 '18 at 23:31
• Sorry to resuscitate this question, but the definition of $\chi^2$ seems wrong to me -- namely, there is a $-1$ term missing. With this correction, the desired inequality holds due to the inequality $$\log x \leq x-1$$. – Clement C. Oct 21 '18 at 21:38

@odea, one can see that $$\chi^2(P||Q) \leq c D(P||Q)$$ cannot hold in general by taking a two point space with $$P = \{ 1 , 0\}$$ and $$Q = \{ q, 1-q \}$$. Then $$\chi^2(P ; Q) = \frac 1 q -1$$ while $$D(P||Q) = \log \frac 1 q$$. Such a $$c$$ would need to satisfy $$c \geq \frac{x-1}{\log x}$$ for $$x \to \infty$$.
However, if one assumes that $$c=\| \frac{dP}{dQ} \|_\infty < \infty$$, one can follow the argument above with $$\log x \geq \frac{x-1}{x}$$. $$c D(P||Q) \geq \|\frac{dP}{dQ}\|_\infty \int_{\mathcal{X}} dP \left(\frac{\frac{dP}{dQ} -1 }{\frac{dP}{dQ}} \right) \geq \chi^2(P;Q).$$
Your definition of $$\chi^2$$ divergence is missing a term; namely, $$\chi^2(P\|Q) = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ} - 1\right)^2 = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1$$ (see e.g. this Wikipedia article on $$f$$-divergences).
With this in hand, recall that by concavity of the logarithm, we have $$\log x \leq x-1, \qquad \forall x >0$$ (where $$\log$$ denotes the natural logarithm), and thus \begin{align} D(P\| Q) &= \int_{\mathcal{X}} dP\log\frac{dP}{dQ}\\ &\leq \int_{\mathcal{X}} dP\left(\frac{dP}{dQ} - 1\right) \\ &= \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1 \end{align} showing that the inequality holds: $$D(P\| Q) \leq \chi^2(P\|Q)\,,\qquad \forall P\ll Q$$
• I think the question asked the bound the other way around, e.g., if there is some constant $c$ such that $\chi^2(P||Q) \leq c D(P||Q)$. This is also what I needed. – odea Nov 10 '18 at 9:57