since the optimization progress for linear functions is faster if we are further away from the optimum, that is, have more one-bits, this seems difficult to avoid.

Multiplicative Drift Analysis
-----------------------------

We present a way to ease to use of drift analysis in such settings. Informally, our method applies if we have a potential function $g$ satisfying $$\label{eq:drift2}
 {\ensuremath{\operatorname{E}}}[g(y)] \le (1 - \delta)g(x)$$ in the notation above. That is, we require a progress which *multiplicatively* depends on the current potential value. For this reason we call the method *multiplicative drift analysis*. We will see that for a number of problems such potential functions are a natural choice.

This new method allows us to largely separate the structural analysis of an optimization process from the actual calculation of a bound on the expected optimization time. Moreover, the runtime bounds obtained by multiplicative drift analysis are often sharper than those resulting from previously used techniques.

Our Results
-----------

We apply this new tool, multiplicative drift analysis, to the already mentioned problem of optimizing linear functions over $\{0,1\}^n$. This yields a simplified proof of the $O(n\log n)$ bound on the optimization time of the (1+1) EA. Similar to the proof using the classical 