Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.18885 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918510105460736 |
|---|---|
| author | Frydrych, Piotr |
| author_facet | Frydrych, Piotr |
| contents | We prove that the extremum stack of a discrete sequence is a minimal sufficient statistic for the class of all computable, causal, rate-independent functionals, in the sense of Kolmogorov complexity. Specifically, we establish K(Pi_n) - O(1) <= K_R(u_{0:n}) <= K(Pi_n) + O(1), where K_R(u_{0:n}) is the length of the shortest program answering every query in the class R, and the O(1) overhead is independent of both the sequence length n and the stack depth k. Sufficiency follows from the classical wiping property of the Preisach hysteresis operator. Minimality is established via a finite indicator family whose rate-independence is verified explicitly. Any compression of a hysteresis-driven stream that preserves the full class R must therefore retain at least K(Pi_n) - O(1) bits; the stack-based compression algorithm implied by the result carries a Kolmogorov optimality guarantee that none of the standard time-series compression methods provide. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18885 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation Frydrych, Piotr Information Theory Artificial Intelligence Computational Complexity 68Q30, 94A15, 94A29 E.4; F.1.3; H.3.1 We prove that the extremum stack of a discrete sequence is a minimal sufficient statistic for the class of all computable, causal, rate-independent functionals, in the sense of Kolmogorov complexity. Specifically, we establish K(Pi_n) - O(1) <= K_R(u_{0:n}) <= K(Pi_n) + O(1), where K_R(u_{0:n}) is the length of the shortest program answering every query in the class R, and the O(1) overhead is independent of both the sequence length n and the stack depth k. Sufficiency follows from the classical wiping property of the Preisach hysteresis operator. Minimality is established via a finite indicator family whose rate-independence is verified explicitly. Any compression of a hysteresis-driven stream that preserves the full class R must therefore retain at least K(Pi_n) - O(1) bits; the stack-based compression algorithm implied by the result carries a Kolmogorov optimality guarantee that none of the standard time-series compression methods provide. |
| title | The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation |
| topic | Information Theory Artificial Intelligence Computational Complexity 68Q30, 94A15, 94A29 E.4; F.1.3; H.3.1 |
| url | https://arxiv.org/abs/2605.18885 |