What is the most complex sequence that can be made from a n-long binary string?
0....0 and 1....1 are easily compressible, thus what is the most unpredictable sequence?
Let's proceed by induction.
0, 1 - 0 and 1 have a 50% to be selected in a 1-long binary string, thus they are the most complex examples of a 1-long binary string.
With two bits, we introduce two patterns: repeating and alternating. Repeating means that the bits are repeated for the complete string. Alternating means that the bits are alternating between 0 and 1 given a certain periodicity.
|001||complex, or alternating, periodicity=2|
|011||complex, or alternating, periodicity=1,2|
|100||complex, or alternating, periodicity=1,2|
|110||complex, or alternating, periodicity=2|
001, 011, 100, 110 can be described as alternating and repeating, which is more complex than the previous examples as it requires the composition of two operations.
4 complex examples
|0001||complex, or fill & flip|
|0010||complex, or fill & flip|
|0100||complex, or fill & flip|
|0111||complex, or fill & flip|
|1000||complex, or fill & flip|
|1011||complex, or fill & flip|
|1101||complex, or fill & flip|
|1110||complex, or fill & flip|
Here we first observe the presence of the alternating pattern with a periodicity of 2. We also observe the first case of a mirror pattern with 0110 and 1001. It could be claimed that 010 and 101 is the uneven equivalent of the mirror pattern for 3-long binary strings. The remaining "complex" examples are again displaying alternating and repeating patterns at the lower level.
One observation is that the complex patterns appear to be the variants where 1 bit is the opposite of the remaining bits, the only special case so far being for the 3-long binary string where the pattern is considered alternating. Instead of considering it a complex pattern, it could be described as the operation "fill X bits with 0/1, then flip by Y".
From those few inductive iterations, we can see that the first and last string are always the repeating pattern. We also observe that the first half of the strings exhibit the same pattern of the second half of the strings, which is expected due to the binary nature of the string.
At this point there is still not enough information to be able to derive an answer to the original question, given that the strings can be described using 4 patterns: repeating, alternating, mirror, and fill & flip.
8 complex examples
|00001||fill & flip|
|00010||fill & flip|
|00100||fill & flip|
|00101||complex, or 0 and alternating, periodicity=1|
|00110||complex, or alternating, periodicity=2|
|01000||fill & flip|
|01001||complex, or 0 and mirror|
|01011||complex, or 0 and fill & flip|
|01100||complex, or alternating, periodicity=1,2,2|
|01101||complex, or 0 and fill & flip|
|01110||complex, or alternating, periodicity=1,3,1|
|01111||fill & flip|
The second half of this table was not written down due to the previous observation that the patterns are the same, simply inverted.
At this stage, the complex patterns that emerge are difficult to express using the prior language. Composition needs to be used, e.g. 00101 can be described as 00 then 101.
14 complex examples
At this point in my study, I would summarize as follows:
- Repeating, alternating and fill & flip are low complexity. For a n-long binary string, this implies 2 repeating patterns, 2n fill & flip patterns, 2n alternating patterns of periodicity=1.
- Complexity appears to emerge from alternating patterns with varying periodicity. As we're working with longer and longer strings, the periodic patterns will start to become periodic themselves (I believe this is leading to fractal).
- The fill & flip pattern appears to be able to cover most of the complex cases that appear as the length of the binary string increases.
- Some of the patterns can be expressed as a few alternatives, for example 01110 as alternating, periodicity=1,3,1, but also as 0 and fill & flip (or even an "odd" mirror). My intuition would lead me to think that those cases that can be expressed in multiple ways are less complex.