The Fitness Level Method with Tail Bounds
Carsten Witt
DTU Compute
Technical University of Denmark
2800 Kgs. Lyngby

arXiv:1307.4274v1 [] 16 Jul 2013

Denmark

July 17, 2013
Abstract
The fitness-level method, also called the method of f -based partitions,
is an intuitive and widely used technique for the running time analysis of
randomized search heuristics. It was originally defined to prove upper and
lower bounds on the expected running time. Recently, upper tail bounds
were added to the technique; however, these tail bounds only apply to running times that are at least twice as large as the expectation.
We remove this restriction and supplement the fitness-level method with
sharp tail bounds, including lower tails. As an exemplary application, we
prove that the running time of randomized local search on OneMax is
sharply concentrated around n ln n − 0.1159n.

1

Introduction

The running time analysis of randomized search heuristics, including evolutionary
algorithms, ant colony optimization and particle swarm optimization, is a vivid
research area where many results have been obtained in the last 15 years. Different
methods for the analysis were developed as the research area grew. For an overview
of the state of the art in the area see the books by Auger and Doerr (2011),
Neumann and Witt (2010) and Jansen (2013).
The fitness-level method, also called the method of fitness-based partitions,
is a classical and intuitive method for running time analysis, first formalized by
Wegener (2001). It applies to the case that the total running time of a search
heuristic can be represented as (or bounded by) a sum of geometrically distributed
waiting times, where the waiting times account for the number of steps spent on
1

certain levels of the search space. Wegener (2001) presented both upper and lower
bounds on the running time of randomized search heuristics using the fitness-level
method. The lower bounds relied on the assumption that no level was allowed to
be skipped. Sudholt (2013) significantly relaxed this assumption and presented a
very general lower-bound version of the fitness-level method that allows levels to
be skipped with some probability.
Only recently, the focus in running time analysis turned to tail bounds, also
called concentration inequalities. Zhou, Luo, Lu, and Han (2012) were the first
to add tail bounds to the fitness-level method. Roughly speaking, they prove
w. r. t. the running time T that Pr(T > 2E(T ) + 2δh) = e−δ holds, where h is
the worst-case expected waiting time over all fitness levels and δ > 0 is arbitrary.
An obvious open question was whether the factor 2 in front of the expected value
could be “removed” from the tail bound, i. e., replaced with 1; Zhou et al. (2012)
only remark that the factor 2 can be replaced with 1.883.
In this article, we give a positive answer to this question and supplement the
fitness-level method also with lower tail bounds. Roughly speaking, we prove
2
in Section 2 that Pr(T < E(T ) + δ) ≤ e−δ /(2s) and Pr(T > E(T ) + δ) ≤
2
e− min{δ /(4s),δh/4} , where s is the sum of the squares of the waiting times over all
fitness levels. We apply the technique to a classical benchmark problem, more precisely to the running time analysis of randomized local search (RLS) on OneMax
in Section 3, and prove a very sharp concentration of the running time around
n ln n − 0.1159n. We finish with some conclusions and a pointer to related work.

2

New Tail Bounds for Fitness Levels

Miscellaneous authors (2011) on the internet discussed tail bounds for a special case
of our problem, namely the coupon collector problem (Motwani and Raghavan,
1995, Chapter 3.6). Inspired by this discussion, we present our main result in
Theorem 1 below. It applies to the scenario that a random variable (e. g., a
running time) is given as a sum of geometrically distributed independent random
variables (e. g., waiting times on fitness levels). A concrete application will be
presented in Section 3.
Theorem 1. Let Xi , 1 ≤ i ≤ n, be independent random variables
Pnfollowing
the
geometric
distribution
with
success
probability
p
,
and
let
X
:=
i
i=1 Xi . If
Pn
2
i=1 (1/pi ) ≤ s < ∞ then for any δ > 0
δ2

Pr(X < E(X) − δ) ≤ e− 2s .
For h := min{pi | i = 1, . . . , n},
Pr(X > E(X) + δ) ≤ e− 4 ·min{ s ,h} .
δ

2

δ

For the proof, the following two simple inequalities will be used.
Lemma 1.
ex
1+x

1. For x ≥ 0 it holds

