Entropy-Variance Curves of Binary Sequences Generated by Random Substitutions of Constant Length.

Area of Science:

• Dynamical Systems and Chaos Theory
• Information Theory
• Stochastic Processes

Background:

• Binary sequences are fundamental in computer science and information theory.
• Random substitution systems offer a framework for generating complex sequences from simple rules.
• Understanding the statistical properties of such sequences is crucial for applications in data compression, cryptography, and modeling complex systems.

Purpose of the Study:

• To investigate the statistical properties of binary sequences generated by a specific asymmetric random substitution rule.
• To derive the probability distribution, mean, variance, and entropy of the number of ones in these sequences as a function of iteration number and substitution length.
• To characterize the relationship between entropy and variance and identify novel regimes of dependence.

Main Methods:

• Utilizing recurrence relations to determine the discrete probability distribution of the count of ones.
• Deriving analytical expressions for the first two statistical moments (mean and variance).
• Calculating the sequence entropy as a function of substitution length (k) and iteration number (i).
• Analyzing parametric curves of entropy versus variance to identify distinct dependence regimes.

Main Results:

• The discrete probability distribution of the number of ones was obtained by recurrence.
• Analytical expressions for the mean and variance of the generated sequences were derived.
• The entropy of the sequences was characterized as a function of substitution length (k) and iteration number (i).
• Two novel regimes of dependence between entropy and variance were identified, allowing for comparisons of sequences with identical entropy but differing variance, or vice versa.

Conclusions:

• The study provides a comprehensive statistical analysis of binary sequences generated by asymmetric random substitutions.
• Novel insights into the relationship between sequence entropy and variance were uncovered.
• The findings offer a new perspective for comparing and characterizing complex sequences generated by stochastic processes.