(the all-zero string) in the search space. More precisely, it counts the number of one-bits, where each bit is assigned a weight between one and two, such that bits which have higher weight in the objective function $f$ also have higher weight in $g$.

We show that the drift of the (1+1) EA with respect to $g$ is multiplicative, that is, that condition (\[eq:multidrift\]) holds.

\[lem:pointwise\] Let $n\in\mathbb{N}$ be a positive integer. Let $f\colon\{0,1\}^n\to\mathbb{R}$ be a linear function with monotone weights and let $g\colon\{0,1\}^n\to\mathbb{R}$ be the potential function with $g(x)=\sum_{i=1}^n(1+i/n)x_i$ for all $x\in\{0,1\}^n$.

Let $x\in\{0,1\}^n$ and let $y\in\{0,1\}^n$ be randomly chosen by flipping each bit in $x$ with probability $1/n$. Let $\Delta(x):=g(x)-g(y)$ if $f(y)\le f(x)$ and $\Delta(x)=0$ otherwise. Then $${\ensuremath{\operatorname{E}}}[\Delta(x)]\ge\frac{g(x)}{4{\mathrm{e}\xspace}n}.$$

This lemma implies that *at every point in the search space* the drift is at least linear in the current potential value. Thus, the multiplicative drift condition (\[eq:multidrift\]) holds and Theorem \[thm:ealinear\] follows directly by applying Theorem \[thm:multidrift\].

Since ${\ensuremath{\operatorname{E}}}[\Delta(x)\mid f(y)>f(x)]=0$, we have by the law of total expectation that $$\label{eq:accepted}
{\ensuremath{\operatorname{E}}}[\Delta(x)]={\ensuremath{\operatorname{E}}}[g(x)-g(y)\mid f(y)\le f(x)]\,{\ensuremath{\mathrm{Pr}}}[f(y)\le f(x)].$$

Let $I=\{i\in\{1,\dots,n\}\colon x_i=1\}$. We may distinguish three events (cases).

-   There is no index $i\in I$ such that $y_i=0$ and $f(y)\le f(x)$ holds, that is, 