# Upper Bound on Mutual Information

I am interested in an upper bound on mutual information that I have been encountering frequently in the statistics and probability literature. I have yet to see the "purest" form of the inequality, so I will attempt to state it first, and then I will provide some literature that use leverage it. Ideally someone will be able to help me understand where this bound comes from and how it is derived.

Here is the idea: Let $M = \left\{\theta_1,\theta_2,\ldots,\theta_m\right\}$ be a set of "models". Additionally, let $\phi : \mathbb{R}^{n\times m} \to \left\{1,2,\ldots,m\right\}$. Indeed, $\phi\left(X^n\right)\in \left\{1,2,\ldots,m\right\}$ where $X^n$ may be thought of as a data (or design) matrix of $n$ observations. In other words, we are trying to recover, through the estimator $\phi$ one of the $m$ models which best describes our data.

I am interested in the following quantity: $I\left(\phi; X^n\right)$, where $I$ represents the mutual information. Then the following bounds $I$ from above: $$I\left(\phi,X^n\right) \leq \frac{n}{m^2} \sum_{i=1}^m \sum_{j = 1}^m S\left(\mathbb{P}_{\theta_i} \left|\right| \mathbb{P}_{\theta_j}\right)$$ Here, $S\left(\cdot\left|\right|\cdot\right)$ denotes the symmetric KL-divergence. Further, $\mathbb{P}_{\theta_i}$ represents the underlying probability distribution for the model $\theta_i$.

This bound appears in Exploiting the Limits of Structure Learning via Inherent Symmetry and Information-theoretic bounds on model selection for Gaussian Markov random ﬁelds. In the former, see equation (2). In the latter, see equation (18). For the latter paper though, I believe there is a typo as there seems to be a factor of $2n$ missing. (Please correct me if I am wrong.) Therefore, it may be best to consult the first paper.

• try statistics.stackexchange.com – Sergio Parreiras Jul 10 '14 at 18:06
• It is not clear what your question is. Also, if $\phi(X)$ is a deterministic function of $X$, then the mutual information between $X$ and $\phi(X)$ is just $H(\phi(X))$, since $H(\phi(X)|X)=0$. So you might need to clarify what is meant by $X$ and by $\phi$. – Michael Jul 10 '14 at 20:54
• @Michael You assisted me with an earlier question to which this one is related. You helped me with the paper here: eecs.berkeley.edu/~wainwrig/Papers/SanWai12.pdf. You can think of X as a matrix of observed random vectors taken from a probability distribution described by a Markov random field as in equation (2) in the paper. Phi you may think of as a graph estimator also as described in the paper I link above or as Xi in the first paper in the original post above. The mutual information is too difficult to calculate directly, but for my purpose an upper bound will suffice. – user1936768 Jul 10 '14 at 21:32
• @Michael To clarify, my question is to understand where the bound (2) in jmlr.org/proceedings/papers/v33/he14b.pdf comes from. I have seen similar bounds in other literature as well, so I am confident that it is well-known and accepted, but I do not know where it comes from or how it is derived. – user1936768 Jul 10 '14 at 21:38

Equation (2) in the He and Zhang paper describes the problem quite differently: For each $m\in\{1, \ldots, M\}$ we have a joint distribution $p_m(x)$ for a random vector $X$. Now, $\phi$ is a uniform random variable in the set $\{1, \ldots, M\}$. Given $\phi=m$, form a matrix $X^n = [X_1, X_2; \ldots; X_n]$, where each of the $n$ rows is an iid vector $X_i$ taken from the distribution $p_m(x)$. So: \begin{eqnarray*} I(\phi; X^n) &=& H(X^n) - H(X^n|\phi) \\ &=& H(X_1; X_2; \ldots; X_n) - H(X_1; X_2; \ldots; X_n | \phi) \\ &\leq& H(X_1) + \ldots + H(X_n) - H(X_1; X_2; \ldots; X_n | \phi) \\ &=& H(X_1) + \ldots + H(X_n) - [H(X_1|\phi) + H(X_2|\phi) + \ldots + H(X_n|\phi)]\\ &=& \sum_{i=1}^n I(\phi; X_i) \\ &=& nI(\phi; X_1) \end{eqnarray*} where the first inequality is a standard bound on the entropy of a collection of random variables, and the equality below it (that is, the third-to-last equality above) follows because $\{X_1; X_2; \ldots; X_n\}$ are conditionally independent given $\phi$.
Now it suffices to prove a bound on $I(\phi; X_1)$. We have $I(\phi; X_1) = H(X_1) - H(X_1|\phi)$. Then: \begin{eqnarray*} H(X_1) &=& -\sum_x p(x)\log(p(x))\\ &=&-\sum_{\phi=1}^M\sum_x\frac{1}{M}p(x|\phi)\log\left(\frac{1}{M}\sum_{\phi'=1}^Mp(x|\phi')\right)\\ &\leq&-\sum_{\phi=1}^M\sum_x\frac{1}{M}p(x|\phi)\left[\frac{1}{M}\sum_{\phi'=1}^M\log(p(x|\phi')) \right]\\ &=&\frac{1}{M^2}\sum_{\phi'=1}^M\sum_{\phi=1}^M\left[\sum_x p(x|\phi)\log\left(\frac{1}{p(x|\phi')}\right)\right] \end{eqnarray*} where the inequality uses Jensen's inequality on the concave function $\log(\cdot)$. Next:
Putting these two together gives: \begin{eqnarray*} I(\phi; X_1) &=& H(X_1) - H(X_1|\phi) \\ &\leq& \frac{1}{M^2}\sum_{\phi'=1}^M\sum_{\phi=1}^M\sum_x p(x|\phi)\log\left(\frac{p(x|\phi)}{p(x|\phi')}\right)\\ &=& \frac{1}{M^2}\sum_{\phi'=1}^M\sum_{\phi=1}^MD_{KL}\left(p(x|\phi) || p(x|\phi')\right) \end{eqnarray*} where $D_{KL}(\cdot)$ is the Kullback-Leibler divergence.
\begin{eqnarray*} &&\frac{1}{M^2}\sum_{\phi'=1}^M\sum_{\phi=1}^MD_{KL}\left(p(x|\phi) || p(x|\phi')\right)\\ &=&\frac{1}{M^2}\sum_{\phi'=1}^M\sum_{\phi=1}^{\phi'-1} \left[D_{KL}\left(p(x|\phi) || p(x|\phi')\right) + D_{KL}\left(p(x|\phi')||p(x|\phi)\right)\right] \end{eqnarray*} with the understanding that $D_{KL}\left(p(x|\phi)||p(x|\phi)\right)=0$.