5
$\begingroup$

In CLRS, "Intro to Algorithms" section 5.4.3 the following is shown. If a fair coin is flipped n times, the expected number of streaks of consecutive heads of length (1/2)log(n) is $ \Theta (\sqrt n)$. So, for large n, "we expect there are a large number of streaks of length (1/2)log(n)."

Then the book continues, "Therefore, one streak of such a length is likely to occur."

Is that a correct conclusion? To conclude that there is high probability for such a streak isn't it neccessary to bound the variance besides for showing a large expectation?

Thanks.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
8
$\begingroup$

You're right that something more is needed to conclude that the probability of no streak is small.

In this particular case, one can easily get a lower bound by partitioning the sequence of coin flips into $2 n/ \log(n)$ disjoint sequences of length $\log(n)/2$ each. The probability of each such subsequence being all heads is $2^{-\log(n)/2}=\theta(1/\sqrt{n})$. Since the subsequences are disjoint, these events are independent, so the probability that they all fail to occur is $$\big(1-\frac{1}{\sqrt{n}}\big)^{2 n/\log(n)} \approx e^{-2\sqrt{n}/\log(n)} .$$

[I am ignoring rounding effects which would change the exponent by a constant factor]

The truth is that this probability should be of order $e^{-\sqrt{n}}$, but that requires a bit more work.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Ori, thanks for your answer. But isn't your bound a very loose interpretation of "likely to occur"? Or did I miss your point? $\endgroup$
    – user31594
    Commented Feb 20, 2013 at 0:21
  • $\begingroup$ It looks like a rigorous proof to me. It shows that the probability of having a streak in some limited places goes to 1, which implies that the probability of a streak anywhere also goes to 1. $\endgroup$
    – Brendan McKay
    Commented Feb 20, 2013 at 1:22
  • $\begingroup$ What Brendan said. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Feb 20, 2013 at 23:52
3
$\begingroup$

It seems to me that you're right; in principle there could be a few sequences with many streaks and many sequences with no streaks, yielding a high expected value and yet a low probability for a streak.

On the other hand, fix $k$ and let $f(n)$ be the number of sequences of length $n$ that contain a streak of heads having length $k$. Then clearly $f(1)=f(2)=...=f(k-1)=0$ and $f(k)=1$. And (unless I screwed up) it's not hard to get the following recursion: $$f(n)=2^{n-k}+(n-k)2^{n-k-1}-\sum_{j=k}^{n-k-1}f(j)2^{n-k-1-j}$$

The probability $g(n)$ that a randomly chosen sequence of length $n$ contains a string of heads of length $k$ is $f(n)/2^n$, which gives us the following recursion:

$$g(1)=g(2)=...=g(k-1)=0$$ $$g(k)=1/2^k$$ $$g(n)= {1\over 2^{k+1}}\left(2+n-k-\sum_{j=k}^{n-k-1}g(j)\right)$$

The generating function for $g$ is then

$${x^k\over(1-x)(2^k-2^{k-1}x-2^{k-2}x^2-...-x^k)}$$

The question, then, is what the $n$th power series coefficient looks like when $n$ is approximately $e^{2k}$. I don't have a theorem for you, but numerical tests suggest that this is very close to 1. In particular, even for $k=3$, we're looking at roughly the 403'd coefficient, which is approximately .9999999999999975 --- and this increases monotonically with $k$.

In other words, yes, at least one such streak is very likely to occur.

Improve this answer
$\endgroup$
2
  • $\begingroup$ To finish the other 1% of the proof first show that the large factor in the denominator has no zeros of modulus $\le 1$. I think they all have modulus 2. Then note that the coefficients are asymptotically equal to those of $x^k/(1-x)$, namely 1, since the difference between your generating function and $x^k/(1-x)$ has radius of convergence greater than 1. This shows the coefficients are exponentially close to 1. (This is Darboux's method.) I think that in fact the denominator factors into linear factors involving roots of unity, so you can use partial fractions and get a full expansion. $\endgroup$
    – Brendan McKay
    Commented Feb 20, 2013 at 1:32
  • $\begingroup$ Ooops, I interpretted the large term in your denominator as having alternating signs, but now I see the signs are negative except for the leading term. The method still applies except that partial fractions approach will be harder. The smallest zero of the large term is still greater than 1, which is what you need. $\endgroup$
    – Brendan McKay
    Commented Feb 20, 2013 at 7:29
2
$\begingroup$

The broken logic in the book can bite in many places. Here is a simple example. If we make a random graph with $n$ vertices and edge probability $3/n$, the expected number of hamiltonian cycles goes to infinity exponentially fast, yet the probability of having any hamiltonian cycle at all goes to 0 exponentially fast.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .