General Drift Analysis with Tail Bounds∗
Carsten Witt
DTU Compute
Technical University of Denmark
2800 Kgs. Lyngby
Denmark
cawi@dtu.dk

arXiv:1307.2559v3 [] 2 Jun 2017

Per Kristian Lehre
School of Computer Science
University of Birmingham
Birmingham, B15 2TT
United Kingdom
P.K.Lehre@birmingham.ac.uk

June 5, 2017

Abstract
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.

∗

A preliminary version of this paper appeared in the proceedings of ISAAC 2014 [27].

1

Contents
1 Introduction

2

2 Preliminaries

4

3 General Drift Theorem

7

4 Applications of the Tail Bounds
4.1 OneMax, Linear Functions and LeadingOnes . . . . . . . . . . . . . . . . .
4.2 An Application to Probabilistic Recurrence Relations . . . . . . . . . . . . .

12
13
22

5 Conclusions

25

A Existing Drift Theorems as Special Cases
A.1 Variable Drift and Fitness Levels . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Multiplicative Drift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29
29
31

B Fitness Levels Lower and Upper Bounds as Special Cases

33

C Non-monotone Variable Drift

34

1

Introduction

Randomized search heuristics (RSHs) such as simulated annealing, evolutionary algorithms
(EAs), ant colony optimization etc. are highly popular techniques in black-box optimization, i. e., the problem of optimizing a function with only oracle access to the function.
These heuristics often imitate some natural process, and are rarely designed with analysis
in mind. Their extensive use of randomness, such as in the mutation operator, render the
underlying stochastic processes non-trivial. While the theory of RSHs is less developed
than the theory of classical, randomized algorithms, significant progress has been made in
the last decade [3, 29, 20]. This theory has mainly focused on the optimization time, which
is the random variable TA,f defined as the number of oracle accesses the heuristic A makes
before the maximal argument of f is found. Most studies considered the expectation of
TA,f , however more information about the distribution of the optimisation time is often
needed. For example, the expectation can be deceiving when the runtime distribution has
a high variance. Also, tail bounds can be helpful for other performance measures, such as
fixed-budget computation which seeks to estimate the approximation-quality as a function
of time, [11].
Results on the runtime of RSHs were obtained after relevant analytical techniques were
developed, some adopted from other fields, others developed specifically for RSHs. Drift
analysis a central method for analyzing the hitting time of stochastic processes and was
introduced to the analysis of simulated annealing as early as in 1988 [34]. Informally, it
allows long-term properties of a discrete-time stochastic process (Xt )t∈N0 to be inferred

2

from properties of the one-step change ∆t := Xt − Xt+1 . In the context of EAs, one has
been particularly interested in the random variable Ta defined as the smallest t such that
Xt ≤ a. For example, if Xt represents the “distance” of the current solution in iteration t
to an optimum, then T0 is the optimization time.
Since its introduction to evolutionary computation by He and Yao in 2001 [18], drift
analysis has been widely used to analyze the optimization time of EAs. Many drift theorems
have been introduced, such as additive drift theorems [18], multiplicative drift [9, 12],
variable drift [21, 28, 33], and population drift [24]. Different assumptions and notation
used in these theorems make it hard to abstract out a unifying statement.
Drift analysis is also used outside theory of RSHs, for example in queuing theory [5, 14].
The widespread use of these techniques in separated research fields has made it difficult to
get an overview of the drift theorems. Drift analysis is also related to other areas, such as
stochastic differential equations and stochastic difference relations.
Most drift theorems used in the theory of RSHs relate to the expectation of the hitting
time Ta , and there are fewer results aboutP
the tails Pr(Ta > t) and Pr(Ta < t). From the
simple observation that Pr(Ta > t) ≤ Pr( ti=0 ∆i < a − X0 ), the problem is reduced to
bounding the deviation of a sum of random variables. If the ∆t were independent and identically distributed, then one would be in the familiar scenario of Chernoff/Hoeffding-like
bounds. The stochastic processes originating from RSHs are rarely so simple, in particular
the ∆t are often dependent variables, and their distributions are not explicitly given. However, bounds on the form E(∆t | Xt ) ≥ h(Xt ) for some function h often hold. The drift
is called variable when h is a non-constant function. The variable drift theorem provides
bounds on the expectation of Ta given some conditions on h. However, there have been no
general tail bounds from a variable drift condition. The only results in this direction seem
to be the tail bounds for probabilistic recurrence relations from [22]; however, this scenario
corresponds to the specific case of non-increasing Xt .
Our main contribution is a new, general drift theorem that provides sharp concentration
results for the hitting time of stochastic processes with variable drift, along with concrete
advice and examples how to apply it. The theorem is used to bound the tails of the
optimization time of the well-known (1+1) EA [13] to the benchmark problems OneMax
and LeadingOnes, as well as the class of linear functions, which is an intensively studied
problem in the area [37]. Surprisingly, the results show that the distribution is highly
concentrated around the expectation. The probability of deviating by an r-factor in lower
order terms decreases exponentially with r. In a different application outside the theory of
RSHs, we use drift analysis to analyze probabilistic recurrence relations and show that the
number of cycles in a random permutation of n elements is sharply concentrated around
the expectation ln n. As a secondary contribution, we prove that our general drift theorem
can be specialized into virtually all variants of drift theorems with drift towards the target
(in particular, variable, additive, and multiplicative drift) that have been scattered over the
literature on runtime analysis of RSHs. Unnecessary assumptions such as discrete or finite
search spaces will be removed from these theorems.
This paper is structured as follows. Section 2 introduces notation and basics of drift
analysis. Section 3 presents the general drift theorem with tail bounds and suggestions

3

for user-friendly corollaries. Section 4 applies the tail bounds from our theorem. Sharpconcentration results on the running time of the (1+1) EA on OneMax, LeadingOnes
and general linear functions are obtained. The application outside the theory of RSHs with
respect to random recurrence relations is described at the end of this section (Section 4.2).
In all these applications, the probability of deviating by an r-factor in lower order terms of
the expected time decreases exponentially with r. Appendix A demonstrates the generality
of the theorem by identifying a large number of drift theorems from the literature as special
cases. We finish with some conclusions.

2

Preliminaries

We analyze time-discrete stochastic processes represented by a sequence of non-negative
random variables (Xt )t∈N0 . For example, Xt could represent a certain distance value of an
RSH from an optimum. In particular, Xt might aggregate several different random variables
realized by an RSH at time t into a single one. In contrast to existing drift theorems, we do
not assume that the state space is discrete (e. g., all non-negative integers) or continuous
but only demand that it is bounded, non-negative and includes the “target” 0.
We adopt the convention that the process should pass below some threshold a ≥ 0
(“minimizes” its state) and define the first hitting time Ta := min{t | Xt ≤ a}. If the
actual process seeks to maximize its state, typically a straightforward mapping allows us
to stick to the convention of minimization. In an important special case, we are interested
in the hitting time T0 of target state 0; for example when a (1+1) EA, a very simple RSH,
is run on the well-known OneMax problem and were are interested in the first point of
time where the number of zero-bits becomes zero. Note that Ta is a stopping time and that
we assume that the stochastic process is adapted to some filtration (Ft )t∈N0 , such as its
natural filtration σ(X0 , . . . , Xt ).
The expected one-step change δt := E(Xt − Xt+1 | Ft ) for t ≥ 0 is called drift. Note that
δt in general is a random variable since the outcomes of X0 , . . . , Xt are random. Suppose we
manage to bound δt from below by some δ∗ > 0 for all possible outcomes of δt , where t < T .
Then we know that the process decreases its state (“progresses towards 0”) in expectation
by at least δ∗ in every step, and the additive drift theorem (see Theorem 1 below) will
provide a bound on T0 that only depends on X0 and δ∗ . In fact, the very natural-looking
result E(T0 | X0 ) ≤ X0 /δ∗ will be obtained. However, bounds on the drift might be more
complicated. For example, a bound on δt might depend on Xt or states at even earlier points
of time, e. g., if the progress decreases as the current state decreases. This is often the case
in applications to EAs. However, for such algorithms the whole “history” is rarely needed.
Simple EAs and other RSHs are Markov processes such that often δt = E(Xt − Xt+1 | Xt )
for an appropriate Xt .
With respect to Markov processes on discrete search spaces, drift conditions traditionally
use conditional expectations such as E(Xt − Xt+1 | Xt = i) and bound these for arbitrary
i > 0 instead of directly bounding the random variable E(Xt − Xt+1 | Xt ) on Xt > 0.
As pointed out, the drift δt in general is a random variable and should not be confused
with the “expected drift” E(δt ) = E(E(Xt − Xt+1 | Ft )), which rarely is available since it
4

averages over the whole history of the stochastic process. Drift is based on the inspection
of the progress from one step to another, taking into account every possible history. This
one-step inspection often makes it easy to come up with bounds on δt . Drift theorems could
also be formulated based on expected drift; however, this might be tedious to compute. See
[19] for one of the rare analyses of “expected drift”, which we will not get into in this paper.
We now present the first drift theorem for additive drift. It is based on [18], from which
we removed the unnecessary assumptions that the search space is discrete and the Markov
property. We only demand a bounded state space.
Theorem 1 (Additive Drift, following [18]). Let (Xt )t∈N0 , be a stochastic process over a
bounded state space S ⊆ R+
0 . Then:
(i) If E(Xt − Xt+1 ; Xt > 0 | Ft ) ≥ δu then E(T0 | F0 ) ≤

X0
δu .

(ii) If E(Xt − Xt+1 ; Xt > 0 | Ft ) ≤ δℓ then E(T0 | F0 ) ≥

X0
δℓ .

Proof. This proof uses martingale theory and resembles the approach in [6, 25]. It is simpler
than the original proof by [18].
In the following, we show only the upper bound since the lower bound is proven symmetrically. Moreover, we assume δu > 0 since the statement is trivial otherwise. We define
the stopped process Yt = Xt∧T0 + (t ∧ T0 )δu , where t ∧ T0 = min{t, T0 }. We prove that Yt is
a super-martingale. More precisely, on the one hand, we get for t < T0 by induction that
E(Yt+1 | Ft ) = E(Xt+1 + (t + 1)δu | Ft )

≤ Xt − δu + (t + 1)δu = Yt ,

where the inequality uses the drift condition. On the other hand, for t ≥ T0 , E(Yt+1 | Ft ) =
Yt , which altogether proves E(Yt+1 | Ft ) ≤ Yt .
The aim is to apply the optional stopping theorem with respect to the super-martingale
Yt , t ∈ N0 and the stopping time T0 . If we can prove that E(T0 | F0 ) < ∞ then all
conditions of the optional stopping theorem are satisfied and we get
E(YT0 | F0 ) ≤ E(Y0 | F0 ) = X0
hence
E(XT0 + T0 δ | F0 ) ≤ X0 ,
which implies
E(T0 | F0 ) ≤ (X0 − E(XT0 | F0 ))/δu = (X0 − 0)/δu = X0 /δu .
Hence, we are left with the claim E(T0 | F0 ) < ∞.
To show the claim, we exploit the uniform drift bound E(Yt − Yt+1 ; Yt > 0 | Ft ) ≥ δu
and the fact that the state space is bounded and non-negative. Note that Yt < δu implies
Yt = 0 since otherwise we would contradict the drift bound. Moreover, since the state space
is bounded, there is some constant r > 1 depending on both the largest state and δu such
5

