Asymptotic Analysis of the kth Subword Complexity

Area of Science:

• Information Theory
• Combinatorics
• Probability Theory

Background:

• Character strings contain patterns that reveal randomness or periodicity.
• The kth Subword Complexity quantifies these patterns by counting distinct substrings of length k.
• Understanding string complexity is crucial for analyzing data randomness.

Purpose of the Study:

• To evaluate the expected value and second factorial moment of the kth Subword Complexity for binary strings from memory-less sources.
• To derive exact expressions for these moments using combinatorial methods.
• To investigate the asymptotic behavior of kth Subword Complexity for specific k values.

Main Methods:

• Combinatorial approach using probability generating functions.
• Derivation of exact expressions for moments based on pattern auto-correlation and correlation polynomials.
• Analysis of asymptotic behavior (k = Θ(log n)) using complex analysis, poissonization, Mellin transform, and saddle point analysis.

Main Results:

• Exact expressions for the expected value and second factorial moment of kth Subword Complexity were obtained.
• The asymptotic behavior of the kth Subword Complexity was investigated.
• The distribution was compared to distinct prefixes in tries.

Conclusions:

• The study provides a rigorous mathematical framework for analyzing string randomness via kth Subword Complexity.
• Advanced analytical techniques offer insights into the behavior of string patterns.
• This research contributes to a deeper understanding of information-theoretic properties of strings.