Assume you have a finite, discrete probability distribution for a joint random variable and such that $P(X=i,Y=j) = p_{i,j}$ for $i \in \{1, \dots, |X|\},j \in \{1, \dots, |Y|\}$. The marginal distributions are given by $Prob(X=i) = p_i = \sum_{j=1}^{|Y|} p_{i,j}$ and similarly $Prob(Y=j) = q_j = \sum_{i=1}^{|X|} p_{i,j}$ for the other marginal.

**I would like to get a "good" upper bound in terms of the mutual information for the following expression:**
$$
\sum_{i,j} (p_{i,j} - p_i q_j) \log(p_i) \log(q_j).
$$

Now, I can do $$ \sum_{i,j} (p_{i,j} - p_i q_j) \log(p_i) \log(q_j)\\ \leq |\sum_{i,j} (p_{i,j} - p_i q_j) \log(p_i) \log(q_j)| \\ \leq \sum_{i,j} | p_{i,j} - p_i q_j|| \log(p_i)|| \log(q_j)| \\ \leq \sum_{i,j} | p_{i,j} - p_i q_j |\max_{i,j}|\log(p_i)|| \log(q_j)| \\ = ||P_{XY} - P_{X}P_{Y}||_1|\log( \min_i p_i)|| \log( \min_j q_j)| \\ \leq \sqrt{2I(X:Y)}|\log( \min_i p_i)|| \log( \min_j q_j)| $$ where $I(X:Y)$ denotes the mutual information and where I used the triangle inequality and Pinsker's inequality. Note that I can assume without loss of generality that $p_{i},q_j > 0$ for all $i,j$ since zero terms simply disappear from the original sum (taking $0\log0=0$).

However, this bound is not good enough for my purposes. I need a bound that cannot be made arbitrarily large simply by decreasing the smallest (non-positive) marginal probability. **Instead, I'm looking for a bound of the form $M\sqrt{I(X:Y)}\log(|X|)\log(|Y|)$ for some $M \in \mathbb{N}$.**

10more comments