Welcome to Randal Douc's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== The Pinsker Inequality. ======

{{page>:defs}}


{{tag> Pinsker_inequality }}

===== What? =====

The inequality is the following: 
<WRAP center round box 80%> __The Pinsker inequality__. 
For all probability measures $\sigma$, $\pi$, 
$$ 
 |\int f (\rmd \sigma-\rmd \pi)|^2\leq 2 \Var_{\mu}(f) KL(\sigma|| \pi) 
$$
where $\mu$ is the probability measure $\mu=2\pi/3+\sigma/3$. 
</WRAP>
 
If $0\leq f\leq 1$, then $\Var_{\mu}(f)=\PE[f^2]-\PE^2[f]\leq \PE[f]-\PE^2[f]=\PE[f](1-\PE[f]) \leq 1/4$ and we get 
$$
\rmd_{tv}^2(\sigma,\pi) \leq  KL(\sigma|| \pi)/2
$$
===== The proof =====

$\bproof$ Here are the main ideas. For simplicity, we assume $\sigma(x)>0$ for all $x$. First note that for all $y> 0$,

<WRAP center round tip 60%>

 \begin{equation} (y-1)^2 \leq \frac{2}{3}(2y+1) (-\log y +y-1) \quad (\star) \end{equation}

</WRAP>

Indeed, set $h(y)=\frac{2}{3}(2y+1)(-\log y+y-1)-(y-1)^2$ and check that $h(1)=h'(1)=0$ and $h''(y)=2(y-1)^2/(3y^2)>0$ for all $y \geq 0$. Therefore, $h$ is a convex function on $\rset^+$ and attains its minimum at $y=1$. Therefore, $h(y) \geq 0$ for all $y\geq 0$, which proves $(\star)$. Then, using $(\star)$ with $y=\frac{\pi(x)}{\sigma(x)}$, and taking $\bar f=f-\mu(f)$ where $\mu=2\pi/3 +\sigma/3$,

\begin{align*} 
|\int f (\rmd \sigma-\rmd \pi)|^2=|\int \bar f (\rmd \sigma-\rmd \pi)|^2 &\leq 
\left(\int  |\bar f(x)|\ |\sigma(x)-\pi(x)|\rmd x\right)^2 \\
&=\left(\int |\bar f(x)|\ \sigma(x)\ |\frac{\pi(x)}{\sigma(x)}-1|\rmd x\right)^2 \\ 
&\leq\left(\int \sigma(\rmd x) \sqrt{\frac{2\bar f^2(x)}{3}\left(2\frac{\pi(x)}{\sigma(x)}+1\right)} \sqrt{\left( -\log \frac{\pi(x)}{\sigma(x)}
+\frac{\pi(x)}{\sigma(x)}-1\right)}\right)^2 \end{align*} And we conclude by applying Holder's inequality: $\left(\int \sigma(\rmd x) \sqrt{a(x)}\sqrt{b(x)} \right)^2\leq \int \sigma(\rmd x) a(x) \times \int \sigma(\rmd x) b(x)$ $\eproof$
Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools
