Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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}<k$ but I doubt it is the kind of improvement you are looking for. Or are you interested in the case $k\to 0$? –  fedja Jun 24 '11 at 17:49
Good example -- I guess for 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 '11 at 18:49
What does one mean by $k>>1$ in mathematics? –  Ashok Aug 29 '11 at 8:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.