that E(Yt+1 ; Yt > 0 | Ft ) ≤ Yt /r. We will use the last inequality to prove that E(Yt | F0 )
converges exponentially to 0, from which we finally will derive our claim.
We first observe that E(Yt+1 | Ft ) = E(Yt+1 ; Yt > 0 | Ft ) + E(Yt+1 ; Yt = 0 | Ft ) =
E(Yt+1 ; Yt > 0 | Ft ) since Yt = 0 implies Yt+1 = 0. From E(Yt+1 ; Yt > 0 | Ft ) ≤ Yt /r
we then get
E(Yt+1 | Ft ) ≤ Yt /r
and therefore
E(Yt+2 | Ft ) = E(E(Yt+2 | Ft+1 ) | Ft ) ≤ E(Yt+1 | Ft )/r.
Applying the bound on E(Yt+1 | Ft ) once again, we get E(Yt+2 | Ft ) ≤ Yt /r 2 and inductively
E(Yt | F0 ) ≤ Y0 /r t for all t ∈ N.
To finally bound E(T0 | F0 ) from above, we will use the identity
E(T0 | F0 ) =

∞
X
t=1

∞
∞
X
X
(1 − Pr(Yt = 0 | F0 )).
(1 − Pr(Yt−1 = 0 | F0 )) ≤
Pr(T0 ≥ t | F0 ) =
t=1

t=1

Hence, we need to show that (1 − Pr(Yt = 0 | F0 )) converges to 0 sufficiently fast. To
this end, we use our observation Pr(Yt = 0) = 1 − Pr(Yt ≥ δu ) made above. By Markov’s
inequality, Pr(Yt ≥ δu ) ≤ E(Yt )/δu . Combining this with our bound on E(Yt ) from above,
we get
Y0
Pr(Yt ≥ δu | F0 ) ≤
δu r t
Since Y0 < ∞, δu > 0 and r > 1, we finally conclude
E(T0 | F0 ) ≤

∞
X
t=0

(1 − Pr(Yt = 0 | F0 )) ≤

∞
X
Y0
<∞
δu r t
t=0

as suggested.
Summing up, additive drift is concerned with the very simple scenario that there is a
progress of at least δu from all non-optimal states towards the target in (i) and a progress
of at most δℓ in (ii). Since the δ-values are independent of Xt , one has to use the worst-case
drift over all non-optimal Xt . This might lead to very bad bounds on the first hitting time,
which is why more general theorems (as mentioned in the introduction) were developed.
Interestingly, these more general theorems are often proved based on Theorem 1 using
an appropriate mapping (sometimes called Lyapunov function, potential function, distance
function or drift function) from the original state space to a new one. Informally, the
mapping “smoothes out” position-dependent drift into an (almost) position-independent
drift. We will use the same approach in the following.

6

3

General Drift Theorem

In this section, we present our general drift theorem. As pointed out in the introduction,
we strive for a very general statement, which is partly at the expense of simplicity. More
user-friendly specializations will be given later. Nevertheless, the underlying idea of the
complicated-looking general theorem is the same as in all drift theorems. We look into the
one-step drift E(Xt − Xt+1 | Ft ) and assume we have a (upper or lower) bound h(Xt ) on
the drift, which (possibly heavily) depends on Xt . Based on h, we define a new function
g (see Remark 2), with the aim of “smoothing out” the dependency, and the drift w. r. t.
g (formally, E(g(Xt ) − g(Xt+1 ) | Ft )) is analyzed. Statements (i) and (ii) of the following
Theorem 3 provide bounds on E(T0 ) based on the drift w. r. t. g. In fact, g can be defined in
a very similar way as in existing variable-drift theorems [21, 28, 33], such that Statements (i)
and (ii) can be understood as generalized variable drift theorems for upper and lower bounds
on the expected hitting time, respectively.
Statements (iii) and (iv) are concerned with tail bounds on the hitting time. Here
moment-generating functions (mgfs.) of the drift w. r. t. g come into play, formally
E(e−λ(g(Xt )−g(Xt+1 )) | Ft )
is bounded. Again for generality, bounds on the mgf. may depend on the point of time t,
as captured by the bounds βu (t) and βℓ (t). We will see an example in Section 4 where the
mapping g smoothes out the position-dependent drift into a (nearly) position-independent
and time-independent drift, while the mgf. of the drift w. r. t. g still heavily depends on the
current point of time t (and indirectly on the position expected at this time).
Our drift theorem generalizes virtually all existing drift theorems concerned with a drift
towards the target, including the variable drift theorems for upper [21, 33, 28] and lower
bounds [8] (see Theorem 16 and Theorem 18), a non-monotone variable drift theorem [15]
(see Theorem 22), and multiplicative drift theorems [9, 37, 7] (see Theorem 19 and Theorem 20). Our theorem also generalizes fitness-level theorems [36, 35] (see Theorem 17 and
Theorem 21), another well-known technique in the analysis of randomized search heuristics. These generalizations are shown in Appendix A. Note that we do not consider the
case of negative drift (drift away from the target) as studied in [30, 31] since this scenario
is handled with structurally different techniques.
Remark 2. If for some function h : [xmin , xmax ] → R+ where 1/h(x) is integrable on
[xmin , xmax ], either E(Xt − Xt+1 ; Xt ≥ xmin | Ft ) ≥ h(Xt ) or E(Xt − Xt+1 ; Xt ≥ xmin |
Ft ) ≤ h(Xt ) hold, it is recommended to define the function g in Theorem 3 as
Z x
1
xmin
+
dy
g(x) :=
h(xmin )
xmin h(y)
for x ≥ xmin and g(0) := 0. In proofs, we will instead often use the extension
Z x
1
x
+
dy
g(x) :=
h(xmin )
xmin h(y)
for x ≥ 0.
7

Theorem 3 (General Drift Theorem). Let (Xt )t∈N0 , be a stochastic process, adapted to
a filtration (Ft )t∈N0 , over some state space S ⊆ {0} ∪ [xmin , xmax ], where xmin ≥ 0. Let
g : {0} ∪ [xmin , xmax ] → R≥0 be any function such that g(0) = 0, and 0 < g(x) < ∞ for all
x ∈ [xmin , xmax ]. Let Ta = min{t | Xt ≤ a} for a ∈ {0} ∪ [xmin , xmax ]. Then:
(i) If E(g(Xt )−g(Xt+1 ) ; Xt ≥ xmin | Ft ) ≥ αu for some αu > 0 then E(T0 | X0 ) ≤

g(X0 )
αu .

(ii) If E(g(Xt ) − g(Xt+1 ) ; Xt ≥ xmin | Ft ) ≤ αℓ for some αℓ > 0 then E(T0 | X0 ) ≥

g(X0 )
αℓ .

(iii) If there exists λ > 0 and a function βu : N0 → R+ such that
E(e−λ(g(Xt )−g(Xt+1 )) ; Xt > a | Ft ) ≤ βu (t)
Q

t−1
λ(g(X0 )−g(a)) for t > 0.
then Pr(Ta > t | X0 ) <
r=0 βu (r) · e

(iv) If there exists λ > 0 and a function βℓ : N0 → R+ such that

E(eλ(g(Xt )−g(Xt+1 )) ; Xt > a | Ft ) ≤ βℓ (t)
P

t−1 Qs−1
then Pr(Ta < t | X0 > a) ≤
β
(r)
· e−λ(g(X0 )−g(a)) for t > 0.
ℓ
s=1
r=0

If additionally the set of
states S ∩{x | x ≤ a} is absorbing, then
Q
t−1
−λ(g(X0 )−g(a)) .
Pr(Ta < t | X0 > a) ≤
r=0 βℓ (r) · e

Statement (ii) is also valid (but useless) if the expected hitting time is infinite. Appendix A studies specializations of these first two statements into existing variable and
multiplicative drift theorems which are mostly concerned with expected hitting time.
Special cases of (iii) and (iv). If E(e−λ(g(Xt )−g(Xt+1 )) ; Xt > a | Ft ) ≤ βu for some
time-independent βu , then Statement (iii) simplifies down to Pr(Ta > t | X0 ) < βut ·
eλ(g(X0 )−g(a)) ; similarly for Statement (iv).
On xmin . Some specializations of Theorem 3 require a “gap” in the state space between
optimal and non-optimal states, modelled by xmin > 0. One example is multiplicative drift,
see Theorem 19 in Section A.2. Another example is the process defined by X0 ∼ Unif[0, 1]
and Xt = 0 for t > 0. Its first hitting time of state 0 cannot be derived by drift arguments
since the lower bound on the drift towards the optimum within the interval [0, 1] has limit 0.
The proof of our main theorem is not too complicated. The tail bounds in (iii) and (iv)
are obtained by the exponential method (a generalized Chernoff bound), which idea is also
implicit in [17].
Proof of Theorem 3. Since g(Xt ) = 0 iff Xt = 0 and the image of g is bounded, the first
two items follow from the classical additive drift theorem (Theorem 1). To prove the third
one, we consider the stopped process that does not move after time Ta . We now use ideas
implicit in [17] and argue
Pr(Ta > t | X0 ) ≤ Pr(Xt > a | X0 ) = Pr(g(Xt ) > g(a) | X0 )

= Pr(eλg(Xt ) > eλg(a) | X0 ) < E(eλg(Xt )−λg(a) | X0 ),
8

where the first equality uses that g(x) is monotonically increasing, the second one that
x 7→ ex is a bijection, and the last inequality is Markov’s inequality. Now,
E(eλg(Xt ) | X0 ) = E(eλg(Xt−1 ) · E(e−λ(g(Xt−1 )−g(Xt )) | Ft−1 ) | X0 )
≤ E(eλg(Xt−1 ) | X0 ) · βu (t − 1)

using the prerequisite from the third item. Unfolding the remaining expectation inductively
(note that this does not assume independence of the differences g(Xr−1 ) − g(Xr )), we get
λg(Xt )

E(e

λg(X0 )

| X0 ) ≤ e

t−1
Y

βu (r),

r=0

altogether
t−1
Y

λ(g(X0 )−g(a))

Pr(Ta > t | X0 ) < e

βu (r),

r=0

which proves the third item.
The fourth item is proved similarly as the third one. By a union bound,
Pr(Ta < t | X0 > a) ≤

t−1
X
s=1

Pr(g(Xs ) ≤ g(a) | X0 )

for t > 0. Note that g(Xt ) < g(xmin ) implies g(Xt ) = g(0) = 0. Moreover,
Pr(g(Xs ) ≤ a | X0 ) = Pr(e−λg(Xs ) ≥ e−λa | X0 ) ≤ E(e−λg(Xs )+λa | X0 )
using again Markov’s inequality. By the prerequisites, we get
E(e−λg(Xs ) | X0 ) ≤ e−λg(X0 )

s−1
Y

βℓ (r)

r=0

Altogether,
Pr(Ta < t) ≤

t−1
X

s−1
Y

e−λ(g(X0 )+g(a))

βℓ (r).

r=0

s=1

If furthermore S ∩ {x | x ≤ a} is absorbing then the event Xt ≤ a is necessary for
Ta < t. In this case,
−λ(g(X0 )+g(a))

Pr(Ta < t | X0 ) ≤ Pr(g(Xt ) ≤ g(a) | X0 ) ≤ e

t−1
Y

βℓ (r).

r=0

Given some assumptions on the “drift” function h that typically hold, Theorem 3 can
be simplified. The following corollary will be used to prove the multiplicative drift theorem
(Theorem 19).
9

