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

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

## Answer

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

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

so they give a probability measure. All the marginal point probabilities are

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)

with the mutual information behaving as $k^2 / 2$ for $k \to 0$ and as $k$ for $k \to \infty$.

Attribution
Source : Link , Question Author : Florian , Answer Author : NRH