many expected streaks imply high probability for a streak 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.
 A: 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.
A: 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.
A: 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.
