dorsal/arxiv
View SchemaComplexity Through Nonextensivity
| Authors | William Bialek, Ilya Nemenman, Naftali Tishby |
|---|---|
| Categories | |
| ArXiv ID | physics/0103076 |
| URL | https://arxiv.org/abs/physics/0103076 |
| DOI | 10.1016/S0378-4371(01)00444-7 |
Abstract
The problem of defining and studying complexity of a time series has interested people for years. In the context of dynamical systems, Grassberger has suggested that a slow approach of the entropy to its extensive asymptotic limit is a sign of complexity. We investigate this idea further by information theoretic and statistical mechanics techniques and show that these arguments can be made precise, and that they generalize many previous approaches to complexity, in particular unifying ideas from the physics literature with ideas from learning and coding theory; there are even connections of this statistical approach to algorithmic or Kolmogorov complexity. Moreover, a set of simple axioms similar to those used by Shannon in his development of information theory allows us to prove that the divergent part of the subextensive component of the entropy is a unique complexity measure. We classify time series by their complexities and demonstrate that beyond the `logarithmic' complexity classes widely anticipated in the literature there are qualitatively more complex, `power--law' classes which deserve more attention.
{
"annotation_id": "3d21cfef-6cf4-42bc-9d5c-ec922d879b05",
"date_created": "2026-03-02T18:00:36.121000Z",
"date_modified": "2026-03-02T18:00:36.121000Z",
"file_hash": "18c6c009283513edaf3dcf568af770af72f4d511ffcce882c98e8bd90893f0e4",
"private": false,
"record": {
"abstract": "The problem of defining and studying complexity of a time series has\ninterested people for years. In the context of dynamical systems, Grassberger\nhas suggested that a slow approach of the entropy to its extensive asymptotic\nlimit is a sign of complexity. We investigate this idea further by information\ntheoretic and statistical mechanics techniques and show that these arguments\ncan be made precise, and that they generalize many previous approaches to\ncomplexity, in particular unifying ideas from the physics literature with ideas\nfrom learning and coding theory; there are even connections of this statistical\napproach to algorithmic or Kolmogorov complexity. Moreover, a set of simple\naxioms similar to those used by Shannon in his development of information\ntheory allows us to prove that the divergent part of the subextensive component\nof the entropy is a unique complexity measure. We classify time series by their\ncomplexities and demonstrate that beyond the `logarithmic\u0027 complexity classes\nwidely anticipated in the literature there are qualitatively more complex,\n`power--law\u0027 classes which deserve more attention.",
"arxiv_id": "physics/0103076",
"authors": [
"William Bialek",
"Ilya Nemenman",
"Naftali Tishby"
],
"categories": [
"physics.data-an"
],
"doi": "10.1016/S0378-4371(01)00444-7",
"title": "Complexity Through Nonextensivity",
"url": "https://arxiv.org/abs/physics/0103076"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "514e936a-ba05-4bff-bdd3-2fa9678c7834",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}