to zero.

Let $J(i)=\{j\in\{i+1,\dots,n\}\colon x_j=0\text{ and }w_j=w_i\}$. For $j\in J(i)$ let $B_{i,j}$ be the event that $y_i=0$, $y_j=1$, and $y_\ell=x_\ell$ for $\ell$ not $i$ or $j$. Then $${\ensuremath{\operatorname{E}}}[\Delta(x)\mid (B_i)]\,{\ensuremath{\mathrm{Pr}}}[(B_i)]=\sum_{j\in J(i)}{\ensuremath{\operatorname{E}}}[\Delta(x)\mid B_{i,j}]\,{\ensuremath{\mathrm{Pr}}}[B_{i,j}].$$ We substitute ${\ensuremath{\operatorname{E}}}[\Delta(x)\mid B_{i,j}]=-\frac{j-i}{n}$ and ${\ensuremath{\mathrm{Pr}}}[B_{i,j}]=\frac{1}{n^2}\big(1-\frac{1}{n}\big)^{n-2}$ in the previous equation. Since these conditional expectations are always negative, we may pessimistically assume that $J(i)=\{i+1,\dots,n\}$ and get $$\sum_{j\in J(i)}{\ensuremath{\operatorname{E}}}[\Delta(x)\mid B_{i,j}]=-\frac{(n-i)}{n}\,\frac{(n+1-i)}{2}\ge -\Big(1-\frac{1}{n}\Big)\frac{(n+1-i)}{2}$$ and therefore $$\label{eq:bi}
{\ensuremath{\operatorname{E}}}[\Delta(x)\mid (B_i)]\,{\ensuremath{\mathrm{Pr}}}[(B_i)]\ge -\frac{1}{n}\Big(1-\frac{1}{n}\Big)^{n-1}\frac{n+1-i}{2n}.$$

Finally, we substitute (\[eq:ai\]) and (\[eq:bi\]) in (\[eq:ab\]) and derive $${\ensuremath{\operatorname{E}}}[\Delta(x)]\ge\frac{1}{n}\Big(1-\frac{1}{n}\Big)^{n-1}\sum_{i\in I}
1-\frac{i-3}{2n}-\frac{n+1-i}{2n}=\frac{1}{n}\Big(1-\frac{1}{n}\Big)^{n-1}\frac{n+2}{4n}\sum_{i\in I}2.$$ Since $g_i=1+i/n\le 2$ for all $i\in I$, we have $\sum_{i\in I}2\ge g(x)$ and therefore $${\ensuremath{\operatorname{E}}}[\Delta(x)]\ge \frac{g(x)}{4{\mathrm{e}\xspace}{}n}$$ which concludes the proof of the lemma.

Distribution-based Versus Point-wise Drift {#sec:jagerskupper}
------------------------------------------

In this subsection we show an almost tight upper bound on the expected optimization time of the (1+1) EA on linear functions.

If we take a closer look at Lemma \[lem:pointwise\], we see that it holds *point-wise*, that is, it guarantees $$\label{eq:pointwise}
{\ensuremath{\operatorname{E}}}\big[g(x^{(t)})-g(x^{t+1}){\,\big|\,}x^{(t)}=x\big]\ge\frac{g(x)}{4{\mathrm{e}\xspace}n}$$ for all $x\in\{0,1\}^n\setminus\{(0,\dots,0)\}$. This is far stronger than the positive *average* drift condition (\[eq:multidrift\]) which only requires

$$\label{eq:average}
{\ensuremath{\operatorname{E}}}\big[g(x^{(t)})-g(x^{t+1}){\,\big|\,}g(x^{(t)})=s, T>t\big]\ge\delta s$$

for all $s\in\mathbb{R}$ such that ${\ensuremath{\mathrm{Pr}}}[g(x^{(t)})=s, T>t]>0$.

The advantage of the stronger point-wise drift assumption is that it immediately guarantees that the result of Theorem \[thm:ealinear\] holds 