Corollary 4. Let (Xt )t∈N0 , be a stochastic process, adapted to a filtration (Ft )t∈N0 , over
some state space S ⊆ {0}∪[xmin , xmax ], where xmin ≥ 0. Let h : [xmin , xmax ] → R+ be a function such that 1/h(x) is integrable on [xmin , xmax ] and h(x) differentiable on [xmin , xmax ].
Then the following statements hold for the first hitting time T := min{t | Xt = 0}.
(i) If E(Xt − Xt+1 ; Xt ≥ xmin | Ft ) ≥ h(Xt ) and
R X0 1
xmin h(y) dy.

(ii) If E(Xt − Xt+1 ; Xt ≥ xmin | Ft ) ≤ h(Xt ) and
R X0 1
xmin h(y) dy.

d
dx h(x)

≥ 0, then E(T | X0 ) ≤

xmin
h(xmin )

+

d
dx h(x)

≤ 0, then E(T | X0 ) ≥

xmin
h(xmin )

+

d
(iii) If E(Xt − Xt+1 ; Xt ≥
t ) and dx h(x)
 ≥ λ for some λ > 0, then
 xmin
 | Ft ) ≥ h(X
R
X0
xmin
1
Pr(T > t | X0 ) < exp −λ t − h(xmin ) − xmin h(y) dy .

d
(iv) If E(Xt − Xt+1 ; Xt ≥ xmin | Ft) ≤ h(Xt ) and dx
h(x) ≤
 −λ for some λ > 0, then
R
X0
λxmin
λ
eλt −eλ
Pr(T < t | X0 > 0) < eλ −1 exp − h(xmin ) − xmin h(y) dy .

Rx
Proof. As in Remark 2, let g(x) := x/h(xmin ) + xmin 1/h(y) dy for x ≥ 0. Note that for the
d
second derivative we have g′′ (x) = −( dx
h(x))/h(x)2 .
For (i), it suffices to show that condition (i) of Theorem 3 is satisfied for αu := 1. From
the assumption h′ (x) ≥ 0, it follows that g′′ (x) ≤ 0, hence g is a concave function. Jensen’s
inequality therefore implies that
E(g(Xt ) − g(Xt+1 ) ; Xt ≥ xmin | Ft ) ≥ g(Xt ) − g(E(Xt+1 ; Xt ≥ xmin | Ft ))
Z Xt
1
1
dy ≥
· h(Xt ) = 1,
≥
h(Xt )
Xt −h(Xt ) h(y)
where the last inequality holds because h is a non-decreasing function.
For (ii), it suffices to show that condition (i) Theorem 3 is satisfied for αℓ := 1. From
the assumption h′ (x) ≤ 0, it follows that g ′′ (x) ≥ 0, hence g is a convex function. Jensen’s
inequality therefore implies that
E(g(Xt ) − g(Xt+1 ) ; Xt ≥ xmin | Ft ) ≤ g(Xt ) − g(E(Xt+1 ; Xt ≥ xmin | Ft ))
Z Xt
1
1
dy ≤
· h(Xt ) = 1,
≤
h(Xt )
Xt −h(Xt ) h(y)
where the last inequality holds because h is a non-increasing function.
For (iii), it suffices to show that condition (iii) of Theorem 3 is satisfied for βu := e−λ .
λg(x)
Let f1 (x) := eλg(x) and note that f1′′ (x) = λeh(x)2 · (λ − h′ (x)). Since h′ (x) ≥ λ, it follows
that f1′′ (x) ≤ 0 and f1 is a concave function. By Jensen’s inequality, it holds that
E(e−λ(g(Xt )−g(Xt+1 )) ; Xt ≥ xmin | Ft ) ≤ e−λr
10

where
r := g(Xt ) − g(E(Xt+1 ; Xt ≥ xmin | Ft )) ≥

Z

Xt
Xt −h(Xt )

1
1
dy >
· h(Xt ) = 1,
h(y)
h(Xt )

where the last inequality holds because h is monotone increasing.
For (iv), it suffices to show that condition (iv) of Theorem 3 is satisfied for βℓ := eλ .
−λg(x)
Let f2 (x) := e−λg(x) and note that f2′′ (x) = λeh(x)2 · (λ + h′ (x)). Since h′ (x) ≤ λ, it follows
that f2′′ (x) ≤ 0 and f1 is a concave function. By Jensen’s inequality, it holds that
E(eλ(g(Xt )−g(Xt+1 )) ; Xt ≥ xmin | Ft ) ≤ eλr
where
r := g(Xt ) − g(E(Xt+1 ; Xt ≥ xmin | Ft )) ≤

Z

Xt
Xt −h(Xt )

1
1
dy <
· h(Xt ) = 1,
h(y)
h(Xt )

where the last inequality holds because h is monotone decreasing.
Condition (iii) and (iv) of Theorem 3 involve an mgf., which may be tedious to compute.
Inspired by [17] and [25], we show that bounds on the mgfs. follow from more user-friendly
conditions based on stochastic dominance between random variables, here denoted by ≺.
Theorem 5. Let (Xt )t∈N0 , be a stochastic process, adapted to a filtration (Ft )t∈N0 , over
some state space S ⊆ {0} ∪ [xmin , xmax ], where xmin ≥ 0. Let h : [xmin , xmax ] → R+ be
a function such that 1/h(x) is integrable on [xmin , xmax ]. Suppose there exist a random
R Xt
1/h(max{x, xmin }) dx| ≺ Z for Xt ≥ xmin and
variable Z and some λ > 0 such that | Xt+1
λZ
E(e ) = D for some D > 0. Then the following two statements hold for the first hitting
time T := min{t | Xt = 0}.
(i) If E(Xt −Xt+1 ; Xt ≥ xmin | Ft ) ≥ h(Xt ) then for any δ > 0, and η := min{λ, δλ2 /(D−
1 − λ)} and t > 0 it holds that


Pr(T > t | X0 ) ≤ exp η(xmin /h(xmin ) +

Z

X0
xmin


1/h(x) dx − (1 − δ)t) .

(ii) If E(Xt − Xt+1 ; Xt ≥ xmin | Ft ) ≤ h(Xt ) then for any δ > 0, η := min{λ, δλ2 /(D −
1 − λ)} and t > 0 it holds
 
Z
Pr(T < t | X0 ) ≤ exp η (1 + δ)t − xmin /h(xmin ) −

X0

1/h(x) dx
xmin



1
.
η(1 + δ)

If state 0 is absorbing then


Pr(T < t | X0 ) ≤ exp η((1 + δ)t − xmin /h(xmin ) −
11

Z

X0

xmin


1/h(x) dx) .

Remark 6. Theorem 5 assumes a stochastic dominance of the kind
Z
|

Xt
Xt+1

1/h(max{x, xmin }) dx| ≺ Z.

This is implied by |Xt+1 − Xt |/h(xmin ) ≺ Z.
Rx
1
Proof. As in Remark 2, we define g : {0} ∪ [0, xmax ] → R≥0 by g(x) := h(xxmin ) + xmin h(y)
dy
R Xt
1
for x ≥ 0. Let ∆t := g(Xt ) − g(Xt+1 ) and note that ∆t = Xt+1 h(max{x,xmin}) dx. To satisfy
the third condition of Theorem 3, we note
−η∆t

E(e

) = 1 − ηE(∆t ) +

∞
X
η k E(∆k )
t

k=2

≤ 1 − ηE(∆t ) + η 2

k!

≤ 1 − ηE(∆t ) + η

∞
X
λk−2 E(|∆t |k )
k=2

k!

=1−η+

2

∞
X
η k−2 E(|∆t |k )

k=2
2
η λZ
(e
λ2

k!

− λE(Z) − 1),

where we have used E(∆t ) ≥ 1 (proved in Theorem 3) and λ ≥ η . Since |∆t | ≺ Z, also
E(Z) ≥ 1. Using eλZ = D and η ≤ δλ2 /(D − 1 − λ), we obtain
E(e−η∆t ) ≤ 1 − η + δη = 1 − (1 − δ)η ≤ e−η(1−δ) .
Setting βu := e−η(1−δ) and using η as the λ of Theorem 3 proves the first statement.
For the second statement, analogous calculations prove
E(eη∆t ) ≤ 1 + (1 + δ)η ≤ eη(1+δ) .
We set βℓ := eη(1+δ) , use η as the λ of Theorem 3.(iv) and note that
eλ(1+δ)t
eλ(1+δ)t − eλ(1+δ)
,
≤
λ(1 + δ)
eλ(1+δ) − 1
which was to be proven. If additionally an absorbing state 0 is assumed, the stronger upper
bound follows from the corresponding statement in Theorem 3.(iv).

4

Applications of the Tail Bounds

So far we have mostly derived bounds on the expected first hitting time using Statements (i)
and (ii) of our general drift theorem. As our main contribution, we show that the general
drift theorem (Theorem 3), together with the function g defined explicitly in Remark 2
in terms of the one-step drift, constitute a very general and precise tool for analysis of
stochastic processes. In particular, it provides very sharp tail bounds on the running time
of randomized search heuristics which were not obtained before by drift analysis. It also
provides tail bounds on random recursions, such as those in analysis of random permutations
(see Section 4.2).
12

As already noted, virtually all existing drift theorems, including an existing result proving tail bounds with multiplicative drift, can be phrased as special cases of the general drift
theorem (see Appendix A). Recently, in [23] different tail bounds were proven for the scenario of additive drift using classical concentration inequalities such as Azuma-Hoeffding
bounds. These bounds are not directly comparable to the ones from our general drift
theorem; they are more specific but yield even stronger exponential bounds.
We first give sharp tail bounds on the optimization time of the (1+1) EA which maximizes pseudo-Boolean functions f : {0, 1}n → R. The optimization time is defined in the
canonical way at the smallest t such that xt is an optimum. We consider classical benchmark problems from the theory of RSHs. Despite their simplicity, their analysis has turned
out surprisingly difficult and research is still ongoing.
Algorithm 1 (1+1) Evolutionary Algorithm (EA)
Choose uniformly at random an initial bit string x0 ∈ {0, 1}n .
for t := 0 to ∞ do
Create x′ by flipping each bit in xt independently with probability 1/n (mutation).
xt+1 := x′ if f (x′ ) ≥ f (xt ), and xt+1 := xt otherwise (selection).
end for

4.1

OneMax, Linear Functions and LeadingOnes

A simple pseudo-Boolean function is given by OneMax(x1 , . . . , xn ) = x1 + · · · + xn . It is
included in the class of so-called linear functions f (x1 , . . . , xn ) = w1 xn + · · · + wn xn , where
wi ∈ R for 1 ≤ i ≤ n. We start by deriving very precise bounds on first the expected
optimization time of the (1+1) EA on OneMax and then prove tail bounds. The lower
bounds obtained will imply results for all linear functions. Note that in [8], already the
following result has been proved using variable drift analysis.
Theorems 3 and 5 in [8] The expected optimization time of the (1+1) EA on OneMax
is at most en ln n − c1 n + O(1) and at least en ln n − c2 n for certain constants c1 , c2 > 0.
The constant c2 is not made explicit in [8], whereas the constant c1 is stated as 0.369.
However, unfortunately this value is due to a typo in the very last line of the proof –
c1 should have been 0.1369 instead. We correct this mistake in a self-contained proof.
Furthermore, we improve the lower bound using variable drift. To this end, we use the
following bound on the drift.
Lemma 7. Let Xt denote the number of zeros of the current search point of the (1+1) EA
on OneMax. Then


n−x


1 n−x x
1
x
x
1−
≤ E(Xt − Xt+1 | Xt = x) ≤
1−
.
1+
2
n
n
n
(n − 1)
n
Proof. The lower bound considers the expected number of flipping zero-bits, assuming that
no one-bit flips. The upper bound is obtained in the proof of Lemma 6 in [8] and denoted
by S1 · S2 , but is not made explicit in the statement of the lemma.
13

Theorem 8. The expected optimization time of the (1+1) EA on OneMax is at most
en ln n − 0.1369n + O(1) and at least en ln n − 7.81791n − O(log n).
≤ X0 ≤ (1+ǫ)n
for an arbitrary
Proof. Note that with probability 1 − 2−Ω(n) we have (1−ǫ)n
2
2
constant ǫ > 0. Hereinafter, we assume this event to happen, which only adds an error
term of absolute value 2−Ω(n) · n log n = 2−Ω(n) to the expected optimization time.
In order to apply the variable drift theorem (more precisely, Theorem 16 for the upper
and Theorem 18 for the lower bound), we manipulate and estimate the expressions from
Lemma 7 to make them easy to integrate. To prove the upper bound on the optimization
time, we observe


1 n−x x
E(Xt − Xt+1 | Xt = x) ≥ 1 −
n
n


n−1 


1
1 −x x
1
= 1−
· 1−
· · 1−
n
n
n
n


x x
1
=: hℓ (x).
≥ e−1+ n · · 1 −
n
n
Now, by the variable drift theorem, the optimization time T satisfies
!

Z (1+ǫ)n/2
Z (1+ǫ)n/2
x
1
1 −1
1
n
1− n
e
1−
+
dx ≤ en +
E(T | X0 ) ≤
·
hℓ (1)
hℓ (x)
x
n
1
1





1
(1+ǫ)n/2
≤ en − en [E1 (x/n)]1
1+O
,
n
R∞

e−t
t

dt denotes the exponential integral (for x > 0). The latter is
P
(−x)k
estimated using the series representation E1 (x) = − ln x−γ− ∞
k=1 kk! , with γ = 0.577 . . .
being the Euler-Mascheroni constant (see Equation 5.1.11 in [1]). We get for sufficiently
small ǫ that
where E1 (x) :=

x

(1+ǫ)n/2

− [E1 (x/n)]1

= E1 (1/n) − E1 ((1 + ǫ)/2) ≤ − ln(1/n) − γ + O(1/n) − 0.559774.

Altogether,
E(T | X0 ) ≤ en ln n + en(1 − 0.559774 − γ) + O(log n) ≤ en ln n − 0.1369n + O(log n)
which proves the upper bound.
For the lower bound on the optimization time, we need according to Theorem 18 a
monotone process (which is satisfied) and a function c bounding the progress towards the
optimum. We use c(x) = x − log x − 1. Since each bit flips with probability 1/n, we get
Pr(Xt+1 ≤ Xt − log(Xt ) − 1) ≤



Xt
log(Xt ) + 1


log(Xt )+1
  log(Xt )+1
eXt
1
≤
.
n
n log(Xt ) + n

14

The last bound takes its maximum at Xt = 2 within the interval [2, . . . , n] and is O(n−2 )
then. For Xt = 1, we trivially have Xt+1 ≥ c(Xt ) = 0. Hence, by assuming Xt+1 ≥ c(Xt )
for all t = O(n log n), we only introduce an additive error of value O(log n).
Next the upper bound on the drift from Lemma 7 is manipulated. We get for some
sufficiently large constant c∗ > 0 that
n−x


x
x
1
·
1+
E(Xt − Xt+1 | Xt = x) ≤
1−
2
n
(n − 1)
n

n−x
2
x
1
+
x/(n
−
1)
x
+ x(n−x)
−1+ n
n2
≤e
· ·
n
1 + x/(n2 )


2x
c∗
x
≤ e−1+ n · · 1 +
=: h∗ (x),
n
n
where we used 1 + x ≤ ex twice. The drift theorem requires a function hu (x) such that
h∗ (x) ≤ hu (c(x)) = hu (x − log x − 1). Introducing the substitution y := y(x) := x − log x − 1
and its inverse function x(y), we choose hu (y) := h∗ (x(y)).
We obtain
!
 
Z (1−ǫ)n/2
1
1
1
+
dy
1−O
E(T | X0 ) ≥
∗
∗
h (x(1))
h (x(y))
n
1

 !
 
Z x((1−ǫ)n/2)
1
1
1
1
+
1−
dx
1−O
≥
∗
∗
h (4)
h (x)
x
n
x(1)
!





Z (1−ǫ)n/2
2x
en
1
1
n
≥
e1− n ·
+
1−
dx
1−O
4
x
x
n
2
!
 
Z (1−ǫ)n/2
Z (1−ǫ)n/2
2x
en
1
n
n
1− 2x
1−
e n · dx −
e n · 2 dx
=
+
1−O
4
x
x
n
2
2
where the second inequality uses integration by substitution and x(1) = 4, the third one
x(y) ≤ y, and the last one partial integration.
With respect to the first integral in the last bound, the only difference compared to
2x
the upper bound is the 2 in the exponent of e−1+ n , such that we can proceed analogously
to the above and obtain −enE1 (2x/n) + C as anti-derivative. The anti-derivative of the
second integral is 2eE1 (2x/n) − e1−2x/n nx + C.
We obtain

 
i(1−ǫ)n/2  
en h
1
1−2x/n n
E(T | X0 ) ≥
+ −(2e + en)E1 (2x/n) + e
1−O
4
x 2
n
Now, for sufficiently small ǫ,
(1−ǫ)n/2

− [E1 (2x/n)]2

≥ − ln(8/n) − γ − O(1/n) − 0.21939 ≥ ln n − 2.76048 − O(1/n)

and
h

e1−2x/n

en
n i(1−ǫ)n/2
≥ 1.9999 −
− O(1/n).
x 2
4
15

Altogether,
E(T | X0 ) ≥ en ln n − 7.81791n − O(log n)
as suggested.
Knowing the expected optimization time precisely, we now turn to our main new contribution, i. e., to derive sharp bounds. Note that the following upper concentration inequality
in Theorem 9 is not new but is already implicit in the work on multiplicative drift analysis
by [12]. In fact, a very similar upper bound is even available for all linear functions [37].
By contrast, the lower concentration inequality is a novel and non-trivial result.
Theorem 9. The optimization time of the (1+1) EA on OneMax is at least en ln n −
cn − ren, where c is a constant, with probability at least 1 − e−r/2 for any r ≥ 0. It is at
most en ln n + ren with probability at least 1 − e−r .
Proof of Theorem 4, upper tail. This tail can be easily derived from the multiplicative drift
theorem (Theorem 19). Let Xt denote the number of zeros at time t. By Lemma 7, we can
choose δ := 1/(en). Then the upper bound follows since X0 ≤ n and xmin = 1.
We only consider the lower tail. The aim is to prove it using Theorem 3.(iv), which
includes a bound on the moment-generating function of the drift of g. We first set up the
h (and thereby the g) used for our purposes. Obviously, xmin := 1.
Lemma 10. Consider the (1+1) EA on OneMax and let the random variable Xt denote
the current number of zeros at time t ≥ 0. Then h(x) := exp (−1 + 2⌈x⌉/n) · (⌈x⌉/n) ·
(1 + c∗ /n) , where c∗ > 0 is a sufficiently large constant, satisfies the condition E(Xt −Xt+1 |
Ri
Xt = i) ≤ h(i) for i ∈ {1, . . . , n}. Moreover, define g(i) := xmin /h(xmin ) + xmin 1/h(y) dy
P
P t
1−2Xt+1 /n ·
and ∆t := g(Xt ) − g(Xt+1 ). Then g(i) = ij=1 1/h(j) and ∆t ≤ X
j=Xt+1 +1 e
(n/j).
x
n−x x is an upper bound on
Proof. According to Lemma 7, h∗ (x) := ((1 − n1 )(1 + (n−1)
2)
n
the drift. We obtain h(x) ≥ h∗ (x) using the simple estimations exposed in the proof of
Theorem 8, lower bound part.
The representation of g(i) as a sum follows immediately from h due to the ceilings. The
2⌈x⌉
∗
bound on ∆t follows from h by estimating e−1+ n · 1 + cn ≥ e−1+2x/n .

The next lemma provides a bound on the mgf. of the drift of g, which will depend on
the current state. Later, the state will be estimated based on the current point of time,
leading to a time-dependent bound on the mgf. Note that we do not need the whole natural
filtration based on X0 , . . . , Xt but only Xt since we are dealing with a Markov chain.

Lemma 11. Let λ := 1/(en) and i ∈ {1, . . . , n}. Then E(eλ∆t | Xt = i) ≤ 1 + λ + 2λ/i +
o(λ/log n).
Proof. We distinguish between three major cases.

16

Case 1: i = 1. Then Xt+1 = 0, implying ∆t ≤ en, with probability (1/n)(1−1/n)n−1 =
(1/(en))(1 + 1/(n − 1)) and Xt+1 = i otherwise. We get


 
1
1
1
λ∆t
1
E(e
| Xt = i) ≤
·e + 1−
+O 2
en
en
n
 


e−1
1
λ
(e − 2)λ
≤ 1+
+O 2 ≤ 1+λ+
+o
.
en
n
i
ln n

Case 2: 2 ≤ i ≤ ln3 n. Let Y := i − Xt+1 and note that Pr(Y ≥ 2) ≤ (ln6 n)/n2 since
the probability of flipping a zero-bit is at most (ln3 n)/n. We further subdivide the case
according to whether Y ≥ 2 or not.
Case 2a: 2 ≤ i ≤ ln3 n and Y ≥ 2. The largest value of ∆t is taken when Y = i.
Using Lemma 10 and estimating the i-th Harmonic number, we have λ∆t ≤ (ln i) + 1 ≤
3(ln ln n) + 1. The contribution to the mgf. is bounded by


 6 
λ
ln n
λ∆t
3 ln ln n+1
=o
E(e
.
· 1 {Xt+1 ≤ i − 2} | Xt = i) ≤ e
·
n2
ln n

Case 2b: 2 ≤ i ≤ ln3 n and Y < 2. Then Xt+1 ≥ Xt − 1, which implies ∆t ≤
en(ln(Xt ) − ln(Xt+1 )). We obtain
i−Xt+1

E(eλ∆t · 1 {Xt+1 ≥ i − 1} | Xt = i) ≤ E(eln(i/Xt+1 ) ) ≤ E(eln(1+ i−1 ) )


Y
= E 1+
,
i−1
P
where the first inequality estimated ki=j+1 1i ≤ ln(k/j) and the second one used Xt+1 ≥
i
(1 + O((ln3 n)/n)) for i ≤ ln3 n. This implies
i − 1. From Lemma 7, we get E(Y ) ≤ en



 3 
ln n
i − Xt+1
i
E 1+
≤1+
1+O
i−1
en(i − 1)
n



 3 

1
λ
ln n
1
2λ
=1+
· 1+
+o
1+O
=1+λ+
,
en
i−1
n
i
ln n

using i/(i − 1) ≤ 2 in the last step. Adding the bounds from the two sub-cases proves the
lemma in Case 2.
 ln n
≤ 1/(ln n)!. We further
Case 3: i > ln3 n. Note that Pr(Y ≥ ln n) ≤ lnnn n1
subdivide the case according to whether Y ≥ ln n or not.
Case 3a: i > ln3 n and Y ≥ ln n. Since ∆t ≤ en(ln n + 1), we get



λ
1
ln n+1
3
λ∆t
·e
=o
· 1 Xt+1 ≤ i − ln n | Xt = i) ≤
E(e
(ln n)!
ln n
Case 3b: i > ln3 n and Y < ln n. Then, using Lemma 10 and proceeding similarly as
in Case 2b,
E(eλ∆t · 1 {Xt+1 > i − ln n} | Xt = i)
≤ E(eλ exp(1−2(i−ln n)/n)·n ln(i/Xt+1 ) | Xt = i) = E
17



i − Xt+1
1+
Xt+1

exp((−2i+ln n)/n) !

.

Using i > ln3 n and Jensen’s inequality, the last expectation is at most

exp((−2i+ln n)/n) 
exp((−2i+ln n)/n)
i − Xt+1
Y
1+E
≤ 1+E
Xt+1
i − ln n


exp((−2i+ln n)/n)
Y
≤ 1+E
,
i(1 − 1/ln2 n)





where the last inequality used again i > ln3 n. Since E(Y ) ≤ e−1+2i/n ni (1 + c∗ /n), we
conclude
!exp((−2i+ln n)/n)
2i/n
e
E(eλ∆t · 1 {Xt+1 > i − ln n} | Xt = i) ≤ 1 +
en(1 − 1/ln2 n)






λ
ln n
1
≤1+λ+o
,
1+O
≤ 1+
n2
ln n
en(1 − 1/ln2 n)
where we used (1 + ax)1/a ≤ 1 + x for x ≥ 0 and a ≥ 1. Adding up the bounds from the
two sub-cases, we have proved the lemma in Case 3.
Altogether,


2λ
λ
λ∆t
E(e
| Xt = i) ≤ 1 + λ +
+o
.
i
ln n
for all i ∈ {1, . . . , n}.
The bound on the mgf. of ∆t derived in Lemma 11 is particularly large for i = O(1), i. e.,
if the current state Xt is small. If Xt = O(1) held during the whole optimization process,
we could not prove the lower tail in Theorem 9 from the lemma. However, it is easy to see
that Xt = i only holds for an expected number of at most en/i steps. Hence, most of the
time the term 2λ/i is negligible, and the time-dependent βℓ (t)-term from Theorem 3.(iv)
comes into play. We make this precise in the following proof, where we iteratively bound
the probability of the process being at “small” states.
Proof of Theorem 9, lower tail. With overwhelming probability 1−2−Ω(n) , X0 ≥ (1−ǫ)n/2
for an arbitrarily small constant ǫ > 0, which we assume to happen. We consider phases in
the optimization process. Phase 1 starts with initialization and ends before the first step
√
ln n−1
where Xt < e 2 = n · e−1/2 . Phase i, where i > 1, follows Phase i − 1 and ends before
√
the first step where Xt < n · e−i/2 . Obviously, the optimum is not found before the end
of Phase ln(n); however, this does not tell us anything about the optimization time yet.
We say that Phase i is typical if it does not end before time eni−1. We will prove induci √
tively that the probability of one of the first i phases not being typical is at most c′ e 2 / n =
i−ln n
c′ e 2 for some constant c′ > 0. This implies the theorem since an optimization time of
at least en ln n − cn − ren is implied by the event that Phase ln n − ⌈r − c/e⌉ is typical,
−r+c/e+1

−r

2
= 1 − e 2 for c = e(2 ln c′ + 1).
which has probability at least 1 − c′ e
Fix some k > 1 and assume for the moment that all the first k − 1 phases are typical.
√
Then for 1 ≤ i ≤ k − 1, we have Xt ≥ ne−i/2 in Phase i, i. e., when en(i − 1) ≤ t ≤ eni − 1.

18

We analyze the event that additionally Phase k is typical, which subsumes the event Xt ≥
√ −k/2
ne
throughout Phase k. According to Lemma 11, we get in Phase i, where 1 ≤ i ≤ k,


i/2
√
√
+o( lnλn )
λ+ 2λe
λ∆t
n
| Xt ≤ 1 + λ + 2λei/2 / n + o(λ/ ln n) ≤ e
E e

The expression now depends on the time only, therefore for λ := 1/(en)
enk−1
Y
t=0



Pk
k/2
i/2 +enk·o
√
λenk+ 2λen
( lnλn ) ≤ ek+ 6en√n +o(1) ≤ ek+o(1) ,
i=1 e
n
E eλ∆t | X0 ≤ e

√
where we used that k ≤ ln n. From Theorem 3.(iv) for a = ne−k/2 and t = enk − 1 we
obtain
√ −k/2
))
.
Pr(Ta < t) ≤ ek+o(1)−λ(g(X0 )−g( ne

From the proof of of Theorem 8, the lower bound part, we already know that g(X0 ) ≥
en ln n − c′′ n for some constant c′′ > 0 (which is assumed large enough to subsume the
−O(log n) term). Moreover, g(x) ≤ en(ln x + 1) according to Lemma 10. We get
k−ln n+O(1)
√
2
Pr(Ta < t) ≤ ek+o(1)−ln n+O(1)−k/2+(ln n)/2 = e
= c′′′ ek/2 / n,

for some sufficiently large constant c′′′ > 0, which proves the bound on the probability of Phase k not being typical (without making statements about the earlier phases).
The
that all phases up to and including Phase k are typical is at least 1 −
Pk probability
√
√
′′′
i/2
( i=1 c e )/ n ≥ 1 − c′ ek/2 / n for a constant c′ > 0.

We now deduce a concentration inequality w. r. t. linear functions, essentially depending
on all variables, i. e., functions of the kind f (x1 , . . . , xn ) = w1 x1 + · · · + wn xn , where wi 6= 0.
This function class contains OneMax and has been studied intensely the last 15 years [37].
Theorem 12. The optimization time of the (1+1) EA on an arbitrary linear function with
non-zero weights is at least en ln n − cn − ren, where c is a constant, with probability at
least 1 − e−r/2 for any r ≥ 0. It is at most en ln n + (1 + r)en + O(1) with probability at
least 1 − e−r .

Proof. The upper tail is proved in Theorem 5.1 in [37]. The lower bound follows from the
lower tail in Theorem 9 in conjunction with the fact that the optimization time within the
class of linear functions is stochastically smallest for OneMax (Theorem 6.2 in [37]).
P Q
Finally, we consider LeadingOnes(x1 , . . . , xn ) := ni=1 ij=1 xj , another intensively
studied standard benchmark problem from the analysis of RSHs. Tail bounds on the optimization time of the (1+1) EA on LeadingOnes were derived in [11]. This result represents
a fundamentally new contribution, but suffers from the fact that it depends on a very specific structure and closed formula for the optimization time. Using a simplified version of
Theorem 3 (see Theorem 5), it is possible to prove similarly strong tail bounds without
needing this exact formula. As in [11], we are interested in a more general statement. Let
T (a) be the number of steps until a LeadingOnes-value of at least a is reached, where
0 ≤ a ≤ n. Let Xt := max{0, a − LeadingOnes(xt )} be the distance from the target a at
time t. Lemma 13 states the drift of (Xt )t∈N0 exactly, see also [11].
19

Lemma 13. For all i > 0, E(Xt − Xt+1 | Xt = i) = (2 − 2−n+a−i+1 )(1 − 1/n)a−i (1/n).
Proof. The leftmost zero-bit is at position a − i + 1. To increase the LeadingOnes-value
(it cannot decrease), it is necessary to flip this bit and not to flip the first a − i bits, which is
reflected by the last two terms in the lemma. The first term is due to the expected number
of free-rider bits (a sequence of previously random bits after the leftmost zero that happen
to be all 1 at the time of improvement). Note that there can be between 0 and n − a + i − 1
such bits. By the usual argumentation using a geometric distribution, the expected number
of free-riders in an improving step equals
n−a+i−1
X
k=0

 min{n−a+i−1,k+1}
1
= 1 − 2−n+a−i+1 ,
k·
2

hence the expected progress in an improving step is 2 − 2−n+a−i+1 .
We can now supply the tail bounds, formulated as Statements (ii) and (iii) in the
following theorem. The first statement is an exact expression for the expected optimization
time, which has already been proved without drift analysis [11].
Theorem 14. Let T (a) the time for the (1+1) EA to reach a LeadingOnes-value of at
least a. Moreover, let r ≥ 0. Then

a

2
1
−1 .
(i) E(T (a)) = n 2−n 1 + n−1
−3/2

)
(ii) For 0 < a ≤ n − log n, with probability at least 1 − e−Ω(rn


a
1
n2
− 1 + r.
1+
T (a) ≤
2
n−1

−3/2

) − e−Ω(log
(iii) For log2 n − 1 ≤ a ≤ n, with probability at least 1 − e−Ω(rn

a

n2 − n
2 log2 n
1
T (a) ≥
−1−
1+
− r.
2
n−1
n

2

n)

Proof. The first statement is already contained in [11] and proved without drift analysis.
We now turn to the second statement. From Lemma 13, h(x) = (2−2/n)(1−1/n)a−x /n
is a lower bound on the drift E(Xt − Xt+1 | Xt = x) if x ≥ log n. To bound the change of
the g-function, we observe that h(x) ≥ 1/(en) for all x ≥ 1. This means that Xt − Xt+1 = k
implies g(Xt ) − g(Xt+1 ) ≤ enk. Moreover, to change the LeadingOnes-value by k, it is
necessary that
• the first zero-bit flips (which has probability 1/n)
• k − 1 free-riders occur.

20

The change does only get stochastically larger if we assume an infinite supply of free-riders.
Hence, g(Xt ) − g(Xt+1 ) is stochastically dominated by a random variable Z = enY , where
Y
• is 0 with probability 1 − 1/n and
• follows the geometric distribution with parameter 1/2 otherwise (where the support
is 1, 2, . . . ).
The mgf. of Y therefore equals


1
1/2
1
1
λY
E(e ) = 1 −
≤1+
,
e0 +
−λ
n
n e − (1 − 1/2)
n(1 − 2λ)
where we have used e−λ ≥ 1 − λ. For the mgf. of Z it follows
E(eλZ ) = E(eλenY ) ≤ 1 +

1
,
n(1 − 2enλ)

hence for λ := 1/(4en) we get D := E(eλZ ) = 1 + 2/n = 1 + 8eλ, which means D − 1 − λ =
(8e − 1)λ. We get
δλ2
δλ
δ
η :=
=
=
D−1−λ
8e − 1
4en(8e − 1)

(which is less than λ if δ ≤ 8e − 1) . Choosing δ := n−1/2 , we obtain η = Cn−3/2 for
C := 1/((8e − 1)(4e)).
R X0
1/h(x) dx + r)/(1 − δ) in the first statement of TheoWe set t := (xmin /h(xmin ) + xmin
rem 5. The integral within t can be bounded according to
Z X0
a
X
1
1
xmin
+
dx ≤
U :=
h(xmin )
(2 − 2/n)(1 − 1/n)a−i /n
xmin h(x)
i=1




a
1
1
n2
(1 + 1/(n − 1))a − 1
1
=
−1
+
=
·n·
1+
2 2n − 2
1/(n − 1)
2
n−1
Hence, using the theorem we get
Pr(T > t) = Pr(T > (U + r)/(1 − δ)) ≤ e−ηr ≤ e−Crn

−3/2

Since U ≤ en2 and 1/(1 − δ) ≤ 1 + 2δ = 1 + 2n−1/2 , we get
Pr(T ≥ U + 2en3/2 + 2r) ≤ e−Crn

−3/2

.

Using the upper bound on U derived above, we obtain



a

1
n2
−3/2 )
− 1 + r ≤ e−Ω(rn
1+
Pr T ≥
2
n−1
as suggested.
21

.

Finally, we prove the third statement of this theorem in a quite symmetrical way to the
second one. We can choose h(x) := 2(1 − 1/n)a−x /n as an upper bound on the drift E(Xt −
R X0
1/h(x) dx −
Xt+1 | Xt = x). The estimation of the E(eλZ ) still applies. We set t := ( xmin
2
r)/(1 − δ). Moreover, we assume X0 ≥ n − log n − 1, which happens with probability at
2
least 1 − e−Ω(log n) . Note that
2

a−log
Xn
1
1
L :=
dx ≥
2(1 − 1/n)a−i /n
xmin h(x)
i=1

a 
log2 n !
1
1
n2 − n
1+
− 1+
=
2
n−1
n−1



a
log2 n
1
n2 − n
−1−
1+
,
≥
2
n−1
n

Z

X0

where the last inequality used ex ≤ 1 + 2x for x ≤ 1 and ex ≥ 1 + x for x ∈ R. The second
statement of Theorem 5 yields (since state 0 is absorbing)
Pr(T < t) = Pr(T < (L − r)/(1 + δ)) ≤ e−ηr ≤ e−Crn
Now, since

−3/2

.

L−r
≥ (L − r) − δ(L − r) ≥ L − r − en3/2 ,
1+δ

(using L ≤ en2 ), we get the third statement by analogous calculations as above.

4.2

An Application to Probabilistic Recurrence Relations

Drift analysis is not only useful in the theory of RSHs, but also in classical computer
science. Here, we study the probabilistic recurrence relation T (n) = a(n) + T (h(n)), where
n is the problem size, a(n) the amount of work at the current level of recursion, and h(n)
is a random variable, denoting the size of the problem at the next recursion level. The
asymptotic distribution (letting n → ∞) of the number of cycles is well studied [2], but
there are few results for finite n. Karp [22] studied this scenario using different probabilistic
techniques than ours. Assuming knowledge of E(h(n)), he proved upper tail bounds for
T (n), more precisely he analyzed the probability of T (n) exceeding the solution of the
“deterministic” process T (n) = a(n) + T (E(h(n))).
We pick up the example from [22, Section 2.4] on the number of cycles in a permutation π ∈ Sn drawn uniformly at random, where Sn denotes the set of all permutations of the n elements {1, . . . , n}. A cycle is a subsequence of indices i1 , . . . , iℓ such that
π(ij ) = i(j mod ℓ)+1 for 1 ≤ j ≤ ℓ. Each permutation partitions the elements into disjoint
cycles. The expected number of cycles in a random permutation is Hn = ln n + Θ(1). Moreover, it is easy to see that the length of the cycle containing any fixed element is uniform on
{1, . . . , n}. This gives rise to the probabilistic recurrence T (n) = 1+ T (h(n)) expressing the
random number of cyles, where h(n) is uniform on {0, . . . , n − 1} . As a result, [22] shows
that the number of cycles is larger than log2 (n+1)+a with probability at most 2−a+1 . Note
22

that the log2 (n), which results from the solution of the deterministic recurrence, is already
by a constant factor away from the expected value. Lower tail bounds are not obtained in
[22]. Using our drift theorem (Theorem 3), it however follows that the number of cycles is
sharply concentrated around its expectation.
Theorem 15. Let N be the number of cycles in a random permutation of n elements. Then
ǫ2

Pr(N < (1 − ǫ)(ln n)) ≤ e− 4 (1−o(1)) ln n
for any constant 0 < ǫ < 1. And for any constant ǫ > 0,
Pr(N ≥ (1 + ǫ)((ln n) + 1)) ≤ e−

min{ǫ,ǫ2 }
6

ln n

.

Proof. We regard the probabilistic recurrence as a stochastic process, where Xt , t ≥ 0,
denotes the number of elements not yet included in a cycle; X0 = n. As argued in [22], if
Xt = i then Xt+1 is uniform on {0, ..., i − 1}. Note that N equals the first hitting time for
Xt = 0, which is denoted by T0 in our notation. Obviously, N is stochastically larger than
Ta for any a > 0.
We now prove the lower tail using Theorem 3.(iv). We compute E(Xt+1 | Xt ) =
(Xt − 1)/2, which means E(Xt − Xt+1 | Xt ) ≥ X2t = |X2t | since only integral Xt can happen.
Therefore we choose h(x) = |x|/2 in the theorem. Letting xmin = 1, we obtain the drift
Ri
P
function g(i) = 2 + 1 2/⌈j⌉ dj = ij=1 2/⌈j⌉ for i ≥ 1 and g(0) = 0. We remark that other
choices of h, with 1/2 replaced by different constants, would lead to the essentially same
result.
For the drift theorem, we have to compute g(i) − g(Xt+1 ), given Xt = i, and to bound
the mgf. w. r. t. this difference. We get
(
2(ln(i) − ln(j)) for j = 1, ..., i − 1, each with prob. 1/i,
g(i) − g(Xt+1 ) ≤
2(ln(i) + 1)
with prob. 1/i
Let Xt = i. For λ > 0, we bound the mgf.
λ(g(i)−g(Xt+1 ))

E(e

i−1

i−1

j=1

j=1

1 X 2λ(ln i−ln j) 1 η η 1 η X −η
1
j ,
e
= e i + i
) ≤ · e2λ e2λ ln i +
i
i
i
i

where η = 2λ. Now assume η constant and η < 1. Then


Z i−1
λ(g(i)−g(Xt+1 ))
η−1 η
η−1
−η
E(e
)≤i e +i
j dj
1+

1


1
η−1 η
η−1
1−η
≤i e +i
(i − 1)
−1
1+
1−η
1
1
− iη−1 = iη−1 eη +
≤ iη−1 (eη + 1) +
1−η
1−η
η iη−1 + η
η
e
1−η =: β
≤e
= 1 + iη−1 eη +
1−η
23

η η−1

will turn out to be negligible (more precisely,
using 1 + x ≤ ex . The factor ee i
η−1
eO((ln n) ) ) for i ≥ ln n in the following, which is why we set a := ln n in Theorem 3.(iv).
From the theorem, P
we get Pr(Ta < t) ≤ β t e−λ(g(X0 )−g(a)) . We work with the lower
bound g(X0 ) − g(a) = nj=a 2/j ≥ 2(ln(n + 1) − ln(a + 1)), which yields
Pr(Ta < t) < β t e−λ(2(ln(n+1)−ln(a+1))) = β t e−η ln n+O(ln ln n)
η−1 )+ η t−η ln n+O(ln ln n)
1−η

= eO(t(ln n)

η

= eo(t)+O(ln ln n)+ 1−η t−η ln n

η
Now we concentrate on the difference d(ǫ) = 1−η
t − η ln n that is crucial for the order
of growth of the last exponent. We assume t := (1 − ǫ) ln n for some constant ǫ > 0 and set
η := ǫ/2 (implying ǫ < 2); hence λ = ǫ/4. We get


1−ǫ
ǫ
ǫ
ǫ2
ǫ/2
(1 − ǫ)(ln n) − (ln n) = (ln n)
− 1 ≤ − (ln n)
d(ǫ) =
1 − ǫ/2
2
2
1 − ǫ/2
4

Using the bound for d(ǫ) in the exponent and noting that ǫ > 0 is constant, give
ǫ2

Pr(Ta < (1 − ǫ) ln n) ≤ e− 4 (1−o(1)) ln n , which also bounds T0 the same way.
To prove the upper tail, we must set a := 0 in Theorem 3.(iii). Using the lower bound
on the difference of g-values derived above, we estimate for Xt = i and any λ > 0
−λ(g(i)−g(Xt+1 ))

E(e

i−1

i−1

j=0

j=0

1 X −λ(2(ln(i+1)−ln(j+1))) 1 X
e
=
)≤
i
i



j+1
i+1

η

,

where again η = 2λ. Hence, similarly to the estimations for the lower tail,
Z i
η
1
1
1 η+1
1
−λ(g(i)−g(Xt+1 ))
j η dj ≤ η+1
i
=
≤ e− η+1 =: β
E(e
) ≤ η+1
i
i
η+1
η+1
1
From the drift theorem, we get
ηt

ηt

Pr(T0 > t) ≤ β t eλ(g(X0 )−g(0)) ≤ e− η+1 eλ(2(ln(n)+1)) = e− η+1 +η(ln n+1) .
Setting t := (1 + ǫ)(ln n + 1) and η = ǫ/2, the exponent is no more than
−

η(1 + ǫ/2 + ǫ/2)(ln n + 1)
ǫ2
+ η(ln n + 1) ≤ −
(ln n + 1).
1 + ǫ/2
4 + 2ǫ
2

The last fraction is at most − ǫ6 if ǫ ≤ 1 and at most − 6ǫ otherwise (if ǫ > 1). Altogether
Pr(T0 > t | X0 = n) ≤ e−

min{ǫ2 ,ǫ}
(ln n+1)
6

.

For appropriate functions g(x), our drift theorem may provide sharp concentration
results for other probabilistic recurrences, such as the case a(n) > 1.
24

5

Conclusions

We have presented a new and versatile drift theorem with tail bounds. It can be understood as a general variable drift theorem and can be specialized into all existing variants
of variable, additive and multiplicative drift theorems we found in the literature as well
as the fitness-level technique. Moreover, it provides lower and upper tail bounds, which
were not available before in the context of variable drift. Tail bounds were used to prove
sharp concentration inequalities on the optimization time of the (1+1) EA on OneMax,
linear functions and LeadingOnes. Despite the highly random fashion this RSH operates,
its optimization time is highly concentrated up to lower order terms. The drift theorem
also leads to tail bounds on the number of cycles in random permutations. The proofs
illustrate how to use the tail bounds and we provide simplified (specialized) versions of
the corresponding statements. We believe that this research helps consolidate the area of
drift analysis. The general formulation of drift analysis increases our understanding of its
power and limitations. The tail bounds imply more practically useful statements on the
optimization time than the expected time. We expect further applications of our theorem,
also to classical randomized algorithms.
Acknowledgements.
This research received funding from the European Union Seventh Framework Programme
(FP7/2007-2013) under grant agreement no 618091 (SAGE) and from the Danish Council
for Independent Research (DFF-FNU) under grant no. 4002–00542.

References
[1] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions with Formulas,
Graphs, and Mathematical Tables. National Bureau of Standards, 1964.
[2] R. Arratia and S. Tavare. The cycle structure of random permutations. The Annals
of Probability, 20(3):1567–1591, 1992.
[3] A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics: Foundations
and Recent Developments. World Scientific Publishing, 2011.
[4] W. Baritompa and M. A. Steel. Bounds on absorption times of directionally biased
random sequences. Random Structures and Algorithms, 9(3):279–293, 1996.
[5] E. G. Coffman, A. Feldmann, N. Kahale, and B. Poonen. Computing call admission capacities in linear networks. Probability in the Engineering and Informational Sciences,
13(04):387–406, 1999.
[6] D. Corus, D. Dang, A. V. Eremeev, and P. K. Lehre. Level-based analysis
of genetic algorithms and other search processes. CoRR, abs/1407.7663, 2014.
http://arxiv.org/abs/1407.7663.

25

[7] B. Doerr, C. Doerr, and T. Kötzing. The right mutation strength for multi-valued
decision variables. In Proc. of the Genetic and Evolutionary Computation Conference
(GECCO 2016), pages 1115–1122. ACM Press, 2016.
[8] B. Doerr, M. Fouz, and C. Witt. Sharp bounds by probability-generating functions
and variable drift. In Proc. of the Genetic and Evolutionary Computation Conference
(GECCO 2011), pages 2083–2090. ACM Press, 2011.
[9] B. Doerr and L. A. Goldberg. Adaptive drift analysis. Algorithmica, 65(1):224–250,
2013.
[10] B. Doerr, A. Hota, and T. Kötzing. Ants easily solve stochastic shortest path problems.
In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2012),
pages 17–24. ACM Press, 2012.
[11] B. Doerr, T. Jansen, C. Witt, and C. Zarges. A method to derive fixed budget results
from expected optimisation times. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2013), pages 1581–1588. ACM Press, 2013.
[12] B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. Algorithmica,
64(4):673–697, 2012.
[13] S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary
algorithm. Theoretical Computer Science, 276:51–81, 2002.
[14] A. Eryilmaz and R. Srikant. Asymptotically tight steady-state queue length bounds
implied by drift conditions. Queueing Systems: Theory and Applications, 72(3-4):311–
359, 2012.
[15] M. Feldmann and T. Kötzing. Optimizing expected path lengths with ant colony
optimization using fitness proportional update. In Proc. of Foundations of Genetic
Algorithms (FOGA 2013), pages 65–74. ACM Press, 2013.
[16] C. Gießen and C. Witt. Optimal mutation rates for the (1+λ) EA on onemax. In
Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2016), pages
1147–1154. ACM Press, 2016.
[17] B. Hajek. Hitting and occupation time bounds implied by drift analysis with applications. Advances in Applied Probability, 14:502–525, 1982.
[18] J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):57–85, 2001. Erratum in Artif. Intell. 140(1/2):
245-248 (2002).
[19] J. Jägersküpper. Combining markov-chain analysis and drift analysis - the (1+1)
evolutionary algorithm on linear functions reloaded. Algorithmica, 59(3):409–424, 2011.
[20] T. Jansen. Analyzing Evolutionary Algorithms - The Computer Science Perspective.
Natural Computing Series. Springer, 2013.
26

