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

-
 Alas, that's almost all you can say for large $k$: take $X=Y$ of cardinality $e^k$ and consider the linear combination of the uniform distribution on the diagonal with the coefficient $1-e^{-k}$ and the uniform distribution on the entire product with the coefficient $e^{-k}$. You'll still get $k-ke^{-k}> 1, there is no substantially better upper bound. I wonder if something is possible if$p(x)$is a uniform distribution over$X$and$|X|$>>$e^k$... – Florian Jun 24 2011 at 18:49 What does one mean by$k>>1\$ in mathematics? – Ashok Aug 29 2011 at 8:08