The discrepancy of the lex-least de Bruijn sequence

摘要

We answer the following question: What is the discrepancy of the lexicographically least binary de Bruijn sequence? Here, "discrepancy" refers to the maximum (absolute) difference between the number of ones and the number of zeros in any initial segment of the sequence. We show that the answer is (-) (2(n) log n).