[21] D. Johannsen. Random combinatorial structures and randomized search heuristics.
PhD thesis, Universität des Saarlandes, Germany, 2010.
[22] R. M. Karp. Probabilistic recurrence relations. Journal of the ACM, 41(6):1136–1150,
1994.
[23] T. Kötzing. Concentration of first hitting times under additive drift. Algorithmica,
75(3):490–506, 2016.
[24] P. K. Lehre. Negative drift in populations. In Proc. of Parallel Problem Solving from
Nature (PPSN XI), volume 6238 of LNCS, pages 244–253. Springer, 2011.
[25] P. K. Lehre. Drift analysis (tutorial). In Companion to GECCO 2012, pages 1239–1258.
ACM Press, 2012.
[26] P. K. Lehre and C. Witt. Black-box search by unbiased variation. Algorithmica,
64(4):623–642, 2012.
[27] P. K. Lehre and C. Witt. Concentrated hitting times of randomized search heuristics
with variable drift. In Proceedings of the 25th International Symposium Algorithms
and Computation (ISAAC 2014), volume 8889 of Lecture Notes in Computer Science,
pages 686–697. Springer, 2014.
[28] B. Mitavskiy, J. E. Rowe, and C. Cannings. Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of
links. International Journal of Intelligent Computing and Cybernetics, 2(2):243–284,
2009.
[29] F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization –
Algorithms and Their Computational Complexity. Natural Computing Series. Springer,
2010.
[30] P. S. Oliveto and C. Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59(3):369–386, 2011.
[31] P. S. Oliveto and C. Witt.
Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation.
CoRR, abs/1211.7184, 2012.
http://arxiv.org/abs/1211.7184.
[32] P. S. Oliveto and C. Witt. Improved time complexity analysis of the simple genetic
algorithm. Theoretical Computer Science, 605:21–41, 2015.
[33] J. E. Rowe and D. Sudholt. The choice of the offspring population size in the (1,λ) EA.
In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2012),
pages 1349–1356. ACM Press, 2012.
[34] G. H. Sasak and B. Hajek. The time complexity of maximum matching by simulated
annealing. Journal of the ACM, 35:387–403, 1988.
27