2. For 0 ≤ x ≤ 1 it holds

≤ ex
e−x
1−x

2 /2

.

≤ ex

2 /(2−2x)

.

Proof. We start with the first inequality. The series representation of the exponential function yields
x

e =

∞
X
xi
i=0

since x ≥ 0. Hence,

∞
X
x2i
≤
(1 + x)
i!
(2i)!
i=0

∞
X
ex
x2i
≤
.
1+x
(2i)!
i=0

Since (2i)! ≥ 2i i!, we get
∞
X
x2i
ex
2
≤
= ex /2 .
i
1+x
2 i!
i=0

To prove the second inequality, we omit all negative terms except for −x from
the series representation of e−x to get
P
x2i
∞
X
1−x+ ∞
x2i
e−x
i=1 (2i)!
≤
= 1+
.
1−x
1−x
(1 − x) · (2i)!
i=1
For comparison,
ex

2 /(2−2x)

= 1+

∞
X
i=1

x2i
,
2i (1 − x)i i!

which, as x ≤ 1, is clearly not less than our estimate for e−x /(1 − x).
Proof of Theorem 1. Both the lower and upper tail are analyzed similarly, using
the exponential method (see, e. g., the proof of the Chernoff bound in Motwani and
Raghavan,
1995, Chapter 3.6). We start with the lower tail. Let d := E(X) − δ =
Pn
i=1 (1/pi ) − δ. Since for any t ≥ 0
X < d ⇐⇒ −X > −d ⇐⇒ e−tX > e−td ,

3

Markov’s inequality and the independence of the Xi yield that

n
Y

E e−tX
td
Pr(X < d) ≤
=e ·
E e−tXi .
−td
e
i=1
Note that the last product involves the moment-generating functions (mgf’s) of
the Xi . Given a geometrically distributed random variable
Y with parameter p, its

r
1
moment-generating function at r ∈ R equals E erY = 1−epe
r (1−p) = 1−(1−e−r )/p for
r < − ln(1 − p). We will only use negative values for r, which guarantees existence
of the mgf’s used in the following. Hence,
td

Pr(X < d) ≤ e ·

n
Y
i=1

n
Y
1
1
td
≤e ·
,
t
1 − (1 − e )/pi
1
+
t/p
i
i=1

where we have used ex ≥ 1 + x for x ∈ R. Now, by writing the numerators as
2
ex
et/pi · e−t/pi , using 1+x
≤ ex /2 for x ≥ 0 (Lemma 1) and finally plugging in d, we
get
!
n
Y
Pn
2
2
2
2
2
Pr(X < d) ≤ etd ·
et /(2pi ) e−t/pi = etd e(t /2) i=1 (1/pi ) e−tE(X) ≤ e−tδ+(t /2)s .
i=1

The last exponent is minimized for t = δ/s, which yields
δ2

Pr(X < d) ≤ e− 2s
and proves the lower tail inequality.
For the upper tail, we redefine d := E(X) + δ and obtain

n
Y

E etX
−td
=e ·
E etXi .
Pr(X > d) ≤
td
e
i=1
Estimating the moment-generating functions similarly as above, we get
!
n
−t/pi
Y
e
Pr(X > d) ≤ e−td ·
· et/pi .
1 − t/pi
i=1
Since now positive arguments are used for the moment-generating functions, we
limit ourselves to t ≤ min{pi | i = 1, . . . , n}/2 = h/2 to ensure convergence. Using
2
e−x
≤ ex /(2−2x) for 0 ≤ x ≤ 1 (Lemma 1), we get
1−x
!
!
n
n
Y
Y
2
2
2
2
2
et /(pi (2−2t/pi )) · et/pi =
e−tδ+t /pi ≤ e−tδ+t s ,
Pr(X > d) ≤ e−td ·
i=1

i=1

4

which is minimized for t = δ/(2s). If δ ≤ sh, this choice satisfies t ≤ h/2. Then
−tδ + t2 s = −δ 2 /(4s) and we get
δ2

Pr(X > d) ≤ e− 4s .
Otherwise, i. e. if δ > sh, we set t = h/2 to obtain −tδ + t2 s = −δh/2 + s(h/2)2 ≤
−δh/2 + δh/4 = −δh/4. Then
δh

