I mentioned the Ehrenfeucht-Mycielski sequence and gave a reference, but I realize that few of you will take the trouble to look at the PDF unless I do a bit of advertising. Here's a passage from a different paper "On the Ehrenfeucht-Mycielski Balance Conjecture" by Kieffer and Szpankowski (available from the web at www.cs.purdue.edu/homes/spa/papers/em.pdf): "In the paper Ehrenfeucht and Mycielski (1992), an interesting binary sequence was defined, since termed the EM-sequence, which seems to possess pseudorandomness properties. The EM-sequence is sequence A038219 in the encyclopedia Sloane (2007), and is generated via an algorithm described in Sloane (2007) as follows: "The sequence starts 0,1,0 and continues according to the following rule: find the longest sequence at the end that has occurred at least once previously. If there are more than one previous occurrences select the last one. The next digit of the sequence is the opposite of the one following the previous occurrence." For example, the first 50 terms of the EM-sequence are 01001101011100010000111101100101001001110100011000. Despite the simplicity of this algorithm, not very much is known about the asymptotics of the EMsequence. It is natural to conjecture that the EM-sequence behaves as a typical sequence generated by a binary IID process. In particular, we would expect that the averages of the initial segments of the EM-sequence converge to 1/2; this is called the balance conjecture." The balance conjecture remains open, as far as I know. Jim