[35] D. Sudholt. A new method for lower bounds on the running time of evolutionary
algorithms. IEEE Trans. on Evolutionary Computation, 17(3):418–435, 2013.
[36] I. Wegener. Theoretical aspects of evolutionary algorithms. In Proc. of the 28th
International Colloquium on Automata, Languages and Programming (ICALP 2001),
volume 2076 of LNCS, pages 64–78. Springer, 2001.
[37] C. Witt. Tight bounds on the optimization time of a randomized search heuristic
on linear functions. Combinatorics, Probability & Computing, 22(2):294–318, 2013.
Preliminary version in STACS 2012.

28

A

Existing Drift Theorems as Special Cases

In this appendix, we show that virtually all known variants of drift theorems with drift
towards the target can be derived from our general Theorem 3 with surprisingly short
proofs.

A.1

Variable Drift and Fitness Levels

A clean form of a variable drift theorem, generalizing previous formulations from [21] and
[28], was presented in [33]. We restate this theorem in our notation and carry out two
generalizations: we allow for a continuous state space instead of demanding a finite one
and do not fix xmin = 1.
Theorem 16 (Variable Drift, Upper Bound; following [33]). Let (Xt )t∈N0 , be a stochastic
process over some state space S ⊆ {0}∪[xmin , xmax ], where xmin > 0. Let h(x) : [xmin , xmax ] →
R+ be a monotone increasing function such that 1/h(x) is integrable on [xmin , xmax ] and
E(Xt − Xt+1 | Ft ) ≥ h(Xt ) if Xt ≥ xmin . Then it holds for the first hitting time
T := min{t | Xt = 0} that
xmin
+
E(T | X0 ) ≤
h(xmin )

