The DOI matches its Crossref record; 69 of the 69 references it cites were found in a registry or an index.
Regularities unseen, randomness observed: Levels of entropy convergence
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 successive derivatives of the Shannon entropy growth curve. This leads, in turn, to natural measures of apparent memory stored in a source and the amounts of information that must be extracted from observations of a source in order for it to be optimally predicted and for an observer to synchronize to it. To measure the difficulty of synchronization, we define the transient information and prove that, for Markov processes, it is related to the total uncertainty experienced while synchronizing to a process. One consequence of ignoring a process’s structural properties is that the missed regularities are converted to apparent randomness. We demonstrate that this problem arises particularly for settings where one has access only to short measurement sequences. Numerically and analytically, we determine the Shannon entropy growth curve, and related quantities, for a range of stochastic and deterministic processes. We conclude by looking at the relationships between a process’s entropy convergence behavior and its underlying computational structure.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb00917.x · Cited by 48,949
The Nature of Statistical Learning Theory
Vapnik, V. N. (1995) · doi:10.1007/978-1-4757-2440-0 · Cited by 39,138
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Introduction to automata theory, languages and computation
(1981) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(81)90068-9 · Cited by 10,699
The Mathematical Theory of Communication
Shannon, C. E., Weaver, W., & Wiener, N. (1950) · Physics Today · doi:10.1063/1.3067010 · Cited by 9,801
Communication Theory of Secrecy Systems
Shannon, C. E. (1949) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1949.tb00928.x · Cited by 9,440
Ott, E., & Wiesenfeld, K. (1994) · Physics Today · doi:10.1063/1.2808369 · Cited by 3,448
Nonlinear Time Series Analysis
(2012) · SpringerReference · doi:10.1007/springerreference_205493 · Cited by 1,983
Entropy and Information Theory
Gray, R. M. (2011) · Springer eBooks · doi:10.1007/978-1-4419-7970-4 · Cited by 1,803
守屋, 悦. (1980) · 情報処理 · Cited by 1,791
An Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697
(1995) · Stochastic Modelling and Applied Probability · doi:10.1007/978-0-387-84854-9 · Cited by 1,432
Thermodynamics of Chaotic Systems
Beck, C. H., & Schögl, F. (1993) · Cambridge University Press eBooks · doi:10.1017/cbo9780511524585 · Cited by 1,390
Complexity, Entropy And The Physics Of Information
H. Zurek, W. (2018) · CRC Press eBooks · doi:10.1201/9780429502880 · Cited by 1,380
A philosophical essay on probabilities
(1952) · Journal of the Franklin Institute · doi:10.1016/0016-0032(52)90656-x · Cited by 1,136
Les méthodes nouvelles de la mécanique céleste
Poincaré, H. (1892) · doi:10.3931/e-rara-421 · Cited by 1,072
1 A Statistical Measure of ComplexityPreprint
López‐Ruiz, R., Mancini, H., & Calbet, X. (1995) · Cited by 939
A Statistical Measure of Complexity
López-Ruiz, R., Mancini, H. L., & Calbet, X. (1995) · Physics Letters A · doi:10.1016/0375-9601(95)00867-5 · Cited by 920
H. Poincaré, H. P. (2024) · doi:10.55094/holistence.185 · Cited by 816
The calculi of emergence: computation, dynamics and induction
Crutchfield, J. P. (1994) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(94)90273-9 · Cited by 754
Self-citationToward a quantitative theory of self-generated complexity
Grassberger, P. (1986) · International Journal of Theoretical Physics · doi:10.1007/bf00668821 · Cited by 694
The Theory of Critical Phenomena: An Introduction to the Renormalization Group
Binney, J. J., Dowrick, N. J., Fisher, A., & Newman, M. E. J. (1992) · CERN Document Server (European Organization for Nuclear Research) · Cited by 515
Predictability, Complexity, and Learning
Bialek, W., Nemenman, I., & Tishby, N. (2001) · Neural Computation · doi:10.1162/089976601753195969 · Cited by 504
Information theory and the living system
Gatlin, L. L. (1972) · Medical Entomology and Zoology · Cited by 490
The dripping faucet as a model chaotic system
Shaw, R. (1984) · Medical Entomology and Zoology · Cited by 472
Computational Mechanics: Pattern and Prediction, Structure and Simplicity
Shalizi, C. R., & Crutchfield, J. P. (2001) · Journal of Statistical Physics · doi:10.1023/a:1010388907793 · Cited by 471
Self-citationMutual information functions versus correlation functions
Li, W. (1990) · Journal of Statistical Physics · doi:10.1007/bf01025996 · Cited by 438
Measures of statistical complexity: Why?
Feldman, D. P., & Crutchfield, J. P. (1998) · Physics Letters A · doi:10.1016/s0375-9601(97)00855-4 · Cited by 436
Self-citationEntropy estimation of symbol sequences
Schürmann, T., & Grassberger, P. (1996) · Chaos: An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.166191 · Cited by 319
Shiner, J. S., Davison, M., & Landsberg, P. T. (1999) · Physical Review E · doi:10.1103/physreve.59.1459 · Cited by 317
Subshifts of finite type and sofic systems
Weiss, B. (1973) · Monatshefte für Mathematik · doi:10.1007/bf01295322 · Cited by 314
Ford, J. (1983) · Physics Today · doi:10.1063/1.2915570 · Cited by 291
Finite sample corrections to entropy and dimension estimates
Grassberger, P. (1988) · Physics Letters A · doi:10.1016/0375-9601(88)90193-4 · Cited by 287
Sixty-Two Years of Uncertainty
(1990) · NATO ASI Series · doi:10.1007/978-1-4684-8771-8 · Cited by 281
Lebowitz, J. L., & Penrose, O. (1973) · Physics Today · doi:10.1063/1.3127948 · Cited by 240
Nonlinear Modeling And Forecasting
Casdagli, M. (1992) · Cited by 233
Symbolic dynamics of noisy chaos
Crutchfield, J. P., & Packard, N. H. (1983) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(83)90127-6 · Cited by 212
Self-citationNoise, chaos, and (ε, τ)-entropy per unit time
Gaspard, P., & Wang, X.-J. (1993) · Physics Reports · doi:10.1016/0370-1573(93)90012-3 · Cited by 210
Entropy and Long-Range Correlations in Literary English
Ebeling, W., & Pöschel, T. (1993) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/26/4/001 · Cited by 183
Measuring correlations in symbol sequences
Herzel, H., & Große, I. (1995) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/0378-4371(95)00104-f · Cited by 170
Cellular Automata and Modeling of Complex Physical Systems
Manneville, P., Boccara, N., Vichniac, G. Y., & Bidaux, R. (1989) · Springer proceedings in physics · doi:10.1007/978-3-642-75259-9 · Cited by 127
On the Identifiability Problem for Functions of Finite Markov Chains
Blackwell, D., & Koopmans, L. H. (1957) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177706802 · Cited by 114
Beyond Belief: Randomness, Prediction and Explanation in Science
Casti, J. L., & Karlqvist, A. (1990) · Cited by 112
Statistical complexity of simple one-dimensional spin systems
Crutchfield, J. P., & Feldman, D. P. (1997) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.55.r1239 · Cited by 112
Self-citationFinite sample effects in sequence analysis
Herzel, H., Schmitt, A. O., & Ebeling, W. (1994) · Chaos Solitons & Fractals · doi:10.1016/0960-0779(94)90020-5 · Cited by 112
Estimating the information content of symbol sequences and efficient codes
Grassberger, P. (1989) · IEEE Transactions on Information Theory · doi:10.1109/18.30993 · Cited by 107
On the Relationship between Complexity and Entropy for Markov Chains and Regular Languages.
Li, W. (1991) · Cited by 94
Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise
Crutchfield, J. P., & Packard, N. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650178 · Cited by 93
Self-citationComputing Anticipatory Systems
Dubois, D. M. (1998) · University of Groningen research database (University of Groningen / Centre for Information Technology) · Cited by 87
Complexity measures and cellular automata
Lindgren, K. A., & Nordahl, M. G. (1988) · Chalmers Publication Library (Chalmers University of Technology) · doi:10.5555/56123.56125 · Cited by 78
Mathematical and Philosophical Questions in the Theory of Open and Macroscopic Quantum Systems
Primas, H. (1990) · NATO ASI series. Series B : Physics · doi:10.1007/978-1-4684-8771-8_14 · Cited by 76
Theory and algorithms for hidden Markov models and generalized hidden Markov models
Upper, D. R. (1998) · Cited by 61
Feldman, D. P., & Crutchfield, J. P. (1998) · RePEc: Research Papers in Economics · Cited by 55
Self-citationPrediction and entropy of nonlinear dynamical systems and symbolic sequences with LRO
Ebeling, W. (1997) · Physica D Nonlinear Phenomena · doi:10.1016/s0167-2789(97)00157-7 · Cited by 48
ENTROPY, TRANSINFORMATION AND WORD DISTRIBUTION OF INFORMATION-CARRYING SEQUENCES
Ebeling, W., Pöschel, T., & Albrecht, K. ‐. (1995) · International Journal of Bifurcation and Chaos · doi:10.1142/s0218127495000041 · Cited by 42
Calculation of the entropy in chaotic systems
Györgyi, G., & Szépfalusy, P. (1985) · Physical Review A · doi:10.1103/physreva.31.3477 · Cited by 42
Information-theoretic Analysis of Phase Transitions.
Arnold, D. V. (1996) · Complex Systems · Cited by 29
Computational mechanics of classical spin systems
Feldman, D. P. (1998) · PhDT · Cited by 29
Self-citationMicroscopic and macroscopic entropy
Lindgren, K. (1988) · Physical Review A · doi:10.1103/physreva.38.4794 · Cited by 27
Entropy, Complexity, Predictability, and Data Analysis of Time Series and Letter Sequences
Ebeling, W., Molgedey, L., Kurths, J., & Schwarz, U. D. (2002) · Springer eBooks · doi:10.1007/978-3-642-56257-0_1 · Cited by 26
Ontic and epistemic descriptions of chaotic systems
Harald Atmanspacher, A. (2000) · AIP conference proceedings · doi:10.1063/1.1291283 · Cited by 26
Comment II on “Simple measure for complexity”
Binder, P. M., & Perry, N. (2000) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.62.2998 · Cited by 26
Structural Information in Self-Organizing Systems
Eriksson, K.-E., & Lindgren, K. (1987) · Physica Scripta · doi:10.1088/0031-8949/35/3/026 · Cited by 22
Unreconstructible at any radius
Crutchfield, J. P. (1992) · Physics Letters A · doi:10.1016/0375-9601(92)90132-6 · Cited by 15
Self-citationInformation theory and learning: a physical approachPreprint
Nemenman, I. M. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.physics/0009032 · Cited by 15
Feldman, D. P., & Crutchfield, J. P. (2004) · Advances in Complex Systems · doi:10.1142/s0219525904000196 · Cited by 14
Self-citationMultiscale analysis of complex systems
Binder, P. M., & Plazas, J. A. (2001) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.63.065203 · Cited by 11
Noise Scaling of Symbolic Dynamics Entropies
Crutchfield, J. P., & Packard, N. H. (1982) · Springer series in synergetics · doi:10.1007/978-3-642-68808-9_19 · Cited by 8
Self-citation
Cited by
Supply-chain networks: a complex adaptive systems perspective
Surana, A., Kumara *, S., Greaves, M., & Raghavan, U. N. (2005) · International Journal of Production Research · doi:10.1080/00207540500142274 · Cited by 620
Predictability, Complexity, and Learning
Bialek, W., Nemenman, I., & Tishby, N. (2001) · Neural Computation · doi:10.1162/089976601753195969 · Cited by 504
Crutchfield, J. P. (2012) · Nature Physics · doi:10.1038/nphys2190 · Cited by 446
Self-citationJIDT: An Information-Theoretic Toolkit for Studying the Dynamics of Complex Systems
Lizier, J. T. (2014) · Frontiers in Robotics and AI · doi:10.3389/frobt.2014.00011 · Cited by 390
Local information transfer as a spatiotemporal filter for complex systems
Lizier, J. T., Prokopenko, M., & Zomaya, A. Y. (2008) · Physical Review E · doi:10.1103/physreve.77.026110 · Cited by 277
Metadata
- Authors
- Crutchfield, J. P., & Feldman, D. P.
- Venue
- Chaos: An Interdisciplinary Journal of Nonlinear Science
- Publisher
- AIP Publishing
- Published
- 2003-03-01
- Volume
- 13
- Issue
- 1
- Pages
- 25-54
- ISSN
- 1054-1500 (ISSN-L)
- 1089-7682
- OpenAlex
- W1532729789
- Cited by
- 368
- References
- 69
- FWCI
- 11.16
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.