  Drift analysis is one of the state-of-the-art techniques for the runtime
analysis of randomized search heuristics (RSHs) such as evolutionary algorithms
(EAs), simulated annealing etc. The vast majority of existing drift theorems
yield bounds on the expected value of the hitting time for a target state,
e.g., the set of optimal solutions, without making additional statements on the
distribution of this time. We address this lack by providing a general drift
theorem that includes bounds on the upper and lower tail of the hitting time
distribution. The new tail bounds are applied to prove very precise
sharp-concentration results on the running time of a simple EA on standard
benchmark problems, including the class of general linear functions.
Surprisingly, the probability of deviating by an $r$-factor in lower order
terms of the expected time decreases exponentially with $r$ on all these
problems. The usefulness of the theorem outside the theory of RSHs is
demonstrated by deriving tail bounds on the number of cycles in random
permutations. All these results handle a position-dependent (variable) drift
that was not covered by previous drift theorems with tail bounds. Moreover, our
theorem can be specialized into virtually all existing drift theorems with
drift towards the target from the literature. Finally, user-friendly
specializations of the general drift theorem are given.
