Binary Sequences

November 22nd, 2016

Maximally Unpredictable Sequences


Recently, my abstract algebra teacher mentioned a very interesting class of binary sequences called "maximally unpredictable" sequences, so I decided to make a simple generator. Hit Generate Sequence if you want to see the original sequence (A038219) described in Ehrenfeucht and Mycielski's paper, or type in any binary sequence and this will generate the "most unpredictable" sequence based off of your input.


If you were given the first 10 terms of a sequence of 1s and 0s, how would you try to predict what the 11th term in is? One approach is to try and find the longest chunk from the end which has appeared before. For example, take these ten terms \[0100110101.\] If we look at the last three terms \(101\), the last time this pattern occurred was in the 6th through 8th positions. This is the longest chunk from the end which has appeared sometime earlier in the sequence so our guess is whatever value is in the 9th position, \(0\). In order to make a sequence which was as hard as possible to guess, we flip that scheme on its head and say the next term in this sequence is the opposite of whatever your guess would have been! Hence this sequence is "maximally unpredictable".

It would be interesting to explore different sequences where the next term is defined by flipping various guessing schemes on their heads.

The Thue-Morse Sequence


I first got interested in binary sequences in the summer of 2014 when I came across the Thue-Morse sequence (A010060). This sequence is defined recursively:

\[ \begin{align*} T_0 &= 0\\ T_{2n} &= T_{n}\\ T_{2n+1} &= 1 - T_{n} \end{align*} \]

The recursive definition makes it very appealing to computer scientists. For example, you can indefinitely generate terms with just a few lines of code:

1
2
3
4
5
6
7
8
let T = [];
T[0] = 0;
let n = 0;
while (n < Infinity) {
    T[2*n] = T[n];
    T[2*n + 1] = 1 - T[n];
    n++;
}

Here's what that sequence looks like.

01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101...

That summer I spent an inordinate amount of time working out this closed form solution \[ T_n=1+\left(\sum_{k=0}^{\lfloor\log_2(n)\rfloor-1}\left\lfloor\frac{n}{2^k}\right\rfloor\mod 2\right)\mod 2 .\] There are other closed form solutions involving sines and binomial coefficients, but I have not seen this particular solution anywhere.

One of the interesting properties this sequence has is that the \(n\)-th term counts the number of 1s in the binary expansion of \(n\). I later found out that this was some "well-known" result, but I guess it depends who you ask.

This sequence has some very interesting 'fractal' properties as well. If we take the first \(2^{2n}\) terms and place them in a grid, ordered left to right, top to bottom, a repeating pattern emerges. Here are those patterns for \(n = 1, 2, 3, 4\).

The fractal nature of the Thue-Morse sequence visualized.

But the coolest property is this: if you interpret the sequence as a set of instructions where 0 means move forward, and 1 means rotate by \(\pi/3\) radians, a familiar pattern begins to emerge...

Yet another fractal pattern hidden in the Thue-morse sequence.

Details on why this happens can be found here.

De Bruijn Sequences


The final binary sequence I want to talk about here is another class of binary sequences called De Bruijn sequences. These are not necessarily binary sequences, but the easiest to visually see in binary. De Bruijn sequences are, in a sense the most efficient way of encoding permutations. These sequences are named after Nicolaas Govert de Bruijn, a Dutch mathematician who probably deserves his own post. But for now, here is an embedded Sagemath cell.

A (2,3) De Bruijn sequence looks like this: 00010111. This string contains every possible 8-bit sequence which you can see by looking at consecutive strings of length 3.

But how do we find these sequences? It turns out these sequences correspond exactly to what are called *Hamiltonian cycles*, or a path through a certain type of graph which touches every vertex exactly once, and returns to the starting vertex. To see what I mean, check out the sage cell below.

Footnotes


  1. More technically, the longest suffix which has appeared at least once before.

References


  1. Ehrenfeucht, A., & Mycielski, J. (1992). A Pseudorandom Sequence -- How Random Is It? The American Mathematical Monthly, 99(4), 373-375. doi:10.2307/2324917