2 Fixed two typo

The reason the bound you obtain is worse than the advertised bound is that you sum over all $k$, including those $k$ for which the bound on $Q(k)$ is greater than $1$.

Suppose $T$ is a an integer-valued random variable about which we know that $\Pr[T\geq k]\leq (1-\varepsilon)^k X$. Then \begin{align*} E[T]\leq (\log X/\varepsilon) \Pr[T\geq \log X/\varepsilon] + \sum_{k\geq \log X/\varepsilon} \Pr[T\geq k] =(\log X/\varepsilon)+X\sum_{k\geq \log X/\varepsilon}(1-\varepsilon)^k \end{align*} which is $O(\log X/\varepsilon)$.

1

The reason the bound you obtain is worse than the advertised bound is that you sum over all $k$, including those $k$ for which the bound on $Q(k)$ is greater than $1$.

Suppose $T$ is a random variable about which we know that $\Pr[T\geq k]\leq (1-\varepsilon)^k X$. Then \begin{align*} E[T]\leq (\log X/\varepsilon) \Pr[T\geq \log X/\varepsilon] + \sum_{k\geq X/\varepsilon} \Pr[T\geq k] =(\log X/\varepsilon)+X\sum_{k\geq \log X/\varepsilon}(1-\varepsilon)^k \end{align*} which is $O(\log X/\varepsilon)$.