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(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$. 
 A: 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$. 

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