Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2512.21193 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911337600253952 |
|---|---|
| author | Vidakovic, Brani |
| author_facet | Vidakovic, Brani |
| contents | Kolmogorov complexity of a finite binary word reflects both algorithmic structure and the empirical distribution of symbols appearing in the word. Words with symbol frequencies far from one half have smaller combinatorial richness and therefore appear less complex under the standard definition. In this paper an entropy-normalized complexity measure is introduced that divides the Kolmogorov complexity of a word by the empirical entropy of its observed distribution of zeros and ones. This adjustment isolates intrinsic descriptive complexity from the purely combinatorial effect of symbol imbalance. For Martin Löf random sequences under constructive exchangeable measures, the adjusted complexity grows linearly and converges to one. A pathological construction shows that regularity of the underlying measure is essential. The proposed framework connects Kolmogorov complexity, empirical entropy, and randomness in a natural manner and suggests applications in randomness testing and in the analysis of structured binary data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21193 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization Vidakovic, Brani Computation Computational Complexity Information Theory 68Q30, 60G09 F.2.3 Kolmogorov complexity of a finite binary word reflects both algorithmic structure and the empirical distribution of symbols appearing in the word. Words with symbol frequencies far from one half have smaller combinatorial richness and therefore appear less complex under the standard definition. In this paper an entropy-normalized complexity measure is introduced that divides the Kolmogorov complexity of a word by the empirical entropy of its observed distribution of zeros and ones. This adjustment isolates intrinsic descriptive complexity from the purely combinatorial effect of symbol imbalance. For Martin Löf random sequences under constructive exchangeable measures, the adjusted complexity grows linearly and converges to one. A pathological construction shows that regularity of the underlying measure is essential. The proposed framework connects Kolmogorov complexity, empirical entropy, and randomness in a natural manner and suggests applications in randomness testing and in the analysis of structured binary data. |
| title | Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization |
| topic | Computation Computational Complexity Information Theory 68Q30, 60G09 F.2.3 |
| url | https://arxiv.org/abs/2512.21193 |