Z

X0
xmin

1
dx.
h(x)

Proof. Since
R x h(x) is monotone increasing, 1/h(x) is decreasing and the function g(x) :=
x/ min + xmin 1/h(y) dy, defined in Remark 2, is concave on [0, xmax ]. By Jensen’s inequality, we get
E(g(Xt ) − g(Xt+1 ) | Ft ) ≥ g(Xt ) − g(E(Xt+1 | Ft ))
Z Xt
Z Xt
1
1
=
dx ≥
dx,
E(Xt+1 |Ft ) h(x)
Xt −h(Xt ) h(x)
where the equality just expanded g(x). Using that 1/h(x) is decreasing, it follows
Z

Xt
Xt −h(Xt )

1
dx ≥
h(x)

Z

Xt

Xt −h(Xt )

1
h(Xt )
dy =
= 1.
h(Xt )
h(Xt )

Plugging in αu := 1 in Theorem 3 completes the proof.
In [33] it was also pointed out that variable drift theorems in discrete search spaces
look similar to bounds obtained from the fitness level technique (also called the method of
f -based partitions, first formulated in [36]). For the sake of completeness, we present the
classical upper bounds by fitness levels w. r. t. the (1+1) EA here and prove them by drift
analysis.
Theorem 17 (Classical Fitness Levels, following [36]). Consider the (1+1) EA maximizing
some function f and a partition of the search space into non-empty sets A1 , . . . , Am . Assume
that the sets form an f -based partition, i. e., for 1 ≤ i < j ≤ m and all x ∈ Ai , y ∈ Aj it
29

