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

  • 1
    $\begingroup$ 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? $\endgroup$ Feb 8, 2019 at 12:29
  • $\begingroup$ @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. $\endgroup$
    – Paul
    Feb 8, 2019 at 12:37
  • $\begingroup$ 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? $\endgroup$ Feb 8, 2019 at 12:39
  • $\begingroup$ It's definitely false if your replace $\sqrt{I(X:Y)}$ by $I(X:Y)$ -- I can provide easy examples. $\endgroup$ Feb 8, 2019 at 12:40
  • $\begingroup$ @AryehKontorovich, sorry, I misunderstood. Yes, the bound from your first comment would be good enough. $\endgroup$
    – Paul
    Feb 8, 2019 at 12:53

1 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.

  • $\begingroup$ 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 $\endgroup$
    – Paul
    Apr 8, 2019 at 10:00
  • $\begingroup$ 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. $\endgroup$
    – Paul
    Apr 8, 2019 at 10:01
  • $\begingroup$ 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. $\endgroup$
    – Paul
    Apr 8, 2019 at 10:04
  • $\begingroup$ 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. $\endgroup$
    – Artemy
    Apr 8, 2019 at 17:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .