the potential function $\widetilde{g}\colon \{0,1\}^n \to \mathbb{R}$ such that $$\label{eq:heyao}
\widetilde{g}(x)=\ln\Big(1+\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor}x_i+\sum_{i=\lfloor \frac{n}{2}\rfloor +1}^n c x_i\Big)$$ for all $x\in\{0,1\}^n$. For this function, with $1<c\le 2$ chosen arbitrarily, they show that for all $x\in\{0,1\}^n\setminus\{(0,\dots,0)\}$ $${\ensuremath{\operatorname{E}}}\big[\widetilde{g}(x^{(t)})-\widetilde{g}(x^{(t+1)}){\,\big|\,}x^{(t)}=x\big]=\Omega(1/n).$$ Afterwards, they apply Theorem \[thm:additivedrift\] to show Theorem \[thm:ealinear\]. However, while this approach strongly reduced the complexity of the proof in [@DrosteJW02], introducing the natural logarithm into the potential function still resulted in unnecessary case distinctions and even inconsistencies in an early version of the proof [@HeY01; @HeY02AI].

The Drift for Linear Functions is Multiplicative
------------------------------------------------

In this subsection, we give a simple proof of the fact that the (1+1) EA optimizes any linear function in expected time ${\ensuremath{\mathord{O}}}(n \log n)$. Our proof is based on the theorem of multiplicative drift (Theorem \[thm:multidrift\]). Although proofs for Theorem \[thm:ealinear\] are known [@DrosteJW02; @HeY04; @Jagerskupper08], we present this alternative approach to demonstrate the strength of the multiplicative version of the classical drift theorem.

In order to apply Theorem \[thm:multidrift\] we need a suitable potential function. For this, we choose the function $g\colon \{0,1\}^n \to \mathbb{R}$ such that[^3]

$$g(x)=\sum_{i=1}^n\Big(1+\frac{i}{n}\Big)x_i$$

for all $x\in\{0,1\}^n$. This function defines the potential as the *weighted* distance of the current search point to the optimum 