# Bounding mutual information given bounds on pointwise mutual information

Suppose I have two sets $X$ and $Y$ and a joint probability distribution over these sets $p(x,y)$. Let $p(x)$ and $p(y)$ denote the marginal distributions over $X$ and $Y$ respectively.

The mutual information between $X$ and $Y$ is defined to be: $$I(X; Y) = \sum_{x,y}p(x,y)\cdot\log\left(\frac{p(x,y)}{p(x)p(y)}\right)$$

i.e. it is the average value of the pointwise mutual information pmi$(x,y) \equiv \log\left(\frac{p(x,y)}{p(x)p(y)}\right)$.

Suppose I know upper and lower bounds on pmi$(x,y)$: i.e. I know that for all $x,y$ the following holds: $$-k \leq \log\left(\frac{p(x,y)}{p(x)p(y)}\right) \leq k$$

What upper bound does this imply on $I(X; Y)$. Of course it implies $I(X; Y) \leq k$, but I would like a tighter bound if possible. This seems plausible to me because p defines a probability distribution, and pmi$(x,y)$ cannot take its maximum value (or even be non-negative) for every value of $x$ and $y$.

• When the joint and marginal probabilities are uniform, pmi($x$,$y$) is uniformly zero (and therefore non-negative, apparently contradicting your last statement, but just barely). It seems to me, if I am not mistaken, that perturbing this situation over small subsets of $X \times Y$ indicates that bounds on pmi say almost nothing about $I(X;Y)$ itself.
– whuber
Jun 24, 2011 at 19:56
• In fact, if $X$ and $Y$ are independent, then $\mathrm{pmi}(x,y)$ is constant, regardless of the marginal distributions. So there's a whole class of distributions $p(x,y)$ for which $\mathrm{pmi}(x,y)$ obtains its maximum value for every $x$ and $y$. Jun 25, 2011 at 3:38
• Yes, it is certainly true that pmi$(x,y)$ can be equal for all $x$ and $y$, but that does not rule out a tighter bound. For example, it is not hard to prove that $I(X; Y) \leq k(e^k-1)$. This is $\approx k^2$ when $k < 1$, and is a non-trivial strengthening of the bound $k$ when $k < 1$. I am wondering if there are non-trivial bounds that hold more generally. Jun 27, 2011 at 13:57
• I'm doubtful that you'll get a better bound than $O(k^2)$ for $k \to 0$. If you want to look harder, try re-framing your question in terms of the KL divergence between p(x)p(y) and p(x,y). Pinsker's Inequality provides a lower bound on the MI that might confirm my hunch. See also Section 4 of ajmaa.org/RGMIA/papers/v2n4/relog.pdf.
– vqv
Oct 23, 2011 at 20:26

My contribution consists of an example. It illustrates some limits on how the mutual information can be bounded given bounds on the pointwise mutual information.

Take $X = Y = \{1,\ldots, n\}$ and $p(x) = 1/n$ for all $x \in X$. For any $m \in \{1,\ldots, n/2\}$ let $k > 0$ be the solution to the equation $$m e^{k} + (n - m) e^{-k} = n.$$ Then we place point mass $e^k / n^2$ in $nm$ points in the product space $\{1,\ldots,n\}^2$ in such a way that there are $m$ of these points in each row and each column. (This can be done in several ways. Start, for instance, with the first $m$ points in the first row and then fill out the remaining rows by shifting the $m$ points one to the right with a cyclic boundary condition for each row). We place the point mass $e^{-k}/n^2$ in the remaining $n^2 - nm$ points. The sum of these point masses is $$\frac{nm}{n^2} e^{k} + \frac{n^2 - nm}{n^2} e^{-k} = \frac{me^k + (n-m)e^{-k}}{n} = 1,$$ so they give a probability measure. All the marginal point probabilities are $$\frac{m}{n^2} e^{k} + \frac{m - n}{n^2} e^{-k} = \frac{1}{n},$$ so both marginal distributions are uniform.

By the construction it is clear that $\mathrm{pmi}(x,y) \in \{-k,k\},$ for all $x,y \in \{1,\ldots,n\}$, and (after some computations) $$I(X;Y) = k \frac{nm}{n^2} e^{k} - k \frac{n^2 - nm}{n^2} e^{-k} = k\Big(\frac{1-e^{-k}}{e^k - e^{-k}} (e^k + e^{-k}) - e^{-k}\Big),$$ with the mutual information behaving as $k^2 / 2$ for $k \to 0$ and as $k$ for $k \to \infty$.

I'm not sure if this is what you are looking for, as it is mostly algebraic and not really leveraging the properties of p being a probability distribution, but here is something you can try.

Due to the bounds on pmi, clearly $\frac{p(x,y)}{p(x)p(y)}\leq e^k$ and thus $p(x,y)\leq p(x)p(y)\cdot e^k$. We can substitute for $p(x,y)$ in $I(X;Y)$ to get $I(X;Y)\leq \sum_{x,y}p(x)p(y)\cdot e^k\cdot log(\frac{p(x)p(y)\cdot e^k}{p(x)p(y)}) = \sum_{x,y}p(x)p(y)\cdot e^k\cdot k$

I'm not sure if that's helpful or not.

EDIT: Upon further review I believe this is actually less useful than the original upper bound of k. I won't delete this though in case it might hint at a starting point.

• The value of this bound becomes apparent after you note $\sum_{x,y}p(x)p(y)=1$ and (since $k \ge 0$) that $e^k \ge 1$.
– whuber
Jun 24, 2011 at 20:49
• Yes, when I realized that I made my edit. Jun 24, 2011 at 21:17