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.

  • $\begingroup$ 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. $\endgroup$
    – kodlu
    Commented Mar 6, 2015 at 2:32
  • $\begingroup$ @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. $\endgroup$
    – SAmath
    Commented Mar 6, 2015 at 23:35
  • $\begingroup$ @SAmath, have you found an answer to this question after all? $\endgroup$
    – odea
    Commented Jul 28, 2018 at 23:31
  • $\begingroup$ 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$$. $\endgroup$
    – Clement C.
    Commented Oct 21, 2018 at 21:38

2 Answers 2


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 $$

  • 1
    $\begingroup$ 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. $\endgroup$
    – odea
    Commented Nov 10, 2018 at 9:57

@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 Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.