How much information can one bit of memory retain about a Bernoulli sequence?

Abstract

The maximin problem of the maximization of the minimum amount of information that a single bit of memory retains about the entire past is investigated. The problem is to estimate the supremum over all possible sequences of update rules of the minimum information that the bit of memory at epoch (n+1) retains about the previous n inputs. Using only elementary techniques, it is shown that the maximin covariance between the memory at epoch (n+1) and past inputs is Θ(1/n), the maximum average covariance is Θ(1/n), and the maximin mutual information is Ω(1/n^2). In a consideration of related issues, the authors also provide an exact count of the number of Boolean functions of n variables that can be obtained recursively from Boolean functions of two variables, discuss extensions and applications of the original problem, and indicate links with issues in neural computation.