Bounding the difference of mutual information between input-output pairs

Question

Let $X_1$ and $X_2$ be discrete random variables with distributions $p_{X_1}$ and $p_{X_2}$ such that the total variation distance between the two distributions is upper bounded by a constant $\delta$, i.e.,

$$\|p_{X_1} - p_{X_2}\|_{\rm TV} < \delta$$

Let $Y_1$ and $Y_2$ be the respective outputs of a channel with law $p_{Y|X}$ when the inputs are $X_1$ and $X_2$. Do we have any upper bound on $|I(X_1; Y_1)-I(X_2; Y_2)|$?

Answer 1

The problem is that entropy can differ arbitrarily despite a small total variation distance. Let

• $X_1 = 0$ w.prob. $1$.
• $X_2 = 0$ w.prob. $1-\delta$ and otherwise, $X_2 \sim \text{Uniform}\{1,\dots,n\}$.

Let $Y_i = X_i$ w.prob. $1$ for both $i=1,2$. Then $I(X_i,Y_i) = H(X_i)$.

In particular, $I(X_1,Y_1) = 0$ while $I(X_2,Y_2) \approx \delta \log n$.