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?
 A: There is an easy way to get a good upper bound. 
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$.)
