# Does small expected value of a random variable show the small probability for its tail?

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.

• 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? Nov 10, 2016 at 19:32
• Yes, that's exactly what I meant. Nov 10, 2016 at 19:51
• 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. Nov 10, 2016 at 20:57

Set $g(\epsilon)=\sqrt\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\epsilon$. That is $p_iq_j<p_{ij}-\sqrt\epsilon p_{ij}$, which implies $|p_iq_j-p_{ij}|>\sqrt\epsilon p_{ij}$. Hence if $(i,j)\in \Lambda_\epsilon$, then $p_{ij}<1/\sqrt\epsilon |p_iq_j-p_{ij}|$.