I have a proof that I understand the most of it except one step
Lemma 10. The expected number of steps the $(1+1)$ EA takes to optimize a linear function with all non-zero weights is $\Omega(n \ln n)$.
Proof. By our assumptions all weights $w_i$ are positive. Since $x_{\text {one }}$ is the only optimum, it is necessary that each bit that is zero after random initialization flips at least once. Hence, the average time until each of these bits has tried to flip at least once is a lower bound on the considered expected time. The following considerations are similar to the example called "coupons collector's problem" by Motwani and Raghavan [14]. Let $T$ denote the random variable describing the first point of time where each of these bits has tried to flip at least once. Since $T$ takes only positive integers, we have $$ E(T)=\sum_{t=1}^{\infty} t \operatorname{Prob}(T=t)=\sum_{t=1}^{\infty} \operatorname{Prob}(T \geqslant t) $$ Without loss of generality $n$ is even. With probability at least $1 / 2$ at least half of the bits are zero after random initialization. $(1-1 / n)^{t-1}$ describes the probability that one bit does not flip at all in $t-1$ steps. So, $1-(1-1 / n)^{t-1}$ is the probability that it flips at least once in $t-1$ steps. Therefore, we have $\left(1-(1-1 / n)^{t-1}\right)^{n / 2}$ as probability that this is the case with $n / 2$ bits. Finally, $1-\left(1-(1-1 / n)^{t-1}\right)^{n / 2}$ is the probability for the event that at least one of $n / 2$ bits never flips in $t-1$ steps. So, we have $$ E(T) \geqslant \frac{1}{2} \sum_{t=1}^{\infty}\left(1-\left(1-\left(1-\frac{1}{n}\right)^{t-1}\right)^{n / 2}\right) $$ $$ \begin{aligned} & \geqslant \frac{1}{2}(n-1)(\ln n)\left(1-\left(1-\left(1-\frac{1}{n}\right)^{(n-1) \ln n}\right)^{n / 2}\right) \\ & \geqslant \frac{1}{2}(n-1)(\ln n)\left(1-\mathrm{e}^{-1 / 2}\right)=\Omega(n \ln n) . \end{aligned} $$
My question is, where does $(n-1)(\ln n)$ come from?
ref: S. Droste et al. / Theoretical Computer Science 276 (2002) 51-81 59
