Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 8 down vote favorite
3

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
1  
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
1  
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

1 Answer

up vote 0 down vote

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.

share|improve this answer
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
Yes, when I realized that I made my edit. – Michael McGowan Jun 24 '11 at 21:17

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.