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?
10
-
$\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 SteinCommented Mar 28, 2013 at 11:31
-
$\begingroup$ Actually, we even have $F \le n \, 2^{-n}$, don't we? $\endgroup$– gerwCommented Mar 28, 2013 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 NadeauCommented Mar 28, 2013 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 CipraCommented Mar 28, 2013 at 13:56
-
2$\begingroup$ Some relevant papers are Mark Schilling's papers on long runs, csun.edu/~hcmth031/research.html. $\endgroup$– Ira GesselCommented Mar 28, 2013 at 14:39
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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$.)
answered Mar 28, 2013 at 15:20
-
$\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$ Commented Mar 28, 2013 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 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. $\endgroup$ Commented Mar 28, 2013 at 23:07