holds f (x) < f (y). Let pi be a lower bound on the probability that a search point in Ai is
mutated into a search point in ∪m
j=i+1 Aj . Then the expected hitting time of Am is at most
Pm−1 1
i=1 pi .

Proof. At each point of time, the (1+1) EA is in a unique fitness level. Let Yt the current
fitness level at time t. We consider the process defined by Xt = m − Yt . By definition
of fitness levels and the (1+1) EA, Xt is non-increasing over time. Consider Xt = k for
1 ≤ k ≤ m − 1. With probability pm−k , the X-value decreases by at least 1. Consequently,
E(Xt − Xt+1 | Xt = k) ≥ pm−k . We define h(x) = pm−⌈x⌉ , xmin = 1 and xmax = m − 1
and obtain an integrable, monotone increasing function on [xP
min , xmax ]. Hence, the upper
1
1
bound on E(T | X0 ) from Theorem 16 becomes at most p1 + m−2
i=1 pm−i , which completes
the proof.
Recently, the fitness-level technique was considerably refined and supplemented by lower
bounds [35]. We can also identify these extensions as a special case of general drift. This
material is included in an subsection on its own, Appendix B. Similarly, we have moved a
treatment of variable drift theorems with non-monotone drift to Appendix C.
Finally, so far only two theorems dealing with upper bounds on variable drift and thus
lower bounds on the hitting time seems to have been published. The first one was derived
in [8]. Again, we present a variant without unnecessary assumptions, more precisely we
allow continuous state spaces and use less restricted c(x) and h(x).
Theorem 18 (Variable Drift, Lower Bound; following [8]). Let (Xt )t∈N0 , be a stochastic
process over some state space S ⊆ {0} ∪ [xmin , xmax ], where xmin > 0. Suppose there exists
two functions c, h : [xmin , xmax ] → R+ such that h(x) is monotone increasing and 1/h(x)
integrable on [xmin , xmax ], and for all t ≥ 0,
(i) Xt+1 ≤ Xt ,
(ii) Xt+1 ≥ c(Xt ) for Xt ≥ xmin ,
(iii) E(Xt − Xt+1 | Ft ) ≤ h(c(Xt )) for Xt ≥ xmin .
Then it holds for the first hitting time T := min{t | Xt = 0} that
xmin
+
E(T | X0 ) ≥
h(xmin )

Z

X0
xmin

1
dx.
h(x)

Proof. Using the definition of g according to Remark 2, we compute the drift
!
Z Xt
1
dx | Ft
E(g(Xt ) − g(Xt+1 ) | Ft ) = E
Xt+1 h(x)
!
Z Xt
1
≤ E
dx | Ft ,
Xt+1 h(c(Xt ))

30

where we have used that Xt ≥ Xt+1 ≥ c(Xt ) and that h(x) is monotone increasing. The
last integral equals
Xt − E(Xt+1 | Ft )
h(c(x))
≤
= 1.
h(c(Xt ))
h(c(x))
Plugging in αℓ := 1 in Theorem 3 completes the proof.
Very recently, Theorem 18 was relaxed in [16] by replacing the deterministic condition
Xt+1 ≥ c(Xt ) by a probabilistic one. We note without proof that also this generalization
can be proved with Theorem 3.

A.2

Multiplicative Drift

We continue by showing that Theorem 3 can be specialized in order to re-obtain other
classical and recent variants of drift theorems. Of course, Theorem 3 is a generalization of
additive drift (Theorem 1), which interestingly was used to prove the general theorem itself.
The remaining important (in fact possibly the most important) strand of drift theorems is
therefore represented by so-called multiplicative drift, which we focus on in this subsection.
Roughly speaking, the underlying assumption is that the progress to the optimum is proportional to the distance (or can be bounded in this way). Early theorems covering this
scenario, without using the notion of of drift, can be found in [4].
The following theorem is the strongest variant of the multiplicative drift theorem (originally introduced by [12]), which can be found in [9]. It was used to analyze RSHs on
combinatorial optimization problems and linear functions. Here we also need a tail bound
from our main theorem (more precisely, the third item in Theorem 3). Note that the multiplicative drift theorem requires xmin to be positive, i. e., a gap in the state space. Without
the gap, no finite first hitting time can be proved from the prerequisites of multiplicative
drift.
Theorem 19 (Multiplicative Drift, Upper Bound; following [9]). Let (Xt )t∈N0 , be a stochastic process over some state space S ⊆ {0} ∪ [xmin , xmax ], where xmin > 0. Suppose that there
exists some δ, where 0 < δ < 1 such that E(Xt − Xt+1 | Ft ) ≥ δXt . Then the following
statements hold for the first hitting time T := min{t | Xt = 0}.
(i) E(T | X0 ) ≤
(ii) Pr(T ≥

ln(X0 /xmin )+1
.
δ

ln(X0 /xmin )+r
δ

| X0 ) ≤ e−r for all r > 0.

