# Mutual Information for Gaussian Process (and also Fano's Inequality)

According to this presentation: Bounding Gaussian Process Information Gain we have a closed-form expression for the information gain as follows: $$I\left(\vec{y} \mid f\right) = \frac{1}{2} \log\det \left[\bf{I} - \sigma^{-2} \bf{K}\right]$$ Where $\vec{y}$ is a sampling of the Gaussian process at some number of points (say, $n$), $f$ is the Gaussian process, $\bf{K}$ is the covariance matrix.

My question is a simple one, I think. Clearly the only aspect of the equation above that depends on the sample vector $\vec{y}$ is $\bf{K}$. Suppose we have that $n=1$ initially and that we are prepared to sample again from the Gaussian process at another point. Can we say anything about how the mutual information will change with the addition of the this new point into $\vec{y}$? That is, can we say that mutual information will certainly not decrease? Or can we say nothing at all?

With respect to Fano's Inequality, I was having a read of the paper here: Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions. In the paper, the author's state the following:

A "decoder" (i.e. an estimator) $\phi : \mathcal{X}^n \to \left\{1,2,\ldots,M\right\}$ is $\delta$-unreliable over the "family" (i.e. a set of models) $\left\{\theta_1,\theta_2,\ldots, \theta_M\right\}$ if $$\max_{k = 1,\ldots, M} \mathbb{P}\left[\phi\left(X^n\right) \neq k\right] \geq \delta - \frac{1}{\log M}$$ Here, they represent by $X^n$ a design matrix of $n$ samples. Then they go on the say that Fano's Inequality yields an upper bound on the sample size that guarantees that any estimator is $\delta$-unreliable. This bound is, $$n < \frac{(1 - \delta) \log M}{I\left(X^{(1)} ; K\right)}$$ where $$I\left(X^{(1)} ; K\right) = H\left(X^{(1)}\right) - H\left(X^{(1)} \vert K\right)$$ is the mutual information. The authors do not state what $X^{(1)}$ is supposed to be, but I assume it is a single example from the design matrix (would be nice to get some clarification on this as well).

The authors state that this form of Fano's inequality (that upper bounds the number of samples that guarantees $\delta$-unreliability) is standard, and even provide some links to papers using it. That being said, I can't find this particular form of the inequality used or derived in those papers. So I am wondering if anyone can show me where it comes from. All the results that I reproduce above appear on page 4123 in equations 25, 26, and 27.

I would be very appreciative if anyone can help me with these two questions.