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?



Does bounding mutual information restrict the defined meter?
$\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.


