title: A finite-sample, distribution-free, probabilistic lower bound on mutual information.
abstract: For any memoryless communication channel with a binary-valued input and a one-dimensional real-valued output, we introduce a probabilistic lower bound on the mutual information given empirical observations on the channel. The bound is built on the Dvoretzky-Kiefer-Wolfowitz inequality and is distribution free. A quadratic time algorithm is described for computing the bound and its corresponding class-conditional distribution functions. We compare our approach to existing techniques and show the superiority of our bound to a method inspired by Fano's inequality where the continuous random variable is discretized.
authors.affiliation: Computer and Information Science and Engineering, University of Florida, Gainesville, FL 32611, USA. ndv@cise.ufl.edu
authors.forename: Nathan D
authors.initials: ND
authors.lastname: VanderKraats
authors.forename: Arunava
authors.initials: A
authors.lastname: Banerjee
mesh_terms: D000465:Algorithms; D020342:Finite Element Analysis; D015233:Models, Statistical; D011897:Random Allocation