does not increase.

Consider the progress $\Delta^{(t)}:={\textsc{OneMax}\xspace}(x^{(t)})-{\textsc{OneMax}\xspace}(x^{(t+1)})$ of the (1+1) EA in the $t$-th iteration. By construction of the (1+1) EA, $\Delta^{(t)}$ cannot be negative. By definition, the number of one-bits $x^{(t)}$ is ${\textsc{OneMax}\xspace}(x^{(t)})$. For each of these one-bits, there is a $(1/n)(1-1/n)^{n-1}\ge 1/({\mathrm{e}\xspace}n)$ chance that only this one-bit is flipped when sampling $y^{(t)}$, thus increasing the value of ${\textsc{OneMax}\xspace}(x^{(t)})$ by one. Hence, $${\ensuremath{\operatorname{E}}}\big[\Delta^{(t)}{\,\big|\,}x^{(t)}\big]\ge\frac{{\textsc{OneMax}\xspace}(x^{(t)})}{{\mathrm{e}\xspace}n}.$$

Thus, multiplicative drift analysis (Theorem \[thm:multidrift\]) immediately gives us the well-known result $${\ensuremath{\operatorname{E}}}[T_{{\textsc{OneMax}\xspace}}]\le{\mathrm{e}\xspace}n\Big(1+\ln{\ensuremath{\operatorname{E}}}\big[{\textsc{OneMax}\xspace}(x^{(0)})\big]\Big)={\mathrm{e}\xspace}n\Big(1+\ln\Big(\frac{n}{2}\Big)\Big).$$

Another elementary linear pseudo-Boolean function is [<span style="font-variant:small-caps;">BinVal</span>]{}. This function maps a bitstring to the binary value it represents (where $x_1$ represents the lowest and $x_n$ the highest bit). $$\label{eq:binval}
{\textsc{BinVal}\xspace}(x)=\sum_{i=1}^n{2^{i-1} x_i}.$$

Again, for $\Delta^{(t)}:={\textsc{BinVal}\xspace}(x^{(t)})-{\textsc{BinVal}\xspace}(x^{(t+1)})$, we have $${\ensuremath{\operatorname{E}}}\big[\Delta^{(t)}{\,\big|\,}x^{(t)}\big]\ge\frac{{\textsc{BinVal}\xspace}(x^{(t)})}{{\mathrm{e}\xspace}n}$$ and thus $${\ensuremath{\operatorname{E}}}[T_{{\textsc{BinVal}\xspace}}]\le{\mathrm{e}\xspace}n\Big(1+\ln{\ensuremath{\operatorname{E}}}\big[{\textsc{BinVal}\xspace}(x^{(0)})\big]\Big)={\mathrm{e}\xspace}n\Big(1+\ln\Big(\frac{2^n-1}{2}\Big)\Big).$$

Note, that the previous inequality gives us only a quadratic upper bound of ${\ensuremath{\mathord{O}}}(n^2)$ for the expected optimization time of the (1+1) EA on [<span style="font-variant:small-caps;">BinVal</span>]{}. However, it is known that for all linear functions — including [<span style="font-variant:small-caps;">BinVal</span>]{}— the expected optimization time of the (1+1) EA is ${\ensuremath{\mathord{O}}}(n\ln n)$. We discuss this in the following subsections and give a simplified proof using multiplicative drift analysis.

Linear Functions
----------------

A classical test problem for the runtime analysis of randomized search heuristics is 