5
$\begingroup$

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?

$\endgroup$
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 Stein
    Mar 28, 2013 at 11:31
  • $\begingroup$ Actually, we even have $F \le n \, 2^{-n}$, don't we? $\endgroup$
    – gerw
    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$ 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$ 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 Gessel
    Mar 28, 2013 at 14:39

1 Answer 1

3
$\begingroup$

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$.)

$\endgroup$
2
  • $\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, 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$ Mar 28, 2013 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.