# Bound for type of correlation measure

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

• Numerical experiments indicate that a bound of the form $\sqrt{I(X:Y)}\log(|X|\cdot|Y|)$ might be plausible. Would that be good enough? Feb 8 '19 at 12:29
• @AryehKontorovich, thanks. The kind of community I'm addressing would expect an analytical derivation I'm afraid. The crucial difficulty I think is that one has to make explicit use of the relationship between p_{ij} and the marginals, since the above bound for generic random probability vectors does not hold.
– Paul
Feb 8 '19 at 12:37
• Of course we'd want a rigorous proof! I was asking if the bound of the type I proposed is sufficiently good for your purposes. What motivates this question, btw? Feb 8 '19 at 12:39
• It's definitely false if your replace $\sqrt{I(X:Y)}$ by $I(X:Y)$ -- I can provide easy examples. Feb 8 '19 at 12:40
• @AryehKontorovich, sorry, I misunderstood. Yes, the bound from your first comment would be good enough.
– Paul
Feb 8 '19 at 12:53

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.

• Hey Artemy, thanks a lot for your answer (and sorry about the late reply). That's a very nice trick, to split into two square roots, thereby making cauchy schwarz work good enough. I also don't know how to improve on the bound on the second term to yield the calsing that I originally asked for, but in fact, your result is good enough for the purpose of my paper
– Paul
Apr 8 '19 at 10:00
• So, in terms of the MathOverflow rules, since you don't answer my original question but do solve the problem sufficiently well for me, does this mean I should accept your reply as an answer or not? I could wait another week or so, and then accept.
– Paul
Apr 8 '19 at 10:01
• Also, if this result does end up in the paper, I would like to acknowledge you. If you're interested in this, I could either acknowledge your Stack-Overflow account or the real "you". If you prefer the latter, feel free to drop me a message in chat. I'd acknowledge mathoverflow and this thread in either case.
– Paul
Apr 8 '19 at 10:04
• Great. Yes I would prefer to be acknowledged. Sorry I am not too familiar with the chat system, if it's OK with you I will send you an email. Apr 8 '19 at 17:56