Pr(X > d) ≤ e− 4 .
Joining the two cases in a minimum leads to the lower tail.
Based on Theorem 1, we formulate the fitness-level theorem with tail bounds for
general optimization algorithms A instead of a specific randomized search heuristic
(see also Sudholt, 2013, who uses a similar approach).
Theorem 2 (Fitness Levels with Tail Bounds). Consider an algorithm A 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 holds f (x) < f (y). We say that A is in Ai or on
level i if the best search point created so far is in Ai .
1. If pi is a lower bound on the probability that a step of A leads from level i to
some higher level, independently of previous steps, then the first hitting time
of Am , starting from level k, is at most
m−1
X
i=k

1
+ δ.
pi

− 4δ ·min{ δs ,h}

with probability at least 1 − e
h = min{pi | i = k, . . . , m − 1}.

, for any finite s ≥

Pm−1
i=k

1
p2i

and

2. If pi is an upper bound on the probability that a step of A leads from level i
to level i + 1, independently of previous steps, and the algorithm cannot
increase its level by more than 1, then the first hitting time of Am , starting
from level k, is at least
m−1
X
i=k

with probability at least 1 − e

2
− δ2s

1
−δ
pi

.

Proof. By definition, the algorithm cannot go down on fitness levels. Estimate the
time to leave level i (from above resp. from below) by a geometrically distributed
random variable with parameter pi and apply Theorem 1.
5

3

Application to RLS on OneMax

We apply Theorem 2 to a classical benchmark problem in the analysis of randomized search heuristics, more precisely the running time of RLS on OneMax. RLS
is a well-studied randomized search heuristic, defined in Algorithm 1. The function OneMax : {0, 1}n → R is defined by OneMax(x1 , . . . , xn ) = x1 + · · · + xn ,
and the running time is understood as the first hitting time of the all-ones string
(plus 1 to count the initialization step).
t := 0.
choose an initial bit string x0 ∈ {0, 1}n uniformly at random.
repeat
create x0 by flipping a uniformly chosen bit in xt .
xt+1 := x0 if f (x0 ) ≥ f (xt ), and xt+1 := xt otherwise.
t := t + 1.
forever.
Algorithm 1: RLS for the maximization of f : {0, 1}n → R
Theorem 3. Let T be the running time of RLS on OneMax. Then
1. n ln n − 0.11594n − o(n) ≤ E(T ) ≤ n ln n − 0.11593n + o(n).
3r 2

