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

  • $\begingroup$ 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$? $\endgroup$ – fedja Jun 24 '11 at 17:49
  • $\begingroup$ 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$... $\endgroup$ – Florian Jun 24 '11 at 18:49
  • $\begingroup$ What does one mean by $k>>1$ in mathematics? $\endgroup$ – Ashok Aug 29 '11 at 8:08
  • $\begingroup$ @Ashok: It means $k \geq c\times 1$ for some positive constant $c$ so you could say it means $k=\Omega(1)$ in computer science notation. $k\ll 1$ would mean $k=O(1).$ $\endgroup$ – kodlu Oct 27 '15 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.