# 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 '11 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$. –  cardinal Jun 25 '11 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. –  Florian Jun 27 '11 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 '11 at 20:26

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$
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 '11 at 20:49