Does bounding mutual information restrict the defined meter?

Question

Suppose $I(X;Y)$ denotes mutual information and on the other hand there is a relationship as follows. \begin{align} |p(y)-p(y|x)|<\delta p(y),\qquad\forall x,y. \end{align} Then we can say about mutual information: \begin{align} I(X;Y)=\sum_{x,y}p(x,y)\log\frac{p(y|x)}{p(y)}\leq\sum_{x,y}p(x,y)\log\frac{(1+\delta)p(y)}{p(y)}=\log(1+\delta)\leq\delta. \end{align} Is the opposite true? That is, if mutual information is less than $\epsilon$, can it be said that there is a $\delta$ in which first relationship is established?

Answer 1

$\newcommand\ep\varepsilon$Of course not.

E.g., suppose that $P(X=0,Y=0)=t\ep$, $P(X=0,Y=1)=1/2-t\ep$, $P(X=1,Y=0)=(1-t)\ep$, and $P(X=1,Y=1)=1/2-(1-t)\ep$, where $t$ and $\ep$ are in the interval $(0,1)$. Then $$I(X;Y)\sim c_t\ep\to0$$ as $\ep\downarrow0$, where $c_t:=\ln2+t\ln t+(1-t)\ln(1-t)$.

However, here $P(Y=0|X=0)=2t\ep$, which is not relatively close to $P(Y=0)=\ep$ if (say) $t=1/4$. (Or you can let $t\downarrow0$; then $c_t\to\ln2$.)

---

The idea of this counterexample is quite simple: it is to let the conditional probability mass function (pmf) of $Y$ given $X$ differ substantially from its unconditional pmf only on a set of values rather unlikely to be taken by $Y$. This will affect the mutual information only little.