Regularities Unseen, Randomness Observed:
Levels of Entropy Convergence


James P. Crutchfield
Santa Fe Institute
1399 Hyde Park Rd.
Santa Fe, NM 87501, USA

David P. Feldman
College of the Atlantic
105 Eden Street
Bar Harbor, ME 04609, USA
and
Santa Fe Institute
1399 Hyde Park Rd.
Santa Fe, NM 87501, USA

Abstract

We study how the Shannon entropy of sequences produced by an information source converges to the source's entropy rate. We synthesize several phenomenological approaches to applying information theoretic measures of randomness and memory to stochastic and deterministic processes by using a hierarchy of derivatives of Shannon entropy convergence. This leads, in turn, to natural measures of (i) apparent memory stored in a source and (ii) the amounts of information that must be extracted from observations of a source in order (a) for it to be optimally predicted and (b) for an observer to synchronize to it. One consequence of ignoring these structural properties is that the missed regularities are converted to apparent randomness. We demonstrate that this problem arises particularly for small data sets; e.g., in settings where one has access to a relatively few, short measurement sequences.

Citation

J. P. Crutchfield and D. P. Feldman Regularities Unseen, Randomness Observed:
Levels of Entropy Convergence
, Santa Fe Insitute Working Paper 01-02-012. arXiv.org/abs/cond-mat/0102181.

To transfer a copy of the entire paper click on its title.

Compressed: size = 768 kb.
Uncompressed: size = 2830 kb.
PDF: size = 489 kb. File stored as PostScript and gzip compress PostScript.
Above, kb = kilobytes.
For FTP access to these files use ftp.santafe.edu:/pub/CompMech/papers.
Last modified: 21 December 2000, JPC