Proof. Choosing h(x) = δx, the process satisfies Condition (i) of Corollary 4, which implies
that
Z X0
1
ln(X0 /xmin ) + 1
xmin
dy =
,
+
E(T | X0 ) ≤
δxmin
δ
xmin δy
which proves the first item from the theorem. The process also satisfies Condition (iii) of
Corollary 4, however, this will result in the loss of a factor e in the tail bound. We argue
directly instead.
31

Using the notation from Theorem 3, we choose h(x) = δx and obtain E(Xt − Xt+1 |
Ft ) ≥ h(Xt ) by the prerequisite Ron multiplicative drift. Moreover, according to Remark 2
x
we define g(x) = xmin /(δxmin ) + xmin 1/(δy) dy = 1/δ + ln(x/xmin )/δ for x ≥ xmin . We set
a := 0 and consider
E(e−δ(g(Xt )−g(Xt+1 )) | Ft ; Xt ≥ xmin ) = E(eln(Xt+1 /xmin )−ln(Xt /xmin ) ) | Ft ; Xt ≥ xmin )
= E((Xt+1 /Xt ) | Ft ; Xt ≥ xmin ) ≤ 1 − δ,

Hence, we can choose βu (t) = 1 − δ for all Xt ≥ xmin and λ = δ in the third item of
Theorem 3 to obtain
Pr(T > t | X0 ) < (1 − δ)t · eδ(g(X0 )−g(xmin )) ≤ e−δt+ln(X0 /xmin ) .
Now the second item of Theorem 19 follows by choosing t := (ln(X0 /xmin ) + r)/δ.
Compared to the upper bound, the following lower-bound includes a condition on the
maximum step-wise progress and requires non-increasing sequences. It generalizes the version in [37] and its predecessor in [26] by not assuming xmin ≥ 1.
Theorem 20 (Multiplicative Drift, Lower Bound; following [37]). Let (Xt )t∈N0 , be a
stochastic process over some state space S ⊆ {0} ∪ [xmin , xmax ], where xmin > 0. Suppose that there exist β, δ, where 0 < β, δ ≤ 1 such that for all t ≥ 0
(i) Xt+1 ≤ Xt ,
(ii) Pr(Xt − Xt+1 ≥ βXt ) ≤

βδ
1+ln(Xt /xmin ) .

(iii) E(Xt − Xt+1 | Ft ) ≤ δXt
Define the first hitting time T := min{t | Xt = 0}. Then
E(T | X0 ) ≥

ln(X0 /xmin ) + 1 1 − β
·
.
δ
1+β

Proof. Using the definition of g according to Remark 2, we compute the drift
!
Z Xt
1
E(g(Xt ) − g(Xt+1 ) | Ft ) = E
dx | Ft
Xt+1 h(x)
!
Z Xt
1
dx ; Xt+1 ≥ (1 − β)Xt | Ft · Pr(Xt+1 ≥ (1 − β)Xt )
≤ E
Xt+1 h(x)
+ g(Xt ) · (1 − Pr(Xt+1 ≥ (1 − β)Xt ))
where we used the law of total probability and g(Xt+1 ) ≥ 0. As in the proof of Theorem 19,
we have g(x) = (1 + ln(x/xmin ))/δ. Plugging in h(x) = δx, using the bound on Pr(Xt+1 ≥

32

(1 − β)Xt ) and Xt+1 ≤ Xt , the drift is further bounded by
!
Z Xt
1
βδ
1 + ln(Xt /xmin )
E
·
dx | Ft +
1 + ln(Xt /xmin )
δ
Xt+1 δ(1 − β)Xt
=

E(Xt − Xt+1 | Ft )
δXt
1+β
+β ≤
+β ≤
,
δ(1 − β)Xt
δ(1 − β)Xt
1−β

Using αℓ = (1 + β)/(1 − β) and expanding g(X0 ), the proof is complete.
Very recently, it was shown in [7] that the monotonicity condition Xt+1 ≤ Xt in Theorem 20 can be dropped if item (iii) is replaced by E(s − Xt+1 · 1 {Xt+1 ≤ s} | Ft ) ≤ δs
for all s ≤ Xt . We note without proof that also this strengthened theorem can be obtained
from our general drift theorem.

B

Fitness Levels Lower and Upper Bounds as Special Cases

We pick up the consideration of fitness levels again and prove the following lower-bound
theorem due to Sudholt [35] by drift analysis. See Sudholt’s paper for possibly undefined
or unknown terms.
Theorem 21 (Theorem 3 in [35]). Consider an algorithm A and a partition of the search
space into non-empty sets A1 , . . . , Am . For a mutation-based EA A we again say that A
is in Ai or on level i if the best individual created so far is in Ai .PLet the probability of A
traversing from level i to level j in one step be at most ui · γi,j and m
j=i+1 γi,j = 1. Assume
that for all j > i and some 0 ≤ χ ≤ 1 it holds
γi,j ≥ χ

m
X

γi,k .

(1)

k=j

Then the expected hitting time of Am is at least
m−1
X
i=1

≥



Pr(A starts in Ai ) · 

m−1
X
i=1

1
+χ
ui

Pr(A starts in Ai ) · χ

m−1
X
j=i

m−1
X

j=i+1

1
.
uj



1
uj

Proof. Since χ ≤ 1, the second lower bound follows immediately from the first one, which
we prove in the following. To adopt the perspective of minimization, we say that A is on
distance level m − i if the best individual created so far is in Ai . Let Xt be the algorithm’s
distance level at time t. We define the drift function g mapping distance levels to nonnegative numbers (which then form a new stochastic process) by
m−1
X 1
1
+χ
g(m − i) =
ui
uj
j=i+1

33

for 1 ≤ i ≤ m − 1. Defining um := ∞, we extend the function to g(0) = 0. Our aim is to
prove that the drift
∆t (m − i) := E(g(m − i) − g(Xt+1 ) | Xt = m − i)
has expected value at most 1. Then the theorem follows immediately using additive drift
(Theorem 1) along with the law of total probability to condition on the starting level.
To analyze the drift, consider the case that the distance level decreases from m − i to
m − ℓ, where ℓ > i. We obtain
g(m − i) − g(m − ℓ) =

ℓ
X
1
1
1
−
+χ
,
ui uℓ
uj
j=i+1

which by the law of total probability (and as the distance level cannot increase) implies


ℓ
m
X
X
1
1
1

ui · γi,ℓ  −
∆t (m − i) =
+χ
ui uℓ
u
j=i+1 j
ℓ=i+1


m
ℓ
X
X
1
1
= 1 + ui
γi,ℓ − + χ
,
uℓ
uj
j=i+1

ℓ=i+1

where the last equality used

Pm

ℓ=i+1 γi,ℓ

m
X

γi,ℓ χ

ℓ=i+1

= 1. If we can prove that

m
ℓ
X
X
1
1
≤
γi,ℓ ·
uj
uℓ

j=i+1

(2)

ℓ=i+1

then ∆t (m − i) ≤ 1 follows and the proof is complete. To show this, observe that
m
X

ℓ=i+1

γi,ℓ χ

m
m
ℓ
X
X
X
1
1
=
·χ
γi,ℓ
uj
uj
j=i+1

j=i+1

ℓ=j

since the term u1j appears for all terms ℓ = j, . . . , m in the outer sum, each term weighted
P
by γi,ℓ χ. By (1), we have χ m
ℓ=j γi,ℓ ≤ γi,j , and (2) follows.

We remark here without going into the details that also the refined upper bound by
fitness levels (Theorem 4 in [35]) can be proved using general drift.

C

Non-monotone Variable Drift

In many applications, a monotone increasing function h(x) bounds the drift from below.
For example, the expected progress towards the optimum of OneMax increases with the
distance of the current search point from the optimum. However, certain ant colony optimization algorithms do not have this property and exhibit a non-monotone drift [10]. To
34

handle this case, generalizations of the variable drift theorem have been developed that does
not require h(x) to be monotone. The most recent version of this theorem is presented in
[15]. Unfortunately, it turned out that the two generalizations suffer from a missing condition, relating positive and negative drift to each other. Adding the condition and removing
an unnecessary assumption (more precisely, the continuity of h(x)) the theorem in [15] can
be corrected as follows. Note that this formulation is also used in [32] but proved with a
specific drift theorem instead of our general approach.
Theorem 22 (extending [15]). Let (Xt )t∈N0 , be a stochastic process over some state space
S ⊆ {0}∪[xmin , xmax ], where xmin > 0. Suppose there exists two functions h, d : [xmin , xmax ] →
R+ , where 1/h is integrable, and a constant c ≥ 1 such that for all t ≥ 0
1. E(Xt − Xt+1 ; Xt ≥ xmin | Ft ) ≥ h(Xt ),

2.

E((Xt+1 −Xt )·1{Xt+1 >Xt } ; Xt ≥xmin |Ft )
E((Xt −Xt+1 )·1{Xt+1 <Xt } ; Xt ≥xmin |Ft )

≤

1
,
2c2

3. |Xt − Xt+1 | ≤ d(Xt ) if Xt ≥ xmin ,
4. for all x, y ≥ xmin with |x − y| ≤ d(x), it holds h(min{x, y}) ≤ ch(max{x, y}).

Then it holds for the first hitting time T := min{t | Xt = 0} that


Z X0
1
xmin
+
dx .
E(T | X0 ) ≤ 2c
h(xmin )
xmin h(x)

It is worth noting that Theorem 16 is not necessarily a special case of Theorem 22.

Proof of Theorem 22. Using the definition of g according to Remark 2 and assuming Xt ≥
xmin , we compute the drift
!
Z Xt
1
dx Ft
E(g(Xt ) − g(Xt+1 ) | Ft ) = E
Xt+1 h(x)
!
Z Xt+1

Z Xt
1
1
= E
dx · 1 {Xt+1 < Xt } Ft − E
dx · 1 {Xt+1 > Xt } Ft ,
h(x)
Xt+1 h(x)
Xt
where equality holds since the integral is empty if Xt+1 = Xt . Item (4) from the prerequisites yields h(x) ≤ ch(Xt ) if Xt − d(Xt ) ≤ x < Xt and h(x) ≥ h(Xt )/c if Xt < x ≤
Xt + d(Xt ). Using this and |Xt − Xt+1 | ≤ d(Xt ), the drift can be further bounded by
!
Z Xt+1

Z Xt
c
1
dx · 1 {Xt+1 < Xt } Ft − E
dx · 1 {Xt+1 > Xt } Ft
E
h(Xt )
Xt
Xt+1 ch(Xt )
Z Xt+1

E((Xt − Xt+1 Ft ) · 1 {Xt+1 < Xt })
1
≥ E
dx · 1 {Xt+1 < Xt } Ft =
2ch(Xt )
2ch(Xt )
Xt
1
h(Xt )
=
,
≥
2ch(Xt )
2c
where the first inequality used the Item (2) from the prerequisites and the last one Item (1).
Plugging in αu := 1/(2c) in Theorem 3 completes the proof.

35

