I have been reading about some randomized algorithms and I appear to be having an issue reproducing what should be a very simple claim, while the rest of the analysis is clear.
Suppose we are given the keys $k \in \lbrace 1, \cdots, n\rbrace$ and we define the random variables $X_k$ to be the number of times we flip heads without seeing tails, using a fair coin so $P[heads] = \frac{1}{2}$, indexed by the value $k$. Let us then define the random variable $\bar{X} = \max_{k} X_k$.
For some $k$, the probability that $X_k$ is at least as big as some value $m$ corresponds to the probability of flipping heads $m$ times in a row, so clearly $P[X_k \geq m] = \frac{1}{2^m}$. If we turn our attention to finding the probability that $\bar{X} \geq m$ for some $m$, we know this will be true as long as at least one value for $k$ exists such that $X_k \geq m$. Thus, $P[\bar{X} \geq m] = P\left[\bigvee_{i=k}^n (X_k \geq m)\right]$. We can use union bound to show that $P\left[\bigvee_{i=k}^n (X_k \geq m)\right] \leq \sum_{k=1}^n P[X_k \geq m] = \frac{n}{2^m}$. This is cool to know because now we can choose $m = c \log n$ and find that $P[\bar{X} \geq c \log n] \leq \frac{1}{n^{c-1}}$, implying that $\bar{X}$ is bounded by $O(\log n)$ in high probability, given a choice for $c > 1$.
My issue is when I then go to try and find the expectation of $\bar{X}$. I have found a claim that says $(1)$ holds.
\begin{align} \mathbb{E}[\bar{X}] &= \sum_{m=1}^{\infty} P[\bar{X} \geq m] \tag{1} \end{align}
I cannot find a way to go from the standard expectation definition in $(2)$ to obtain the claim $(1)$.
\begin{align} \mathbb{E}[\bar{X}] &= \sum_{m=0}^{\infty} m P[\bar{X} = m] \tag{2} \end{align}
I was thinking about something along the lines of
\begin{align} P[\bar{X} = m] &= P[\bar{X} \geq m \wedge \bar{X} < m+1] \\ &= P[\bar{X} < m+1 | \bar{X} \geq m] P[\bar{X} \geq m] \end{align}
but I cannot resolve what the conditional probability term should be, so I feel this is a bad direction. Expression $(1)$ seems to imply that the conditional probability is $\frac{1}{m}$ for a given $m$, but I do not see how to get there.
The analysis of the expectation, given $(1)$ is true, leads to the fact that $\mathbb{E}[\bar{X}] \leq \log n + 2$, which is quite interesting in contrast to the high probability bound. Given $(1)$, the analysis makes sense, but I just cannot see how to arrive at $(1)$. Can anyone help? I feel I am missing something obvious.