<p>@odea, one can see that <span class="math-container">$\chi^2(P||Q) \leq c D(P||Q)$</span> cannot hold in general by taking a two point space with <span class="math-container">$P = \{ 1 , 0\}$</span> and <span class="math-container">$Q = \{ q, 1-q \}$</span>. Then <span class="math-container">$\chi^2(P ; Q) = \frac 1 q -1$</span> while <span class="math-container">$D(P||Q) = \log \frac 1 q$</span>.  Such a <span class="math-container">$c$</span> would need to satisfy <span class="math-container">$c \geq \frac{x-1}{\log x}$</span> for <span class="math-container">$x \to \infty$</span>.</p>

<p>However,  if one assumes that <span class="math-container">$c=\| \frac{dP}{dQ} \|_\infty &lt; \infty$</span>, one can follow the argument above with <span class="math-container">$\log x \geq \frac{x-1}{x}$</span>.
<span class="math-container">$$
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).
$$</span></p>

CC BY-SA 4.0
2019-09-12T17:08:12.917Z
2019-09-12T17:08:12.917Z
James Melbourne
<p>Your definition of <span class="math-container">$\chi^2$</span> divergence is missing a term; namely,
<span class="math-container">$$
\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
$$</span>
(see e.g. <a href="https://en.wikipedia.org/wiki/F-divergence" rel="noreferrer">this Wikipedia article on <span class="math-container">$f$</span>-divergences</a>).</p>

<p>With this in hand, recall that by concavity of the logarithm, we have
<span class="math-container">$$
\log x \leq x-1, \qquad \forall x &gt;0
$$</span>
(where <span class="math-container">$\log$</span> denotes the natural logarithm), and thus
<span class="math-container">$$\begin{align}
D(P\| Q) &amp;=  \int_{\mathcal{X}} dP\log\frac{dP}{dQ}\\
&amp;\leq  \int_{\mathcal{X}} dP\left(\frac{dP}{dQ} - 1\right) \\
&amp;= \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1
\end{align}$$</span>
showing that the inequality holds:
<span class="math-container">$$
D(P\| Q) \leq \chi^2(P\|Q)\,,\qquad \forall P\ll Q
$$</span></p>

CC BY-SA 4.0
2018-11-10T09:57:10.187Z
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
CC BY-SA 4.0
2018-10-22T02:35:13.337Z
2018-10-22T02:35:13.337Z
Clement C.
<p>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}.$$</p>

<p>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. </p>

CC BY-SA 3.0
2015-03-06T02:32:22.477Z
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
CC BY-SA 3.0
2015-03-06T23:35:33.030Z
@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
CC BY-SA 4.0
2018-07-28T23:31:04.947Z
@SAmath, have you found an answer to this question after all?
odea
CC BY-SA 4.0
2018-10-21T21:38:40.287Z
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.
<pr.probability><it.information-theory><st.statistics>
An upper bound for chi-square divergence in terms of KL divergence for general alphabets
SAmath
# An upper bound for chi-square divergence in terms of KL divergence for general alphabets

(Asked by: username_0 on 2015-03-05)

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.

**Tags:** pr.probability, it.information-theory, st.statistics
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: @SAmath, have you found an answer to this question after all?  
> **username_3**: 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$$.  

---

## 2 answers

### Answer by username_4 on 2019-09-12. Score: 5

@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).
$$


---

### Answer by username_3 on 2018-10-22. Score: 5

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](https://en.wikipedia.org/wiki/F-divergence)).

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

> **Comments:**
> **username_2**: 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.  

---

