Do there exist functions $g(\epsilon)$ and $h(\epsilon)$ defined for $\epsilon>0$ such that $g(\epsilon)\to 0$ and $h(\epsilon)\to 0$ as $\epsilon\to 0^+$ with the following property:

If $X$ and $Y$ are random variables with joint pmf $p(X,Y)$ satisfying $$\mathbb{I}(X;Y)=\mathbb{E}_{X,Y}\left(\log\frac{p(X,Y)}{p(X)\cdot p(Y)}\right)\leq\epsilon,$$ then $\mathbb P(\Lambda_\epsilon)<h(\epsilon)$, where $$\Lambda_\epsilon:=\left\{(x,y):\frac{p(y)}{p(y|x)}\leq1-g(\epsilon)\right\}$$

First, I do a wrong analysis with $g(\epsilon)=1-e^{-\sqrt{\epsilon}}$ as follows: \begin{align} \mathbb{P}(\Lambda)&=\mathbb{P}\left(\frac{p(Y)}{p(Y|X)}\leq 1-g(\epsilon)\right)\nonumber\\ &=\mathbb{P}\left(\log\frac{p(Y)}{p(Y|X)}\leq \log (1-g(\epsilon))\right)\nonumber\\ &=\mathbb{P}\left(\log\frac{p(Y|X)}{p(Y)}\geq \log\frac{1}{1-g(\epsilon)}\right)\nonumber\\ &\overset{(a)}{\leq}\frac{\epsilon}{\log\frac{1}{1-g(\epsilon)}}=\sqrt{\epsilon}. \end{align} where $(a)$ comes from Markov inequality. This analysis is wrong because Markov inequality is correct only for non-negative random variables and $\log\frac{p(Y|X)}{p(Y)}$ is not necessarily non-negative. In addition, maybe Pinsker inequality could help you: $$\frac{1}{2}\lVert p(x,y)-p(x)p(y)\rVert_1^2\leq I(X;Y)\leq\epsilon$$ where $\lVert.\rVert_1$ denotes total variation distance.

  • $\begingroup$ I think the question you are asking is this: Do there exist positive functions $g(\epsilon)$ and $h(\epsilon)$, both converging to 0 as $\epsilon\to 0^+$ such that $\Bbb I(X;Y)<\epsilon$ implies $\Bbb P(\{(x,y)\colon p(y)/p(y|x)\le 1-g(\epsilon)\})\le h(\epsilon)$. Is this right? $\endgroup$ Nov 10, 2016 at 19:32
  • $\begingroup$ Yes, that's exactly what I meant. $\endgroup$
    – Math_Y
    Nov 10, 2016 at 19:51
  • $\begingroup$ OK. I'll edit the question to reflect this, because as it's written, all of the quantities are fixed numbers once the $X$ and $Y$ are fixed. $\endgroup$ Nov 10, 2016 at 20:57

1 Answer 1


So you can recover what you want directly from the Pinsker inequality.

Set $g(\epsilon)=\sqrt[4]\epsilon$. Let $p_{ij}=\mathbb P(X=i,Y=j)$, $p_i=\mathbb P(X=i)$ and $q_j=\mathbb P(Y=j)$.

Then $$ \mathbb P(\Lambda_\epsilon)=\sum_{(i,j)\in\Lambda_\epsilon}p_{i,j}. $$ If $(i,j)\in\Lambda_\epsilon$, then $p_iq_j/p_{ij}<1-\sqrt[4]\epsilon$. That is $p_iq_j<p_{ij}-\sqrt[4]\epsilon p_{ij}$, which implies $|p_iq_j-p_{ij}|>\sqrt[4]\epsilon p_{ij}$. Hence if $(i,j)\in \Lambda_\epsilon$, then $p_{ij}<1/\sqrt[4]\epsilon |p_iq_j-p_{ij}|$.

Now \begin{align*} \mathbb P(\Lambda_\epsilon)&=\sum_{(i,j)\in\Lambda_\epsilon}p_{ij}\\ &<\frac 1{\sqrt[4]\epsilon}\sum_{(i,j)\in\Lambda_\epsilon}|p_iq_j-p_{ij}|\\ &<\frac 1{\sqrt[4]\epsilon}\sum_{i,j}|p_iq_j-p_{ij}|\\ &=\epsilon^{-1/4}\|p_iq_j-p_{ij}\|_1<\epsilon^{-1/4}\sqrt{2\epsilon}=\sqrt 2\epsilon^{1/4}. \end{align*}


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.