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$ – Anthony Quas Nov 10 '16 at 19:32
  • $\begingroup$ Yes, that's exactly what I meant. $\endgroup$ – Math_Y Nov 10 '16 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$ – Anthony Quas Nov 10 '16 at 20:57

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, privacy policy and cookie policy

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