Patterns in Bit Strings

The simplest structure to carry information is bit strings. We consider patterns in bit strings here. Here we note that logic can express patterns that are inviolate or merely more likely than expected. Mathematics specializes in inviolate patterns. We contemplate here an information field and patterns therein. A field (I am purposely vague here) generally has some group of transformations and we are interested in patterns that are not statistically affected by these transformations. I will mainly stick to 1D fields and even infinite strings of bits. There are indeed 2ⁿ strings of n bits and we declare these equally probable. If k < n then the first k bits of a string of n random bits produces random k bit strings. Choosing a j bit string and k bit string produces a j+k bit string if we concatenate them. These pleasant properties fail for more complex probabilities. If we remove from our set of 2ⁿ strings all strings with adjacent ones then we have F_n strings left.

We seek here a meaning for the suggestive description:

an infinite string of bits except for the fact that only 1/5 of the adjacent bit pairs are 11. We propose a procedure to choose a random such k bit string: Consider a large integer n (>k) and a small positive real ε. Consider that set X(n,ε) of n bit strings such that the density δ of adjacent one’s satisfies |δ − 1/5| < ε. Choose k (< n) bits randomly from a random one of these n bit strings. We thus get a distribution of k bit strings. Let n approach infinity and then ε approach zero, this distribution converges.

The above needs to be made clearer and more rigorous. The ideas here seem adaptable to producing samples bit streams, but not without some considerable work.

If that were all verified then we could test some of the following ideas. Suppose you come across a very long bit stream that looks random except that 1/5 of adjacent bit pairs are 11 (or some other stationary pattern occurs with a frequency not accounted for by the presumption of independent p=½ bits). In the sparse 11 case we will expect fewer occurrences of 011 and 111 as well. Indeed the ‘sparse 11’ situation will adjust the probability of most other patterns in ways that should be easy to compute. We can then look further at the string and look for more ‘unexpected’ distributions in the form of ‘stationary boolean patterns’. If we find more those new patterns may imply our ‘sparse 11’ pattern whereupon we might simplify our description. It is somewhat like finding a basis set for a linear subspace of a vector space, but that is a premature conjecture.