A Caltech Library Service

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

Venkatesh, Santosh S. and Franklin, Joel (1991) How much information can one bit of memory retain about a Bernoulli sequence? IEEE Transactions on Information Theory, 37 (6). pp. 1595-1604. ISSN 0018-9448. doi:10.1109/18.104320.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1991 IEEE. Manuscript received June 8, 1990; revised March 19, 1991. This work was supported by the Air Force Office of Scientific Research under Grant AFOSR-89-0523. This work was presented in part at the IEEE International Symposium on Information Theory, San Diego, CA, January 14-19, 1990. The authors are indebted to J. Komlós for bringing the problem analyzed in this paper to our attention, and for going through an earlier version of the paper with helpful comments. The authors are also much obliged to A. Barron who showed them the simple convex combination argument using which Theorem 3 follows directly from the proof of Theorem 1.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)AFOSR-89-0523
Issue or Number:6
Record Number:CaltechAUTHORS:20190304-142847195
Persistent URL:
Official Citation:S. S. Venkatesh and J. Franklin, "How much information can one bit of memory retain about a Bernoulli sequence?," in IEEE Transactions on Information Theory, vol. 37, no. 6, pp. 1595-1604, Nov. 1991. doi: 10.1109/18.104320
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93449
Deposited By: Tony Diaz
Deposited On:04 Mar 2019 22:38
Last Modified:16 Nov 2021 16:57

Repository Staff Only: item control page