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

  • $\begingroup$ I hope you guys can help me on the part of $(n-1)\ln n$, since I understand all other parts. $\endgroup$
    – Edee
    Oct 14 at 14:23
  • $\begingroup$ Well, it's somewhat arbitrary. The summand is decreasing in $t$ and non-negative for each $t$, so they lower bound the infinite sum by the sum over the first $(n-1)\ln n$ terms which they then bound by $(n-1)\ln n$ times the term corresponding to $t = (n-1)\ln n$ (though there is a $-1$ missing, though I doubt it's a big deal). So, the inequality that first introduces $(n-1)\ln n$ is valid. Now, the reason they chose $(n-1) \ln n$ is for the last inequality (the last "$\ge$"). $\endgroup$ Oct 15 at 1:52
  • $\begingroup$ so, it's not a simplification by using some series, right? It's just a reasonable lower bound to replace the summand, right? $\endgroup$
    – Edee
    Oct 15 at 5:02
  • $\begingroup$ @Edee you should @ me so I am notified when you respond. What you just said is correct. $\endgroup$ Oct 15 at 18:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.