Exponential Concentration for Mutual Information Estimation with Application to Forests

Part of Advances in Neural Information Processing Systems 25 (NIPS 2012)

Bibtex Metadata Paper


Han Liu, Larry Wasserman, John Lafferty


We prove a new exponential concentration inequality for a plug-in estimator of the Shannon mutual information. Previous results on mutual information estimation only bounded expected error. The advantage of having the exponential inequality is that, combined with the union bound, we can guarantee accurate estimators of the mutual information for many pairs of random variables simultaneously. As an application, we show how to use such a result to optimally estimate the density function and graph of a distribution which is Markov to a forest graph.