thus $$\ln\Big(\frac{w}{u}\Big)\ge\frac{w-u}{w}.$$ for all $u,w\in\mathbb{R}$.

Hence, by (\[eq:multzero\]) and (\[eq:multgeneral\]), independent of whether $Z^{(t+1)}=0$ or $Z^{(t+1)}\neq 0$, we have $$Z^{(t)}-Z^{(t+1)}\ge\frac{X^{(t)}-X^{(t+1)}}{X^{(t)}}.$$

Let $r\in R$. Since $g$ is bijective, there exist a unique $s\in S$ such that $r=g(s)$. Moreover, the events $Z^{(t)}=r$ and $X^{(t)}=s$ coincide. Hence, we have by condition (\[eq:multidrift\]) that $${\ensuremath{\operatorname{E}}}[Z^{(t)}-Z^{(t+1)}\mid Z^{(t)}=r]\ge\frac{{\ensuremath{\operatorname{E}}}[X^{(t)}-X^{(t+1)}\mid X^{(t)}=s]}{s}\ge\delta.$$

Finally, we apply Theorem \[thm:additivedrift\] for additive drift and obtain for $s\in S$ with ${\ensuremath{\mathrm{Pr}}}[X^{(0)}=s]>0$ that $${\ensuremath{\operatorname{E}}}[T\mid X^{(0)}=s]={\ensuremath{\operatorname{E}}}[T\mid Z^{(0)}=g(s)]\le\frac{g(s)}{\delta}\le\frac{1+\ln(s/s_{\min})}{\delta}$$ which concludes the proof of the theorem.

In Section \[sec:linear\] and Section \[sec:combinatorial\], we demonstrate the strength of this new tool by applying it to four well-known problems: the problem of minimizing linear pseudo-Boolean functions, the minimum spanning tree problem, the single-source shortest path problem, and the problem of finding Euler tours.

The Runtime of the (1+1) Evolutionary Algorithm on Pseudo-Boolean Functions {#sec:linear}
===========================================================================

Many optimization problems can be phrased as the problem of maximizing or minimizing a pseudo-Boolean function $f\colon \{0,1\}^n \to \mathbb{R}$ where $n$ is a positive integer. In the setting of randomized search heuristics, such a function $f$ is considered to be a black-box, that is, the optimization process can access $f$ only by evaluating it at limited number of points in $\{0,1\}^n$.

\[alg:oneoneea\] choose 