17
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – whuber Jun 24 '11 at 19:56
  • 1
    $\begingroup$ 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$. $\endgroup$ – cardinal Jun 25 '11 at 3:38
  • $\begingroup$ 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. $\endgroup$ – Florian Jun 27 '11 at 13:57
  • 1
    $\begingroup$ 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. $\endgroup$ – vqv Oct 23 '11 at 20:26
4
+50
$\begingroup$

My contribution consists of an example. It illustrates some limits on how the mutual information can be bounded given bounds on the pointwise mutual information.

Take $X = Y = \{1,\ldots, n\}$ and $p(x) = 1/n$ for all $x \in X$. For any $m \in \{1,\ldots, n/2\}$ let $k > 0$ be the solution to the equation $$m e^{k} + (n - m) e^{-k} = n.$$ Then we place point mass $e^k / n^2$ in $nm$ points in the product space $\{1,\ldots,n\}^2$ in such a way that there are $m$ of these points in each row and each column. (This can be done in several ways. Start, for instance, with the first $m$ points in the first row and then fill out the remaining rows by shifting the $m$ points one to the right with a cyclic boundary condition for each row). We place the point mass $e^{-k}/n^2$ in the remaining $n^2 - nm$ points. The sum of these point masses is $$\frac{nm}{n^2} e^{k} + \frac{n^2 - nm}{n^2} e^{-k} = \frac{me^k + (n-m)e^{-k}}{n} = 1,$$ so they give a probability measure. All the marginal point probabilities are $$\frac{m}{n^2} e^{k} + \frac{m - n}{n^2} e^{-k} = \frac{1}{n},$$ so both marginal distributions are uniform.

By the construction it is clear that $\mathrm{pmi}(x,y) \in \{-k,k\},$ for all $x,y \in \{1,\ldots,n\}$, and (after some computations) $$I(X;Y) = k \frac{nm}{n^2} e^{k} - k \frac{n^2 - nm}{n^2} e^{-k} = k\Big(\frac{1-e^{-k}}{e^k - e^{-k}} (e^k + e^{-k}) - e^{-k}\Big),$$ with the mutual information behaving as $k^2 / 2$ for $k \to 0$ and as $k$ for $k \to \infty$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – whuber Jun 24 '11 at 20:49
  • $\begingroup$ Yes, when I realized that I made my edit. $\endgroup$ – Michael McGowan Jun 24 '11 at 21:17

Your Answer

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

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