4
$\begingroup$

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

$\endgroup$
15
  • 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

2
$\begingroup$

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.

$\endgroup$
4
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.