On 4/23/07, James Propp <propp@math.wisc.edu> wrote:

... 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." ...

I haven't inspected the EM sequence directly --- generating a long chunk of it might be a nice exercise in implementing the Knuth-Morris-Pratt algorithm! And I don't know exactly what is meant by "IID". But I did take a quick look at the behaviour of (pseudo-)random de Bruijn sequences recently, and the (standard) deviation of their intervals between successive equal words seems indistinguishable from random. There seems no reason to think that EM --- a sort of cut-price oo-span de Bruijn sequence --- will behave differently; so its Propp discrepancy should be no better than random. Fred Lunnon