2. Pr(T ≤ E(T ) − rn) ≤ e− π2 for any r > 0.
( 3r2
2
e− 2π2 if 0 < r ≤ π6
3. Pr(T ≥ E(T ) + rn) ≤
.
r
otherwise.
e− 4
Proof. We start with Statement 1, i. e., the bounds on the expected running time.
Let the fitness levels A0 , . . . , An be defined by Ai = {x ∈ {0, 1}n | OneMax(x) =
i} for 0 ≤ i ≤ n. By definition of RLS, the probability pi of leaving level i equals
pi = n/(n − i) for 0 ≤ i ≤ n − 1. Therefore, the expected running time from
starting level k is
n−1
n−k
X
X
n
1
= n
,
n−i
i
i=1
i=k
which leads to the weak upper bound E(T ) ≤ n ln n + n in the first place. Due
to the uniform initialization in RLS, Chernoff bounds yield Pr(n/2 − n2/3 ≤ k ≤
1/3
n/2 + n2/3 ) = 1 − e−Ω(n ) . We obtain




n/2+n2/3
n/2+n2/3
X
X 1
1
 + e−Ω(n1/3 ) · (n ln n + n) = n 
+ o(n).
E(T ) ≤ n 
i
i
i=1
i=1
6

We can now estimate the Harmonic number by ln(n/2 + n2/3 ) + γ + o(1) = ln n +
γ − ln 2 + o(1), where γ = 0.57721 . . . is the Euler-Mascheroni constant. Plugging
in numerical values for γ − ln 2 proves the upper bound on E(T ). The lower one
is proven symmetrically.
Pn−k 1
≤
For Statement 2, the lower tail bound, we use Theorem 2. Now, i=1
p2i
Pn n2
2
2
n π
=: s. Plugging δ := rn and s in the second part of the theorem
i=1 i2 ≤
6
r 2 n2

3r 2

yields Pr(T ≤ E(T ) − rn) ≤ e− 2s = e− π2 .
For Statement 3, the upper tail bound, we argue similarly but have to determine
when δs ≤ h. Note that h = min{pi } = 1/n. Hence, it suffices to determine when
2
6rn
≤ 1/n, which is equivalent to r ≤ π6 . Now the two cases of the lower bound
n2 π 2
follow by appropriately plugging δs or h in the first part of Theorem 2.
The stochastic process induced by RLS on OneMax equals the classical and
well-studied coupon collector problem (started with k full bins). Despite this fact,
the lower tail bound from Theorem 3 could not be found in the literature (see
also the comment introducing Theorem 1.24 in Doerr, 2011, which describes a
simple but weaker lower tail). There is an easy-to-prove upper tail bound for the
coupon collector of the kind Pr(T ≥ E(T ) + rn) ≤ e−r , which is stronger than
our result but not obvious to generalize. Finally, Scheideler (2000, Theorem 3.38)
suggests upper and lower tail bounds for sums of geometrically distributed random
variables, which could also be tried out in our
√ example; however, it then turns out
that these bounds are only useful if r = Ω( ln n).

4

Conclusions

We have supplemented upper and lower tail bounds to the fitness-level method.
The lower tails are novel contributions and the upper tails improve an existing
result from the literature significantly. As a proof of concept, we have applied the
fitness levels with tail bounds to the analysis of RLS on OneMax and obtained a
very sharp concentration result.
If the stochastic process under consideration is allowed to skip fitness levels,
which is often the case with globally searching algorithms such as evolutionary
algorithms, our upper tail bound may become arbitrarily loose and the lower tail
is even unusable. To prove tail bounds in such cases, drift analysis may be used,
which is another powerful and in fact somewhat related method for the running
time analysis of randomized search heuristics. See, e. g., Lehre and Witt (2013)
and references therein for further reading.
Acknowledgement. The author thanks Per Kristian Lehre for useful discussions.
7

References
Auger, A. and B. Doerr (Eds.) (2011). Theory of Randomized Search Heuristics:
Foundations and Recent Developments. World Scientific Publishing.
Doerr, B. (2011). Analyzing randomized search heuristics: Tools from probability theory. In A. Auger and B. Doerr (Eds.), Theory of Randomized Search
Heuristics: Foundations and Recent Developments, Chapter 1. World Scientific
Publishing.
Jansen, T. (2013). Analyzing Evolutionary Algorithms - The Computer Science
Perspective. Natural Computing Series. Springer.
Lehre, P. K. and C. Witt (2013). General drift analysis with tail bounds. Technical
report, arXiv:1307.2559. http://arxiv.org/abs/1307.2559.
Miscellaneous authors (2011).
What is a tight lower bound on the
coupon collector time. http://stats.stackexchange.com/questions/7774/
what-is-a-tight-lower-bound-on-the-coupon-collector-time.
Motwani, R. and P. Raghavan (1995). Randomized algorithms. Cambridge University Press.
Neumann, F. and C. Witt (2010). Bioinspired Computation in Combinatorial Optimization – Algorithms and Their Computational Complexity. Natural Computing Series. Springer.
Scheideler, C. (2000). Probabilistic Methods for Coordination Problems, Volume 78
of HNI-Verlagsschriftenreihe. University of Paderborn. Habilitation thesis.
Available at: http://www.cs.jhu.edu/%7Escheideler/papers/habil.ps.gz.
Sudholt, D. (2013). A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation 17 (3),
418–435.
Wegener, I. (2001). Theoretical aspects of evolutionary algorithms. In Proceedings
of the 28th International Colloquium on Automata, Languages and Programming
(ICALP 2001), Volume 2076 of Lecture Notes in Computer Science, pp. 64–78.
Springer.
Zhou, D., D. Luo, R. Lu, and Z. Han (2012). The use of tail inequalities on
the probable computational time of randomized search heuristics. Theoretical
Computer Science 436, 106–117.

8

