method also builds on the observation that if the drift is multiplicative (that is, condition (\[eq:multidrift\]) holds), then at time $t=(1+\ln(s_0/s_{\min}))/\delta$ the expected potential $X^{(t)}$ is at most $s_0/{\mathrm{e}\xspace}$. Afterwards, various methods (variants of Wald’s identity in [@DrosteJW02; @Jagerskupper08] and Markov’s inequality in [@NeumannW07; @BaswanaBDFKN09]) are used to show that the expected stopping time ${\ensuremath{\operatorname{E}}}[T]$ is indeed in this regime. However, the bounds obtained in this way are not best possible. This is demonstrated in Section \[sec:jagerskupper\] where we replace for the proofs in [@Jagerskupper08] the method of expected weight decrease by the above multiplicative drift theorem. This results in an immediate improvement of the leading constant in the main runtime bound of [@Jagerskupper08].

Let $g\colon S\to\mathbb{R}$ be the function defined by $$g(s):=1+\ln\frac{s}{s_{\min}}.$$

Let $ R:=g(S)$ be the image of $g$ and let $\{Z^{(t)}\}_{t\in\mathbb{N}}$ be the sequence of random variables over $ R\cup\{0\}$ given by $$Z^{(t)}:=\begin{cases}
0 & \text{if }X^{(t)}=0,\\
g(X^{(t)}) & \text{otherwise.}
\end{cases}$$

Then $T$ is also the first point in time $t\in\mathbb{N}$ such that $Z^{(t)}=0$. Suppose $T>t$. Then we have $Z^{(t)}=g(X^{(t)})>0$. If $X^{(t+1)}=0$, then also $Z^{(t+1)}=0$ and $$\label{eq:multzero}
Z^{(t)}-Z^{(t+1)}=1+\ln\Big(\frac{X^{(t)}}{s_{\min}}\Big)\ge 1=\frac{X^{(t)}-X^{(t+1)}}{X^{(t)}}.$$ Otherwise, $Z^{(t+1)}=g(X^{(t+1)})$ and again $$\label{eq:multgeneral}
Z^{(t)}-Z^{(t+1)}=\ln\Big(\frac{X^{(t)}}{X^{(t+1)}}\Big)\ge\frac{X^{(t)}-X^{(t+1)}}{X^{(t)}},$$ where the last inequality follows from $$\frac{u}{w}=1+\frac{u-w}{w}\le {\mathrm{e}\xspace}{}^{\frac{u-w}{w}}$$ which implies $$\ln\Big(\frac{u}{w}\Big)\le\frac{u-w}{w}$$ and 