  This erratum points out an error in the simplified drift theorem (SDT)
[Algorithmica 59(3), 369-386, 2011]. It is also shown that a minor modification
of one of its conditions is sufficient to establish a valid result. In many
respects, the new theorem is more general than before. We no longer assume a
Markov process nor a finite search space. Furthermore, the proof of the theorem
is more compact than the previous ones. Finally, previous applications of the
SDT are revisited. It turns out that all of these either meet the modified
condition directly or by means of few additional arguments.
