I am estimating the mutual information for a continuous data set using the kNN-based mutual information estimator proposed by Kraskov et al .
Lets consider two features $X$ and $Y$, and the estimated mutual information for the total dataset: $MI(X;Y) = I$.
When I split up the dataset in two parts, where both parts do not have matching samples (meaning each sample of the total data set is either in the first or second part). Estimating the mutual information for both parts gives: $MI(X_1, Y_1) = I_1$ and $MI(X_2, Y_2) = I_2$.
In the dataset I am working with: I get the following result: $I_1 < I_2 < I$. Meaning the mutual information is smaller in both subsets than the mutual information of the entire dataset.
Intuitively, this does not make sense to me as I was expecting that one subset would have a larger mutual information than the entire data set and the other subset a smaller mutual information. I tried to find mathematical arguments to prove if the results make sense or not, however without success.
Is it (mathematically) possible that when you divide your dataset into two parts, that the mutual information of both parts is smaller than the mutual information of the whole dataset?
 Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information. Physical Review E, 69(6), 2004. ISSN 1539-3755. doi: 10.1103/physreve.69.066138. URL https://dx.doi.org/ 10.1103/PhysRevE.69.066138.