Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization.

Area of Science:

• Information Theory
• Algorithmic Complexity
• Probability Theory

Background:

• Kolmogorov complexity quantifies algorithmic structure but is influenced by symbol frequencies.
• Words with imbalanced symbol distributions are often considered less complex combinatorially.
• Existing measures do not fully isolate intrinsic descriptive complexity from symbol imbalance.

Purpose of the Study:

• To introduce an entropy-normalized complexity measure for binary words.
• To isolate intrinsic descriptive complexity from combinatorial effects of symbol imbalance.
• To explore the relationship between Kolmogorov complexity, empirical entropy, and randomness.

Main Methods:

• Normalization of Kolmogorov complexity by empirical entropy.
• Analysis of adjusted complexity for Martin-Löf random sequences under constructive exchangeable measures.
• Construction of a pathological case to demonstrate the necessity of measure regularity.

Main Results:

• The proposed entropy-normalized complexity measure effectively separates intrinsic complexity from symbol imbalance.
• For Martin-Löf random sequences, the adjusted complexity exhibits linear growth and converges to one.
• Regularity of the underlying measure is crucial for the observed properties of the adjusted complexity.

Conclusions:

• The framework provides a natural connection between Kolmogorov complexity, empirical entropy, and randomness.
• The adjusted complexity measure offers potential applications in randomness testing and structured binary data analysis.
• This work refines the understanding of complexity in binary sequences by accounting for symbol distribution.