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

CC BY-SA 4.0
2023-10-14T14:23:04.677Z
I hope you guys can help me on the part of $(n-1)\ln n$, since I understand all other parts.
Edee
CC BY-SA 4.0
2023-10-15T00:40:35.017Z
Cross-posted: https://cs.stackexchange.com/q/162459/755, https://cstheory.stackexchange.com/q/53432/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
CC BY-SA 4.0
2023-10-15T01:52:23.750Z
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$").
mathworker21
CC BY-SA 4.0
2023-10-15T05:02:45.800Z
so, it's not a simplification by using some series, right? It's just a reasonable lower bound to replace the summand, right?
Edee
CC BY-SA 4.0
2023-10-15T18:11:01.887Z
@Edee you should @ me so I am notified when you respond. What you just said is correct.
mathworker21
CC BY-SA 4.0
2023-10-17T00:49:03.347Z
thanks a lot! @mathworker21, I though it used to attach @ automatically when the reply is written, lol.
Edee
CC BY-SA 4.0
2023-10-17T02:11:06.303Z
@Edee It depends. For example, if I was the only one who had commented under your post, then yes, it would have @-ed me automatically.
mathworker21
<approximation-algorithms><lower-bounds><randomized-algorithms>
How to understand this evolutionary algorithm lower bound calculation?
Edee
# How to understand this evolutionary algorithm lower bound calculation?

(Asked by: username_0 on 2023-10-14)

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

**Tags:** approximation-algorithms, lower-bounds, randomized-algorithms
> **Comments:**
> **username_0**: I hope you guys can help me on the part of $(n-1)\ln n$, since I understand all other parts.  
> **username_1**: Cross-posted: https://cs.stackexchange.com/q/162459/755, https://cstheory.stackexchange.com/q/53432/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  
> **username_2**: 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$").  
> **username_0**: so, it's not a simplification by using some series, right? It's just a reasonable lower bound to replace the summand, right?  
> **username_2**: @Edee you should @ me so I am notified when you respond. What you just said is correct.  
> **username_0**: thanks a lot! @mathworker21, I though it used to attach @ automatically when the reply is written, lol.  
> **username_2**: @Edee It depends. For example, if I was the only one who had commented under your post, then yes, it would have @-ed me automatically.  

---

## 0 answers

