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?

$\begingroup$ 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? $\endgroup$ – Noah Stein Mar 28 '13 at 11:31

$\begingroup$ Actually, we even have $F \le n \, 2^{n}$, don't we? $\endgroup$ – gerw Mar 28 '13 at 11:44

1$\begingroup$ 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. $\endgroup$ – Philippe Nadeau Mar 28 '13 at 12:14

1$\begingroup$ 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. $\endgroup$ – Barry Cipra Mar 28 '13 at 13:56

2$\begingroup$ Some relevant papers are Mark Schilling's papers on long runs, csun.edu/~hcmth031/research.html. $\endgroup$ – Ira Gessel Mar 28 '13 at 14:39
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 $nk+1$ possible substrings of length $k$, so the expected number of all$1$ substrings of length $k$ is $(nk+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$.)

$\begingroup$ 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$? $\endgroup$ – Noah Stein Mar 28 '13 at 19:25

$\begingroup$ @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 trietheory (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. $\endgroup$ – Douglas Zare Mar 28 '13 at 23:07