show the following (see, e.g., [@HeY04] where a variant of Algorithm \[alg:oneoneea\] is analyzed). Let $x \in \{0,1\}^n$. Let $y \in \{0,1\}^n$ be the result of one iteration (mutation and selection) of the (1+1) EA started in $x$. Then there exists a $\delta > 0$ such that $$\label{eq:drift}
 {\ensuremath{\operatorname{E}}}[h(y)] \le h(x) - \delta/n.$$ Now, classical drift analysis tells us that in expectation after a number of $h(x)/(\delta/n) = O(n \log n)$ iterations, the potential value is reduced to zero. But $h(x)=0$ implies $f(x)=0$, that is, the (1+1) EA has found the desired optimum.

Using drift analysis to analyze a randomized search heuristic usually bears two difficulties. The first is guessing a suitable potential function $h$. The second, related to the first, is proving that during the search, $f$ and $h$ behave sufficiently similar, that is, we can prove some statement like inequality (\[eq:drift\]). Note that this inequality contains information about $f$ as well, namely implicitly in the fact that $y$ has an at least as good $f$–value as $x$.

A main difficulty in showing that $h$ in (\[eq:logpotential\]) is a suitable potential function is the logarithm around the simple linear function giving weights one and two to the bits. However, 