# Maximal chain of 1s in binary strings

Let $S$ be the set of $2^n$ binary $n$-bit strings. For every $x\in S$, let $f(x)$ is the maximal chain of bits 1 in $x$. So Can we find a good upper bound of $$F(n)=\frac{\sum_{x\in S}f(x)}{2^n}$$ Of course, $O(1)\le F(n) \le O(n)$. I think the upper bound is a constant or $O(\log n)$. Can anyone help me?

-
Well $1$ is an upper bound, but it is a pretty silly one. A slightly better but still bad one is $\frac{1}{2}$. What do you mean by "the" upper bound? – Noah Stein Mar 28 '13 at 11:31
Actually, we even have $F \le n \, 2^{-n}$, don't we? – gerw Mar 28 '13 at 11:44
One can easily write down the length generating function for strings where f(x)<=k, and from this the one for your quantity F(n). From the expression thus obtained, one may probably perform some asymptotic analysis (cf. works of Odlyzko or Flajolet/sedgewick), and obtain precise upper bounds or even asymptotic equivalents. – Philippe Nadeau Mar 28 '13 at 12:14
Consider an interpretation. Think of, say a basketball team whose wins and losses are determined by the toss of a coin. The function $f$ is the length of the longest win streak in an $n$-game season, so $F$ is the expected length of the longest win streak. It seems implausible to expect $F$ to be bounded by a constant. – Barry Cipra Mar 28 '13 at 13:56
Some relevant papers are Mark Schilling's papers on long runs, csun.edu/~hcmth031/research.html. – Ira Gessel Mar 28 '13 at 14:39

The probability that there is a streak of length $k$ is at most the expected number of streaks of $1$s length $k$, which is at most the expected number of all-$1$ substrings of length $k$ (which may overlap). It is easy to get the last expected value. There are $n-k+1$ possible substrings of length $k$, so the expected number of all-$1$ substrings of length $k$ is $(n-k+1)2^{-k} \lt n /2^k$. For $k = \lceil \log_2 n \rceil + c$ this gives us an upper bound of $1/2^c$ for the probability that there is a streak of length $\lceil \log_2 n \rceil + c$. So, the average excess over $\lceil \log_2 n \rceil$ is at most $1$, and the average length of the longest streak is at most $\lceil \log_2 \rceil + 1$.
Of course, it's not clear that this upper bound is good until you get a lower bound which is close to this. I think the value should be something like $(\log_2 n) -1$. (Actually, my guess is that the difference from $\log_2 n$ is not asymptotically constant, but fluctuates depending on the fractional part of $\log_2 n$.)
Interesting. Do you have a feel for an intuitive reason that the fractional part of $\log_2 n$ should have anything to do with it for large $n$? – Noah Stein Mar 28 '13 at 19:25
@Noah Stein: There is often some dependence on the fractional part of $\log_2 n$ in problems where $n$ might behave like $n/2$, but there could be some sort of transition between $n/2$ and $n$. The fluctuations between $n/2$ and $n$ may not die out. This happens in trie-theory (some restricted binary trees, see Flajolet and Sedgewick) and in problems like mathoverflow.net/questions/11255/…. Schilling's papers confirm the dependence on the fractional part of $\log_2 n$ both for the mean and variance. – Douglas Zare Mar 28 '13 at 23:07