Consider a game in which you flip a coin until you flip tails. Your score is then the number of heads you flipped. So, for example, the sequence $H$, $H$, $H$, $T$ has a score of three, while the sequence $T$ has score zero. You play this game $n$ times. Let $X$ denote your maximum score in the game. I'd like to know what $E[X]$ looks like as a function of $n$.
Here's what I know so far. The probability that your score is greater than or equal to some number $k$ is equal to $$\left(1 - \left(1 - 2^{-k}\right)^n\right),$$ which is the probability that you don't have all scores strictly below $k$. We can then write $E[X]$ as follows:
$$\begin{aligned} E[X] & = \sum_{k = 0}^{\infty} k \cdot Pr[X = k] \\ & = \sum_{k = 1}^{\infty} Pr[X \ge k] \\ & = \sum_{k = 1}^{\infty} \left(1 - \left(1 - 2^{-k}\right)^n\right). \end{aligned}$$
At this point, I'm completely out of my league in terms of sequence manipulations, and I'm not sure how to simplify this or even interpret what this looks like.
I know that I can write
$$(1 - 2^{-k})^n = ((1 - 2^{-k})^{2^{k}})^{n 2^{-k}} \approx e^{-n 2^{-k}},$$
which lets me rewrite the sum as being (approximately)
$$\sum_{k = 1}^{\infty} (1 - e^{-n 2^{-k}}),$$
but (1) I don't know how much this messes up the estimate and (2) I still have no idea how to simplify or manipulate this sum.
I know that for $n \ll 2^k$ that the term in the sum is close to 0 and that for $n \gg 2^k$ the term in the sum is close to 1, so I'm expecting this sum to come out to something like $\alpha \log_2 n + o(\log_2 n)$ or something like that, but I'm not sure how to rigorously quantify this.
Is there a nice way to simplify this sum or otherwise get a decent approximation of it?
(Context: I'm teaching the HyperLogLog estimator and while the full analysis is way too complex to put into a lecture, I'd still like to give some intuitions as to why it works. The game discussed here is equivalent to looking at leading zeros in a random hash, and the distribution of the maximum score is useful for analyzing the expected value of a simple estimator.)
Since there is a transition in the sum around $k=\log_2n$ as the OP points out, let's define $y=\log_2n-\log_2\log n$ and $z=\log_2n+\log_2\log_2n$. We have \begin{align*} \sum_{1\le k\le y} (1 - (1 - 2^{-k})^n) &\ge (y-1)(1-(1-2^{-y})^n) \\ &= (y-1)(1-(1-\tfrac{\log_e n}n)^n) \\ &= (y-1)(1-(e^{(\log_e n)/n})^n) = (y-1)(1-\tfrac1n). \end{align*} On the other hand, using $(1-t)^n \ge 1-tn$ for $0\le t\le 1$, we also have \begin{align*} \sum_{k>z} (1 - (1 - 2^{-k})^n) &\le \sum_{k>z} n2^{-k} < n2^{1-z} = \frac2{\log_2 n}. \end{align*} Therefore the entire series is at least $y(1-\tfrac1n)-1 = \log_2n+O(\log_2\log n)$ and at most $z + \frac2{\log_2n} = \log_2n+O(\log_2\log n)$ as well.