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

Question

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.

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*}