  Hillclimbing is an essential part of any optimization algorithm. An important
benchmark for hillclimbing algorithms on pseudo-Boolean functions $f: \{0,1\}^n
\to \mathbb{R}$ are (strictly) montone functions, on which a surprising number
of hillclimbers fail to be efficient. For example, the $(1+1)$-Evolutionary
Algorithm is a standard hillclimber which flips each bit independently with
probability $c/n$ in each round. Perhaps surprisingly, this algorithm shows a
phase transition: it optimizes any monotone pseudo-boolean function in
quasilinear time if $c<1$, but there are monotone functions for which the
algorithm needs exponential time if $c>2.2$. But so far it was unclear whether
the threshold is at $c=1$.
  In this paper we show how Moser's entropy compression argument can be adapted
to this situation, that is, we show that a long runtime would allow us to
encode the random steps of the algorithm with less bits than their entropy.
Thus there exists a $c_0 > 1$ such that for all $0<c\le c_0$ the
$(1+1)$-Evolutionary Algorithm with rate $c/n$ finds the optimum in $O(n \log^2
n)$ steps in expectation.
