Bound for type of correlation measure

Question

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}$.

Answer 1

Let $V := \sum_{ij}(p_{ij}-p_{i}q_{j})\ln p_{i}\ln q_{j}$ indicate your quantity of interest. Then, \begin{align} V &\le \sum_{ij}\left|p_{ij}-p_{i}q_{j}\right|\left|\ln p_{i}\ln q_{j}\right|\\ & = \sum_{ij}\frac{\left|p_{ij}-p_{i}q_{j}\right|}{\sqrt{p_{ij} + p_iq_i}}\left|\sqrt{p_{ij} + p_iq_i} \ln p_{i} \ln q_{j}\right| \\ & \le \sqrt{\sum_{ij}\frac{(p_{ij}-p_{i}q_{j})^2}{p_{ij}+p_iq_i}}\sqrt{\sum_{i,j} (p_{ij}+p_iq_i) \ln^2 p_{i} \ln^2 q_{j}} \tag{1} \end{align} where the last line uses Cauchy-Schwartz. The sum inside the first square root in Eq. 1 is called triangular discrimination between $p_{XY}$ and $p_X p_Y$, and can be bound as \begin{align} \Delta(p_{XY} \Vert p_X p_Y) = \sum_{ij} \frac{(p_{ij} - p_iq_j)^2}{p_{ij} + p_iq_j} \le \frac{32}{27} D_\mathrm{KL}(p_{XY} \Vert p_X p_Y) = \frac{32}{27} I(X:Y) \tag{2} \end{align} (see Tenaja, "Bounds On Triangular Discrimination, Harmonic Mean and Symmetric Chi-square Divergences", arXiv, Eq. 4.38 for the inequality).

We now upper bound the sum inside the second square root. Note that $p_{ij} \le p_i$ and $p_{ij} \le q_j$, so $p_{ij} \le \sqrt{p_i}\sqrt{q_j}$. This gives \begin{align} & \sum_{i,j} (p_{ij}+p_iq_i) \ln^2 p_{i} \ln^2 q_{j}\\ \le & \sum_{i,j} (\sqrt{p_i}\sqrt{q_i}+p_iq_i) \ln^2 p_{i} \ln^2 q_{j} \\ =& \Big(\sum_{i} \sqrt{p_i} \ln^2 p_{i} \Big)\Big(\sum_{j} \sqrt{q_j} \ln^2 q_{j} \Big) + \Big(\sum_{i} {p_i} \ln^2 p_{i} \Big)\Big(\sum_{j} {q_j} \ln^2 q_{j} \Big) \\ \le & |X||Y|\frac{16^2 + 4^2}{e^4} \tag{3} \end{align} where we use $\max_{x \in [0,1]} \sqrt{x} \ln^2 x = 16/e^2$ and $\max_{x \in [0,1]} x \ln^2 x = 4/e^2$ (e.g. can be found using Mathematica).

Combining Eqs. 1-3 gives \begin{align} V \le C \sqrt{|X|}\sqrt{|Y|} \sqrt{I(X:Y)} \end{align} where $$ C = \sqrt{\frac{32}{27}}\frac{\sqrt{272}}{e^2} \approx 2.43 $$

P.S. I realized that your question asks for a bound of the type $C \log{|X|}\log{|Y|} \sqrt{I(X:Y)}$, not $C \sqrt{|X|}\sqrt{|Y|} \sqrt{I(X:Y)}$. Not sure whether this can be derived.