arXiv:1801.06733v2 [] 29 Jan 2018

Probabilistic Tools for the Analysis of
Randomized Optimization Heuristics
Benjamin Doerr
Laboratoire d’Informatique (LIX)
École Polytechnique
Palaiseau
France
January 31, 2018
Abstract
This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics. This includes classic
material like Markov, Chebyshev and Chernoff inequalities, but also lesser
known topics like stochastic domination and coupling or Chernoff bounds
for geometrically distributed random variables and for negatively correlated
random variables. Almost all of the results presented here have appeared
previously, some, however, only in recent conference publications. While the
focus is on collecting tools for the analysis of randomized search heuristics,
many of these may be useful as well in the analysis of classic randomized
algorithms or discrete random structures.

1

Introduction

Unlike in the field of classic randomized algorithms for discrete optimization problems, where theory has always supported (and, in fact, often led) the development
and understanding of new algorithms, the theoretical analysis of nature-inspired
search heuristics is much younger than the use of these heuristics. The use of
nature-inspired heuristics can easily be traced back to the 1960s, their rigorous
analysis with proven performance guarantees only started in the late 1990s. Propelled by impressive results, most notably from the German computer scientist
Ingo Wegener (*1950–†2008) and his students, theoretical works became quickly
accepted in the nature-inspired algorithms field and now form an integral part of it.
1

They now help to understand these methods, guide the choice of their parameters,
and even (as in the classic algorithms field) suggest new promising algorithms.
It is safe to say that Wegener’s vision that nature-inspired heuristics are nothing
more than a particular class of randomized algorithms, which therefore should be
analyzed with the same rigor as other randomized algorithms, has come true.
After around 20 years of theoretical analysis of nature-inspired algorithms,
however, we have to note that the methods used here are different from those in
the analysis of classic randomized algorithms. This is most visible for particular methods like the fitness level method or drift analysis, but applies even to the
elementary probabilistic tools employed throughout the field. The aim of this chapter is to collect those elementary tools which often have been used in the past 20
years. This includes classic material like expectations, variances, the coupon collector process, Markov’s inequality, Chebyshev’s inequality and Chernoff-Hoeffding
bounds for sums of independent random variables, but also topics that are used
rarely outside the analysis of nature-inspired heuristics like stochastic domination,
Chernoff-Hoeffding bounds for sums of independent geometrically distributed random variables, and Chernoff-Hoeffding bounds for sums of random variables which
are not fully independent. For all results, we also sketch a typical application or
refer to applications in the literature. The large majority of the results and applications presented in this work have appeared previously, some in textbooks, some
in recent conference publications.
This chapter aims to serve both as introduction for newcomers to the field
and as reference book for regular users of these methods. With both addressees
in mind, we did not shy away from stating also elementary reformulations of the
results. We hope that this saves all users of this chapter some time, which is better
spent on understanding the challenging random processes that arise in the analysis
of nature-inspired heuristics.

2

Notation

All notation in this chapter is standard and should need not much additional
explanation. We use N := {1, 2, . . . } to denote the positive integers. We write
N0 := N ∪ {0}. For intervals of integers, we write [a..b] := {x ∈ Z | a ≤ x ≤ b}.
We use the standard definition 00 := 1 (and not 00 = 0).

3

Elementary Probability Theory

We shall assume that the reader has some basic understanding of the concepts
of probability spaces, events and random variables. As usual in probability theory
2

and very convenient in analysis of algorithms, we shall almost never explicitly state
the probability space we are working in. Hence an intuitive understanding of the
notion of a random variable should be enough to follow this exposition.
While many results presented in the following naturally extend to continuous
probability spaces, in the interest of simplicity and accessability for a discrete
optimization audience, we shall assume that all random variables in this book
will be discrete, that is, they take at most a countable number of values. As
a simple example, consider the random experiment of independently rolling two
distinguishable dice. Let X1 denote the outcome of the first roll, that is, the
number between 1 and 6 which the first die displays. Likewise, let X2 denote
the outcome of the second roll. These are already two random variables. We
formalize the statement that with probability 16 the first die shows a one by saying
Pr[X1 = 1] = 16 . Also, the probability that both dice show the same number is
Pr[X1 = X2 ] = 61 . The complementary event that they show different numbers,
naturally has a probability of Pr[X1 6= X2 ] = 1 − Pr[X1 = X2 ] = 65 .
We can add random variables (defined over the same probability space), e.g.,
X := X1 + X2 is the sum of the numbers shown by the two dice, and we can
multiply a random variable by a number, e.g., X := 2X1 is twice the number
shown by the first die.
The most common type of random variable we shall encounter in this book is an
extremely simple one called binary random variable or Bernoulli random variable.
It takes the values 0 and 1 only. In consequence, the probability distribution of a
binary random variable X is fully described by its probability Pr[X = 1] of being
one, since Pr[X = 0] = 1 − Pr[X = 1].
Binary random variables often show up as indicator random variables for random events. For example, if the random experiment is a simple roll of a die, we
may define a random variable X by setting X = 1, if the die shows a 6, and X = 0
otherwise. We say that X is the indicator random variable for the event “die shows
a 6.”
Indicator random variables are useful for counting. If we roll a die n times and
X1 , . . . , Xn are the indicator random variables for the events that the correspondP
ing roll showed a 6 (considered as a success), then ni=1 Xi is a random variable
describing the number of times we saw a 6 in these n rolls. In general, a random
variable X that is the sum of n independent binary random variables being one
all with equal probability p, is called a binomial random variable (with success
probability p). We denote this distribution by Bin(n, p) and write X ∼ Bin(n, p)
to denote that X has this distribution. We have
!

n k
p (1 − p)n−k
Pr[X = k] =
k
for all k ∈ [0..n]. See Section 4.3 for the definition of the binomial coefficient.
3

A different question is how long we have to wait until we roll a 6. Assume that
we have an infinite sequence of die rolls and X1 , X2 , . . . are the indicator random
variables for the event that the corresponding roll showed a 6 (success). Then we
are interested in the random variable Y = min{k ∈ N | Xk = 1}. Again for the
general case of all Xi being one independently with probability p > 0, this random
variable Y is called geometric random variable (with success probability p). We
denote this distribution by Geom(p) and write Y ∼ Geom(p) to indicate that Y
is geometrically distributed (with parameter p). We have
Pr[Y = k] = (1 − p)k−1 p
for all k ∈ N. We note that an equally established definition is to count only the
failures, that is, to regard the random variable Y − 1. So some care is necessary
when comparing results from different sources.

4

Useful Inequalities

Before starting our presentation of probabilistic tools useful in the analysis of
randomized search heuristics, let us briefly mention a few inequalities that are
often needed to estimate probabilities arising naturally in this area.

4.1

Switching Between Exponential and Polynomial Terms

When dealing with events occurring with small probability ε > 0, we often encounter expressions like (1 − ε)n . Such a mix of a polynomial term (1 − ε) with
an exponentiation is often hard to work with. It is therefore very convenient that
1 − ε ≈ e−ε , so that the above expression becomes approximately the purely exponential term e−εn . In this section, we collect a few estimates of this flavor. All
are well-known and can be derived via elementary arguments.
Lemma 1. For all x ∈ R,

1 + x ≤ ex .

We give a canonic proof as an example for a proof method that is often useful
for such estimates.
Proof. Define a function f : R → R by f (x) = ex − 1 − x for all x ∈ R. Since
f ′ (x) = ex − 1, we have f ′ (x) = 0 if and only if x = 0. Since f ′′ (x) = ex > 0 for
all x, we see that x = 0 is the unique minimum of f . Since f (0) = 0, we have
f (x) ≥ 0 for all x, which is equivalent to the claim of the lemma.

4

f (x) = 1 + x + x2
x2
f (x) = 1 + x + 1−x
f (x) = ex
f (x) = 1 + x

f (x)

3

2

1

0
−1

−0.5

0
x

0.5

1

Figure 1: Plot of the estimates of Lemma 1 and 2.
Applying Lemma 1 to −x and taking reciprocals, we immediately derive the
first of the following two upper bounds for the exponential function. The second
bound again follows from elementary calculus. Obviously, the first estimate is
better for x < 0, the second one is better for x > 0.
Lemma 2.

(a) For all x < 1,
ex ≤

x
x2
1
=1+
=1+x+
.
1−x
1−x
1−x

(1)

In particular, for 0 ≤ x ≤ 1, we have e−x ≤ 1 − x2 .
(b) For all x < 1.79,
ex ≤ 1 + x + x2 .

(2)

As visible also from Figure 1, these estimates are strongest for x close to zero.
x
Replacing x with 1+x
in the first inequality of Lemma 2 gives the following bounds.
Corollary 3. For all x > −1, we have
x

e 1+x ≤ 1 + x ≤ ex .
For all x, y > 0,

xy

e x+y ≤ (1 + xy )y ≤ ex .

(3)
(4)

A reformulation often useful on the context of standard-bit mutation (mutating
a bit-string by flipping each bit independently with a small probability like n1 ) is
5

f (x) = (1 − 1/x)x
f (x) = (1 − 1/x)x−0.5
f (x) = (1 − 1/x)x−1
f (x) = ((1 − 1/x)x−1 + (1 − 1/x)x )/2

0.8

f (x)

0.6
0.4
0.2

2

3

4

5

6

7

8

9

10

x
Figure 2: Plots related to Corollary 4.
the following. Note that the first bound holds for all r ≥ 1, while it is often only
stated for r ∈ N. For the (not so interesting) boundary case r = 1, recall that we
use the common convention 00 := 1.
Corollary 4. For all r ≥ 1 and 0 ≤ s ≤ r,
(1 − 1r )r ≤ 1e ≤ (1 − 1r )r−1 ,
(1 − rs )r ≤ e−s ≤ (1 − rs )r−s .

(5)
(6)

Proof.
Occasionally, it is useful to know that (1 − 1r )r is monotonically increasing and
that (1 − 1r )r−1 is monotonically decreasing in r (and thus both converge to 1e ).
Lemma 5. For all 1 ≤ s ≤ r, we have (1 − 1s )s ≤ (1 − 1r )r and (1 − 1s )s−1 ≥
(1 − 1r )r−1 .
Finally, we mention Bernoulli’s inequality and a related result. The lower
Q
bound on ni=1 (1 − pi ) in Lemma 6 (b) below is also valid when all pi ∈ (−∞, 0].
The upper bound will be proven at the end of the Section 5.2, both to show how
probabilistic arguments can be used to prove non-probabilistic results and because
we have not found a proof for it in the literature.
Lemma 6. (a) Bernoulli’s inequality: Let x ≥ −1 and r ∈ {0} ∪ [1, ∞). Then
(1 + x)r ≥ 1 + rx.
6

(b) Weierstrass product inequality: Let p1 , . . . , pn ∈ [0, 1]. Let P :=
Then
n
1−P ≤

4.2

Y

(1 − pi ) ≤ 1 − P +

i=1

X
i<j

Pn

i=1

pi .

pi pj ≤ 1 − P + 12 P 2 .

Harmonic Number

Quite frequently in the analysis of randomized search heuristics we will encounter
P
the harmonic number Hn . For all n ∈ N, it is defined by Hn = nk=1 k1 . Approximating this sum via integrals, namely by
Z

n+1
1

Z n
1
1
dx ≤ Hn ≤ 1 +
dx,
x
1 x

we obtain the estimate
ln n < Hn ≤ 1 + ln n

(7)

valid for all n ≥ 1. Sharper estimates involving the Euler-Mascheroni constant
γ ≈ 0.5772156649 are known, e.g.,
Hn = ln n + γ ± O( n1 ),
1
Hn = ln n + γ + 2n
± O( n12 ).
For non-asymptotic statements, it is helpful to know that Hn −ln n is monotonically
decreasing (with limit γ obviously). In most cases, however, the simple estimate (7)
will be sufficient.

4.3

Binomial Coefficients and Stirling’s Formula

Since discrete probability is strongly related to counting, we often encounter the
binomial coefficients defined by
!

n!
n
:=
k
k! (n − k)!
 

for all n ∈ N0 , k ∈ [0..n]. The binomial coefficient nk equals the number of kelement subsets ofa given n-element set. For this reason, the above definition is
often extended to nk := 0 for k > n.
In this section, we give several useful estimates for binomial coefficients. We
start by remarking that, while very precise estimates are available, in the analysis
of randomized search heuristics often crude estimates are sufficient.

7

The following lemma lists some estimates which all can be proven by elementary
P
kk
ki
means. To prove the second inequality of (11), note that ek = ∞
i=0 i! ≥ k! gives
the elementary estimate
!k
k
≤ k! ≤ k k .
(8)
e
Qn/2
n!
= i=1 2i(2i−1)
=
(n/2)!(n/2)!q
i2
P
Q
n/2
n/2
2n i=1 (1 − 2i1 ) ≤ 2n exp(− 12 i=1 1i ) ≤ 2n exp(− 12 ln n2 ) = 2n n2 , see Lemma 1




q
n
n+1
2
and (7), while for odd n we have ⌊n/2⌋
= 21 (n+1)/2
≤ 2n n+1
.

To prove (12), note that for even n we have



n
n/2



=

Lemma 7. For all n ∈ N and k ∈ [1..n], we have
!

(9)

!

(10)

n
≤ 2n ,
k
n
k

!k

n
≤ nk ,
≤
k
nk
n
≤
≤
k!
k
!

ne
k

!

!

!k

,

(11)
s

2
n
n
≤ 2n
≤
.
⌊n/2⌋
n
k

(12)





q

n
2
of (12),
Stronger estimates, giving also the well-known version ⌊n/2⌋
≤ 2n πn
+
can be obtained from Stirling’s formula below. See [HPR 14] for an analysis of
randomized search heuristics which clearly required Stirling’s formula.

Theorem 8 (Robbins [Rob55]). For all n ∈ N,
√
n! = 2πn( ne )n Rn ,
1
1
) < Rn < exp( 12n
) < 1.08690405.
where 1 < exp( 12n+1

Corollary 9. For all n ∈ N and k ∈ [1..n − 1],
!

1
n
=√
k
2π

s

n
k(n − k)

n
k

!k

n
n−k

1
1
where 0.88102729... = exp(− 16 + 25
) ≤ exp(− 12k
−
1
1
1
− 12(n−k)+1
+ 12n
) < 1.
exp(− 12k+1

!n−k

Rnk ,

1
12(n−k)

+

1
)
12n+1

< Rnk <

Stirling’s formula was also used in [DW14, proof of Lemma 8] to√compute
another useful fact, namely that all binomial coefficients that are O( n) away
from the middle one have the same asymptotic order of magnitude of Θ(2n n−1/2 ).
Here the upper bound is simply (12).
8

Corollary 10. Let γ ≥ 0. Let n ∈ N and ℓ =
n
2
o(1)) 2√2 πn e−4γ .

n
2

 
√
± γ n. Then nℓ ≥ (1 −

When working with mutation rates different from classic choice of n1 , the following estimates can be useful.
Lemma 11. Let n ∈ N, k ∈ [0..n], and p ∈ [0, 1]. Let X ∼ Bin(n, p).
(a) Let Y ∼ Bin(n, nk ). Then Pr[X = k] ≤ Pr[Y = k]. This inequality is strict
except for trivial case p = nk .
(b) For k ∈ [1..n − 1], Pr[X = k] ≤

√1
2π

q

n
.
k(n−k)

 

Proof. The first part follows from Pr[X = k] = nk pk (1 − p)n−k and noting that
p 7→ pk (1−p)n−k has a unique maximum in the interval [0, 1], namely at p = nk . The
second part follows from the first and using
  Corollary 9 to estimate the binomial
coefficient in the expression Pr[Y = k] = nk ( k1 )k (1 − nk )n−k .
For the special case that np = k, the second part of the lemma above was
already shown in [SW16]. For k ∈ {⌊np⌋, ⌈np⌉} but np 6= k, a bound larger than
ours by a factor of e was shown there as well.
To estimate sums of binomial coefficients, large deviations bounds (to be discussed in Section
10) can be an elegant tool. Imagine we need an upper bound
Pn n
for S = k=a k , where a > n2 . Let X be a random variable with distribution
Bin(n, 21 ). Then Pr[X ≥ a] = 2−n S. Using the additive Chernoff bound of The-

orem 53, we also see Pr[X ≥ a] = Pr[X ≥ E[X] + (a − n2 )] ≤ exp(−
2(a− n )2

2(a− n
)2
2
).
n

Consequently, S ≤ 2n exp(− n 2 ).
The same argument can even be used to estimate single binomial coefficients,
in particular,
to close to the middle one. Note that by Lemma 82,
  those
 not

P
S = nk=a nk and na are quite close when a is not too close to n2 . Hence
2(a − n2 )2
n
≤ 2n exp −
a
n
!

!

(13)

is a good estimate in this case.

5

Union Bound

The union bound, sometimes called Boole’s inequality, is a very elementary consequence of the axioms of a probability space, in particular, the σ-additivity of the
probability measure.
9

Lemma 12 (Union bound). Let E1 , . . . , En be arbitrary events in some probability
space. Then
#
"
Pr

n
[

i=1

Ei ≤

n
X

Pr[Ei ].

i=1

Despite its simplicity, the union bound is a surprisingly powerful tool in the
analysis of randomized algorithms. It draws its strength from the fact that does
not need any additional assumptions. In particular, the events Ei are not required
to be independent. Here is an example of such an application of the union bound.

5.1

Example: The (1 + 1) EA Solving the Needle Problem

The needle function is the fitness function f : {0, 1}n → Z defined by f (x) = 0
for all x ∈ {0, 1}n \ {(1, . . . , 1)} and f ((1, . . . , 1)) = 1. It is neither surprising
nor difficult to prove that all reasonable randomized search heuristics need time
exponential in n to find the maximum of the needle function. To give a simple
example for the use of the simplified drift theorem, it was shown in [OW11] that
the classic (1 + 1) EA within a sufficiently small exponential time does not even
get close to the optimum of the needle function (see Theorem 13 below). We now
show that the same result (and in fact a stronger one) can be shown via the union
bound.
The (1 + 1) EA is the simple randomized search heuristic that starts with a
random search point x ∈ {0, 1}n . Then, in each iteration, it generates from x a
new search point y by copying x into y and flipping each bit independently with
probability n1 . If the new search point (“offspring”) y is at least as good as the
parent x, that is, if f (y) ≥ f (x) for an objective function to be maximized, then
x is replaced by y, that is, we set x := y. Otherwise, y is discarded.
Algorithm 1: The (1 + 1) EA for maximizing f : {0, 1}n → R.
n
1 Choose x ∈ {0, 1} uniformly at random;
2 for t = 1, 2, 3, . . . do
3
y ← x;
4
for i ∈ [1..n] do
5
with probability n1 do yi ← 1 − yi;
6

if f (y) ≥ f (x) then x ← y;

The precise result of [OW11] is the following.
Theorem 13. For all η > 0 there are c1 , c2 > 0 such that with probability 1 − 2c1 n
the first 2c2 n search points generated in a run of the (1 + 1) EA on the needle
function all have a Hamming distance of more than ( 21 − η)n from the optimum.
10

The proof of this theorem in [OW11] argues as follows. Denote by x(0) , x(1) , . . .
the search points generated in a run of the (1 + 1) EA. Denote by x∗ the optimum
(i)
of the needle function. For all i ≥ 0, let Xi := H(x(i) , x∗ ) := |{j ∈ [1..n] | xj 6=
x∗j }| be the Hamming distance of x(i) from the optimum. The random initial
search point x(0) has an expected Hamming distance of n2 from the optimum. By
a simple Chernoff bound argument (Theorem 53), we see that with probability
1 − exp(−2η 2 n), we have X0 = H(x(0) , x∗ ) > ( 21 − η)n. Now a careful analysis of
the random process (Xi )i≥0 via a new “simplified drift theorem” gives the claim.
We now show that the Chernoff bound argument plus a simple union bound are
sufficient to prove the theorem. We show the following more explicit bound, which
also applies to all other unbiased algorithms in the sense of Lehre and Witt [LW12]
(roughly speaking, all algorithms which treat the bit-positions [1..n] in a symmetric
fashion as well as the bit-values {0, 1}).
Theorem 14. For all η > 0 and c > 0 we have that with probability at least
2
1−2(c−2 ln(2)η )n the first L := 2cn search points generated in a run of the (1+1) EA
(or any other unbiased black-box optimization algorithm) on the needle function
all have a Hamming distance of more than ( 12 − η)n from the optimum.
Proof. The key observation is that as long as the (1 + 1) EA has not found the
optimum, any search point x generated by the (1 + 1) EA is uniformly distributed
in {0, 1}n . Hence Pr[H(x, x∗ ) ≤ ( 21 − η)n] ≤ exp(−2η 2 n) by Theorem 53. By
the union bound, the probability that one of the first L := 2cn search points
generated by the (1 + 1) EA has a distance H(x, x∗ ) of at most ( 12 − η)n, is at
2
most L exp(−2η 2 n) = 2(c−2 ln(2)η )n .
To be more formal, let x(0) , x(1) , . . . be the search points generated in a run of
the (1 + 1) EA. Let T = min{t ∈ N0 | x(t) = x∗ }. Define a sequence y (0) , y (1) , . . .
of search points by setting y (t) := x(t) for all t ≤ T . For all t > T , let y (t) be
obtained from y (t−1) by flipping each bit independently with probability n1 . With
this definition, and since x(t) = x∗ for all t ≥ T , we have
{x(t) | t ∈ [0..L − 1]} = {x(t) | t ∈ [0.. min{T, L − 1}]}

= {y (t) | t ∈ [0.. min{T, L − 1}]} ⊆ {y (t) | t ∈ [0..L − 1]}.

Consequently,
Pr[∃t ∈ [0..L−1] : H(x(t) , x∗ ) ≤ ( 12 −η)n] ≤ Pr[∃t ∈ [0..L−1] : H(y (t) , x∗ ) ≤ ( 12 −η)n].
By the union bound,
Pr[∃t ∈ [0..L − 1] : H(y (t) , x∗ ) ≤ ( 12 − η)n] ≤
11

L−1
X
t=0

Pr[H(y (t), x∗ ) ≤ ( 21 − η)n].

Note that when y (t) is a search point uniformly distributed in {0, 1}n , then so is
y (t+1) . Since y (0) is uniformly distributed, all y (t) are. Hence by Theorem 53 we
have Pr[H(y (t) , x∗ ) ≤ ( 12 − η)n] ≤ exp(−2η 2 n) for all t and thus
L−1
X
t=0

Pr[H(y (t) , x∗ ) ≤ ( 21 − η)n] ≤ L exp(−2η 2 n) = 2(c−2 ln(2)η

2 )n

.

This proof immediately extends to all algorithms which, when optimizing the
needle function, generate uniformly distributed search points until the optimum is
found. These are, in particular, all unbiased algorithms in the sense of Lehre and
Witt [LW12].
Note that the yt in the proof above are heavily correlated. For all t, the
search points yt and yt+1 have an expected Hamming distance of exactly one.
Nevertheless, we could apply the union bound to the events “H(yt , x∗ ) < ( 21 − η)n”
and from this obtain a very elementary proof of Theorem 14.

5.2

Lower Bounds, Bonferroni Inequalities

The union bound is tight, that is, holds with equality, when the events Ei are
disjoint. In this case, the union bound simply reverts to the σ-additivity of the
probability measure. The second Bonferroni inequality gives a lower bound for the
probability of a union of events also when they are not disjoint.
Lemma 15. Let E1 , . . . , En be arbitrary events in some probability space. Then
Pr

"

n
[

i=1

#

Ei ≥

n
X
i=1

Pr[Ei ] −

n−1
X

n
X

i=1 j=i+1

Pr[Ei ∩ Ej ].

As an illustration, let us regard the performance of blind random search on
the needle function, that is, we let x(1) , x(2) , . . . be independent random search
points from {0, 1}n and ask ourselves what is the first hitting time T = min{t ∈
N | x(t) = (1, . . . , 1)} of the maximum x∗ = (1, . . . , 1) of the needle function (any
other function f : {0, 1}n → R with unique global optimum would do as well).
This is easy to compute directly. We see that T has geometric distribution with
success probability 2−n , so the probability that L iterations do not suffice to find
the optimum is Pr[T > L] = (1 − 2−n )L .
Let us nevertheless see what we can derive from union bound and second Bonferroni inequality. Let Et be the event x(t) = x∗ . Then the union bound gives
Pr[T ≤ L] = Pr

"

L
[

t=1

12

#

Et ≤ L2−n ,

the second Bonferroni inequality yields
Pr[T ≤ L] = Pr

"

L
[

t=1

#

Et ≥ L2−n −

L(L − 1) −2n
2 .
2

Hence if L = o(2n ), that is, L is of smaller asymptotic order than 2n , then Pr[T ≤
L] = (1 − o(1))L2−n , that is, the union bound estimate is asymptotically tight.
For reasons of completeness, we state the full set of Bonferroni inequalities.
Note that the case k = 1 is the union bound and the case k = 2 is the lemma
above.
Lemma 16. Let E1 , . . . , En be arbitrary events in some probability space. For all
k ∈ [1..n], let
X
Sk :=
Pr[Ai1 ∩ · · · ∩ Aik ].
1≤i1 <···<ik ≤n

Then for all k ∈ [1..n] we have
• Pr

"

• Pr

"

n
[

Ei ≤

n
[

#

i=1

i=1

#

Ei ≥

k
X

(−1)j−1 Sj for k ∈ [1..n] odd,

k
X

(−1)j−1 Sj for k ∈ [1..n] even.

j=1

j=1

In simple terms, the Bonferroni inequalities state that when we omit the terms
for j > k in the inclusion-exclusion formula
Pr

"

n
[

i=1

#

Ei =

n
X

(−1)j−1 Sj ,

j=1

then first of the omitted terms (that is, the one for j = k + 1) dominates the error.
So if k is odd and thus the first omitted term is negative, then we obtain a ≤
inequality, and inversely for k even.
We now use the Bonferroni inequalities to prove two of the inequalities given
in the previous section.
Proof of Lemma 6 (b). Consider some probability space with independent events
E1 , . . . , En having Pr[Ei ] = pi . Due to the independence,
n
Y

(1 − pi ) = Pr[∀i ∈ [1..n] : ¬Ei ] = 1 − Pr[∃i ∈ [1..n] : Ei ].

i=1

13

(14)

By the union bound, the right-hand side of (14) is at least 1 − ni=1 pi = 1 − P . By
the Bonferroni inequality for k = 2 and again the independence, the right-hand
side of (14) is at most
P

1−P +

X
i<j

Pr[Ei ∩ Ej ] = 1 − P +

X
i<j

pi pj ≤ 1 − P +

1
2

n X
n
X

i=1 j=1

pi pj = 1 − P + 21 P 2.

Note that the slack in the last inequality is only the term ni=1 p2i , so there is
P
not much reason to prefer the stronger upper bound 1 − P + i<j pi pj over the
bound 1 − P + 12 P 2 .
P

6
6.1

Expectations,
Markov’s
Chebyshev’s Inequality

Inequality,

and

Expectation

The expectation (or mean) of a random variable X taking values in some set Ω ⊆ R
P
is defined by E[X] = ω∈Ω ω Pr[X = ω], where we shall always assume that the
sum exists and is finite. As a trivial example, we immediately see that if X is a
binary random variable, then E[X] = Pr[X = 1].
For non-negative integral random variables, the expectation can also be computed by the following formula (which is valid also when E[X] is not finite).
Lemma 17. Let X be a random variable taking values in the non-negative integers.
Then
∞
E[X] =

X
i=1

Pr[X ≥ i].

This lemma, among others, allows to conveniently transform information about
the tail bound of a distribution into a bound on its expectation. This was done,
e.g., in [DJW02, proof of Lemma 10] for lower bounds and in [DG13] in the simplified proof of the multiplicative drift theorem (which is an upper bound on an
expectation). For exponential tails, we easily obtain the following general result.
Corollary 18 (Expectations from exponential tail bounds). Let α, β > 0 and
T ≥ 0. Let X be an integer random variable and Y be a non-negative integer
random variable.
(a) If Pr[X ≥ T + λ] ≤ α exp(− βλ ) for all λ ∈ N, then E[X] ≤ T + αβ.
(b) If Pr[Y ≤ T − λ] ≤ α exp(− βλ ) for all λ ∈ [1..T ], then E[Y ] ≥ T − αβ.
14

(c) If Pr[X ≥ (1 + ε)T ] ≤ α exp(− βε ) for all ε > 0, then E[X] ≤ (1 + αβ)T .
(d) If Pr[X ≤ (1 − ε)T ] ≤ α exp(− βε ) for all ε ∈ (0, 1], then E[X] ≥ (1 − αβ)T .
∞
i−T
Proof. We compute E[X] ≤ ∞
i=1 Pr[X ≥ i] ≤ T +
i=T +1 α exp(− β ) = T − α +
1
≤ T + αβ, where the last estimate uses Lemma 2.
α 1−exp(−1/β)
P
P
Similarly, we compute E[Y ] ≥ Ti=1 Pr[Y ≥ i] ≥ Ti=1 (1 − Pr[Y ≤ i − 1]) ≥
P∞
PT
λ
λ
λ=1 α exp(− β ) ≥ T − αβ.
λ=1 (1 − α exp(− β )) ≥ T −
The last two claims are simple reformulations of the first two.

P

P

In a similar vein, Lemma 17 yields an elegant analysis of the expectation of a
geometric random variable. Let X be a geometric random variable with success
probability p. Intuitively, we feel that the expected waiting time for a success
is 1p . This intuition is guided by the fact that after 1p repetitions of the underlying
binary random experiment, the expected number of successes is exactly one. This
intuition led to the right result, the “proof” however is not correct. The correct
proof either uses standard results in Markov chain theory, or elementary but nontrivial calculations, or (as done below) the above lemma.
Lemma 19 (Waiting time argument). Let X be a geometric random variable with
success probability p > 0. Then E[X] = p1 .
Proof. We have Pr[X ≥ i] = (1 − p)i−1 , since X ≥ i is the event of having no
success in the first i − 1 rounds of the random experiment. Now Lemma 17 gives
E[X] =

∞
X
i=1

Pr[X ≥ i] =

∞
X
i=1

(1 − p)i−1 =

1
1
= .
1 − (1 − p)
p

An elementary, but very useful property is that expectation is linear.
Lemma 20 (Linearity of expectation). Let X1 , . . . , Xn be arbitrary random variables and a1 , . . . , an ∈ R. Then
E

"

n
X
i=1

#

ai Xi =

n
X

ai E[Xi].

i=1

This fact is very convenient when we can write a complicated random variable
as sum of simpler ones. For example, let X be a binomial
random variable with

n k
parameters n and p, that is, we have Pr[X = k] = k p (1 −p)n−k . Since X counts
P
the number of successes in n (independent) trials, we can write X = ni=1 Xi as
the sum of (independent) binary random variables X1 , . . . , Xn , each with Pr[Xi =
15

1] = p. Here Xi is the indicator random variable for the event that the i-th trial
is a success. Using linearity of expectation, we compute
E[X] = E

"

n
X
i=1

#

Xi =

n
X

E[Xi ] = np.

i=1

Note that we did not need that the Xi are independent.
We just proved the following.
Lemma 21 (Expectation of binomial random variables). Let X be a binomial
random variable with parameters n and p. Then E[X] = pn.
In the same fashion, we can compute the following elementary facts.
Lemma 22. Let x, y, x∗ ∈ {0, 1}n . Denote by H(x, y) := |{i ∈ [1..n] | xi 6= yi }|
the Hamming distance of x and y.
(a) Let z be obtained from x via standard-bit mutation with rate p ∈ [0, 1],
that is, by flipping each bit of x independently with probability p. Then
E[H(x, z)] = pn and E[H(z, x∗ )] = H(x, x∗ ) + 2p( n2 − H(x, x∗ )).
(b) Let z be obtained from x and y via uniform crossover, that is, for each
i ∈ [1..n] independently, we have Pr[zi = xi ] = 21 = Pr[zi = yi ]. Then
E[H(x, z)] = 12 H(x, y) and E[H(z, x∗ )] = 12 (H(x, x∗ ) + H(y, x∗)).
(c) Let z be obtained from the unordered pair {x, y} via 1-point crossover, that
is, we choose r uniformly at random from [0..n] and then with probability 21
each
• define z by zi = xi for i ≤ r and zi = yi for i > r, or

• define z by zi = yi for i ≤ r and zi = xi for i > r.

Then E[H(x, z)] = 12 H(x, y) and E[H(z, x∗ )] = 12 (H(x, x∗ ) + H(y, x∗)).
The fact that the results for the two crossover operators are identical shows
again that linearity of expectation does not care about possible dependencies. We
have Pr[zi = xi ] = 12 in both cases, and this is what is important for the result,
whereas the fact that the events “zi = xi ” are independent for uniform crossover
and strongly dependent for 1-point crossover has no influence on the results.

16

6.2

Markov’s Inequality

Markov’s inequality is an elementary large deviation bound valid for all nonnegative random variables.
Lemma 23 (Markov’s inequality). Let X be a non-negative random variable.
Then for all λ > 0,
Pr[X ≥ λE[X]] ≤ λ1 ,

Pr[X ≥ λ] ≤
Proof. We have E[X] =

X
ω

ω Pr[X = ω] ≥

E[X]
.
λ

X

ω≥λ

(15)
(16)

λ Pr[X = ω] = λ Pr[X ≥ λ].

It is important to note that Markov’s inequality, without further assumptions,
only gives information about deviations above the expectation. If X is a (not
necessarily non-negative) random variable taking only values not larger than some
u ∈ R, then the random variable u − X is non-negative and Markov’s inequality
gives the bound
u − E[X]
Pr[X ≤ λ] ≤
,
u−λ
which is sometimes called reverse Markov’s inequality. An equivalent formulation
of this bound is
E[X] − λ
.
Pr[X > λ] ≥
u−λ
Markov’s inequality is useful if not much information is available about the
random variable under consideration. Also, when the expectation of X is very
small, then the following elementary corollary is convenient and, in fact, often
quite tight.
Corollary 24 (First moment method). If X is a non-negative random variable,
then Pr[X ≥ 1] ≤ E[X].
Corollary 24 together with linearity of expectation often gives the same results
as the union bound. For an example, recall that in Section 5.2 we observed that
in a run of the randomized search heuristic, the probability that the t-th search
point xt is the unique optimum of a given function f : {0, 1}n → R, is 2−n .
Denote this event by Et and let Xt be the indicator random variable for this event.
Then the probability that one of the first L search points is the optimum, can be
estimated equally well via the union bound or the above corollary and linearity of

17

expectation:

6.3

Pr

"

Pr

"

L
[

t=1
L
X
t=1

#

Et ≤

L
X

Pr[Et ] = L2−n ,

t=1

#

Xt ≥ 1 ≤ E

"

L
X

#

Xt =

t=1

L
X

E[Xt ] = L2−n .

t=1

Chebyshev’s Inequality

The second elementary large deviation bound is Chebyshev’s inequality, sometimes
called Bienaymé-Chebyshev inequality as it was first stated in Bienaymé [Bie53]
and later proven in Chebyshev [Tch67]. It seems rarely used in the theory of
randomized search heuristics (exceptions being [NSW10, DJWZ13]).
Recall that the variance of a discrete random variable X is
Var[X] = E[(X − E[X])2 ] = E[X 2 ] − E[X]2 .
Just by definition, the variance already is a measure of how well X is concentrated
around its mean. Applying Markov’s inequality to the random variable (X −
E[X])2 easily yields the following inequality.
Lemma 25 (Chebyshev’s inequality). For all λ > 0,
q

h

i

Pr |X − E[X]| ≥ λ Var[X] ≤
h

i

Pr |X − E[X]| ≥ λ ≤

1
,
λ2

Var[X]
.
λ2

(17)
(18)

Note that Chebyshev’s inequality automatically yields a two-sided tail bound
(that is, for both cases that the random variable is larger and smaller than its
expectation), as opposed to Markov’s inequality (giving just a bound for exceeding
the expectation). There is a one-sided version of Chebyshev’s inequality that is
often attributed to Cantelli, though Hoeffding [Hoe63] sees Chebyshev [Tch74] as
its inventor.
Lemma 26 (Cantelli’s inequality). For all λ > 0,
h

q

i

Pr X ≥ E[X] + λ Var[X] ≤

1
,
λ2 +1

(19)

Pr X ≤ E[X] − λ Var[X] ≤

1
.
λ2 +1

(20)

h

q

i

In most applications, the slightly better bound of Cantelli’s inequality is not
very interesting. Cantelli’s inequality, however, has the charm that the right-hand
side is always less than one.
18

While Markov’s inequality can be used to show that a non-negative random variable X rarely is positive (first moment method), Chebyshev’s inequality can serve the opposite purpose, namely showing that X is positive with
good probability. By taking λ = E[X] in (18), we obtain the first estimate
of the following lemma. Using the Cauchy-Schwarz inequality and computing
E[X]2 = E[X1X6=0 ]2 ≤ E[X 2 ]E[1X6=0 ] = E[X 2 ] Pr[X 6= 0], we obtain the second
2
. Since
estimate, which has the nice equivalent formulation Pr[X 6= 0] ≥ E[X]
E[X 2 ]
2
2
E[X ] ≥ E[X] , the second estimate gives a stronger bound for Pr[X = 0] than
the first. While the lemma below does not require that X is non-negative, the
typical application of showing that X is positive requires that X is non-negative
in the second bound, so that Pr[X 6= 0] = Pr[X > 0].
Lemma 27 (Second moment method). For a random variable X with E[X] 6= 0,
Pr[X = 0] ≤ Pr[X ≤ 0] ≤
Pr[X = 0] ≤

Var[X]
,
E[X]2

(21)

Var[X]
.
E[X 2 ]

(22)

In the (purely academic) example of finding a unique global optimum via blind
random search (see Section 5.2), let Xt be indicator random variable for the event
P
that the t-th search point is the optimum. Let X = Lt=1 Xt . Then the probability
that the optimum is found within the first L iterations is
Pr[X > 0] = 1 − Pr[X = 0] ≥ 1 −

Var[X]
.
E[X]2

The variance for a sum of binary random variables is
Var[X] =

L
X
t=1

Var[Xt ] +

X
s<t

Cov[Xs , Xt ] ≤ E[X] +

X

Cov[Xs , Xt ],

s<t

where we recall the definition of the covariance Cov[U, V ] := E[UV ] − E[U]E[V ]
of two arbitrary random variables U and V . Here we have Cov[Xs , Xt ] = 0, since
the Xt are independent. Consequently,
Pr[X > 0] ≥ 1 −

1
.
E[X]

Hence the probability to find the optimum within L iterations is Pr[T ≤ L] =
Pr[X > 0] ≥ 1 − L21−n . Note that this estimate is, for interesting case that E[X]
2−2n which we
is large, much better than the bound Pr[T ≤ L] ≥ L2−n − L(L−1)
2
obtained from the second Bonferroni inequality.
19

7

Conditioning

In the analysis of randomized heuristics, we often want to argue that a certain
desired event C already holds and the continue arguing under this condition. Formally, this gives rise to a new probability space where each of the original events
A now has a probability of
Pr[A | C] :=

Pr[A ∩ C]
.
Pr[C]

Obviously, this only makes sense for events C with Pr[C] > 0. In an analogous
fashion, we define the expectation of a random variable X conditional on C by
P
E[X | C] = ω∈C X(ω) Pr[ω | C]. Conditioning as a proof technique has many
faces, among them the following.
Decomposing events: If we can write some event A as the intersection of two
events A1 and A2 , then it can be useful to first compute the probability of A1 and
then the probability of A2 conditional on A1 . Right from the definition, we have
Pr[A1 ∩ A2 ] = Pr[A1 ] Pr[A2 | A1 ]. Of course, this requires that we have some direct
way of computing Pr[A1 | A2 ].
Case distinctions: Let C1 , . . . , Ck be a partition of our probability space. If it
is easy to analyse our problem conditional on each of these events (“in the that case
Ci holds”), then the following law of total probability and law of total expectation
are useful.
Lemma 28 (Laws of total probability and total expectation). Let C1 , . . . , Ck be
a partition of our probability space. Let A be some event and X be some random
variable. Then
Pr[A] =
E[X] =

k
X

i=1
k
X
i=1

Pr[A | Ci ] Pr[Ci],
E[X | Ci ] Pr[Ci ].

Excluding rare events: Quite often in the analysis of nature-inspired search
heuristics, we would like to exclude some rare unwanted event. For example,
assume that we analyze an evolutionary algorithm using standard-bit mutation
with mutation rate n1 . Then it is very unlikely that in an application of this
mutation operator more than n1/4 bits are flipped. So it could be convenient to
1/4
exclude this rare event, say by stating that “with probability 1 − 2−Ω(n ) , in none
20

of the first n2 applications of the mutation operator more than n1/4 bits are flipped;
let us in the following condition on this event”. See the proofs of Theorem 7 and 8
in [DJW02] for examples where such an argument is useful.
What could be a problem with this approach is that as soon as we condition
on such an event, we change the probability space and thus arguments valid in
the unconditional setting are not valid anymore. As a simple example, note that
once we condition on that we flip at most n1/4 bits, the events Ei that the i-th
bit flips are not independent anymore. Fortunately, we can safely ignore this in
most cases (and many authors do so without saying a word on this affair). The
reason is that when conditioning on an almost sure event, then the probabilities
of all events change only very little (see the lemma below for this statement made
precise). Hence in our example, we can compute the probability of some event
assuming that the bit flips are independent and then correct this probability by a
minor amount.
Lemma 29. Let C be some event with probability 1 − p. Let A be any event. Then
Pr[A]
Pr[A] − p
≤ Pr[A | C] ≤
.
1−p
1−p
In particular, for p ≤ 21 , we have Pr[A] − p ≤ Pr[A | C] ≤ Pr[A] + 2p.
The proof of this lemma follows right from the definition of conditional probabilities and the elementary estimate Pr[A] − p ≤ Pr[A \ C] = Pr[A ∩ C] ≤ Pr[A],
where C denotes the complement of C. From this, we also observe the natural fact
that when A ⊆ C, that is, the event A implies C, then conditioning on C rather
increases the probability of A:
Pr[A ∩ C]
Pr[A]
=
≥ Pr[A].
Pr[C]
Pr[C]

(23)

Pr[A] − p
Pr[A \ C]
=
≤ Pr[A].
Pr[C]
1−p

(24)

Pr[A | C] =
Likewise, when A ⊇ C, then
Pr[A | C] =

For example, if X is the number of bits flipped in an application of standard-bit
mutation, then Pr[X ≤ 10 | X ≤ n2 ] ≥ Pr[X ≥ 10] and Pr[X ≥ 10 | X ≤ n2 ] ≤
Pr[X ≥ 10].
Conditional binomial random variables: We occasionally need to know the
expected value of a binomially distributed random variable X ∼ Bin(n, p) conditional on that the variable has at least a certain value k. An intuitive (but wrong)
21

argument is that E[X | X ≥ k] should be around k + p(n − k), because we know
already that k of the n independent trials are successes and the remaining (n − k)
trials still have their independent success probability of p. While this argument
is wrong (as we might need more than k trials to have k successes), the result is
correct as an upper bound as shown in this lemma from [DD17].
Lemma 30. Let X be a random variable with binomial distribution with parameters n and p ∈ [0, 1]. Let k ∈ [0..n]. Then
E[X | X ≥ k] ≤ k + (n − k)p ≤ k + E[X].

Pn

Proof. Let X = i=1 Xi with X1 , . . . , Xn being independent binary random variables with Pr[Xi = 1] = p for all i ∈ [1..n]. Conditioning on X ≥ k, let
P
ℓ := min{i ∈ [1..n] | ij=1 Xj = k}. Then
E[X | X ≥ k] =

n
X
i=1

Pr[ℓ = i | X ≥ k]E[X | ℓ = i].

Note that ℓ ≥ k by definition. Note also that (X | ℓ = i) = k + nj=i+1 Xj with
unconditioned Xj . In particular, E[X | ℓ = i] = k + (n − i)p. Consequently,
P

E[X | X ≥ k] =
≤

n
X

i=1
n
X
i=k

Pr[ℓ = i | X ≥ k]E[X | ℓ = i]
Pr[ℓ = i | X ≥ k](k + (n − k)p) = k + (n − k)p.

We note that, in the language introduced in the following section, we have
actually shown the stronger statement that (X | X ≥ k) is dominated by k +
Bin(n − k, p). This stronger version can be useful to obtain tail bounds for (X |
X ≥ k).

8

Stochastic Domination and Coupling

In this section, we discuss two concepts that are not too often used explicitly, but
where we feel that mastering them can greatly help in the analysis of randomized
search heuristics. The first of these is stochastic domination, which is a very strong
way of saying that one random variable is better than another even when they are
not defined on the same probability space. The second concept is coupling, which
means defining two random variables suitably over the same probability space to
facilitate comparing them. These two concepts are strongly related: If the random
variable Y dominates X, then X and Y can be coupled in a way that Y is pointwise not smaller than X, and vice versa. The results of this section and some
related ones have appeared in [Doe18], however, in a more condensed form.
22

8.1

The Notion of Stochastic Domination

Definition 31 (Stochastic domination). Let X and Y be two random variables
not necessarily defined on the same probability space. We say that Y stochastically
dominates X, written as X  Y , if for all λ ∈ R we have Pr[X ≤ λ] ≥ Pr[Y ≤ λ].
If Y dominates X, then the cumulative distribution function of Y is point-wise
not larger than the one of X. The definition of domination is equivalent to
∀λ ∈ R : Pr[X ≥ λ] ≤ Pr[Y ≥ λ],
which is maybe a formulation making it more visible why we feel that Y is at least
as large as X.
Concerning nomenclature, we remark that some research communities in addition require that the inequality is strict for at least one value of λ. Hence,
intuitively speaking, Y is strictly larger than X. From the mathematical perspective, this appears not very practical. Consequently, our definition above is
more common in computer science. We also note that stochastic domination is
sometimes called first-order stochastic domination. For an extensive treatment of
various forms of stochastic orders, we refer to [MS02].
The usual way of explaining stochastic domination is via games. Let us
consider the following three games.
Game A: With probability 12 , each you win 500 and 1500.
Game B: With probability 31 , you win 500, with probability 61 , you win 800, and
with probability 12 , you win 1500.
1
Game C: With probability 1000
, you win 2,000,000. Otherwise, you win nothing.
Which of these games is best to play? It is intuitively clear that you prefer
Game B over Game A. However, it is not clear whether you should prefer Game C
over Game B. Clearly, the expected win in Game C is 2000 compared to only 1050
in Game B. However, the chance of winning something at all is really small in
Game C. If you do not like to go home empty-handed, you might prefer Game B.
The mathematical take on these games is that the random variable XB describing the win in Game B stochastically dominates the one XA for Game A.
This captures our intuitive feeling that it cannot be wrong to prefer Game B over
Game A. For Games B and C, neither of XB and XC dominates the other. Consequently, it depends on the precise utility function of the player which game he
prefers. This statement is made precise in the following lemma.
Lemma 32. The following two conditions are equivalent.
(a) X  Y .
23

(b) For all monotonically non-decreasing functions f : R → R, we have
E[f (X)] ≤ E[f (Y )].
As a simple corollary we note the following.
Corollary 33. If X  Y , then E[X] ≤ E[Y ].
We note another simple, but useful property.
Lemma 34. Let X1 , . . . , Xn be independent random variables defined over some
common probability space. Let Y1 , . . . , Yn be independent random variables defined
over a possibly different probability space. If Xi  Yi for all i ∈ [1..n], then
n
X
i=1

Xi 

n
X

Yi .

i=1

For discrete random variables, this result is a special case of Lemma 38 stated
further below.
Finally, we note two trivial facts.
Lemma 35. Let X and Y be random variables.
(a) If X and Y are defined on the same probability space and X ≤ Y , then
X  Y.
(b) If X and Y are identically distributed, then X  Y .

8.2

Stochastic Domination in Runtime Analysis

From the perspective of algorithms analysis, stochastic domination allows to very
clearly state that one algorithm is better than another. If the runtime distribution
XA of algorithms A dominates the one XB of Algorithm B, then from the runtime
perspective Algorithm B is always preferable to Algorithm A.
In a similar vein, we can use domination also to give more detailed descriptions
of the runtime of an algorithm. For almost all algorithms, we will not be able to
precisely determine the runtime distribution. However, via stochastic domination
we can give a lot of useful information beyond, say, just the expectation. We
demonstrate this via an extension of the classic fitness level method, which is
implicit in Zhou, Luo, Lu, and Han [ZLLH12].
Theorem 36 (Domination version of the fitness level method). Consider an iterative randomized search heuristic A maximizing a function f : Ω → R. Let
A1 , . . . , Am be a partition of Ω such that for all i, j ∈ [1..m] with i < j and all
24

x ∈ Ai , y ∈ Aj , we have f (x) < f (y). Set A≥i := Ai ∪ · · · ∪ Am . Let p1 , . . . , pm−1
be such that for all i ∈ [1..m − 1] we have that if the best-so-far search point is
in Ai , then regardless of the past A has a probability of at least pi to generate a
search point in A≥i+1 in the next iteration.
Denote by T the (random) number of iterations A takes to generate a search
point in Am . Then
T 

m−1
X

Geom(pi ),

i=1

where this sum is to be understood as a sum of independent geometric distributions.
To prove this theorem, we need a technical lemma which we defer to the subsequent subsection to ease reading this part.
Proof. Consider a run of the algorithm A. For all i ∈ [1..m], let Ti be the first
time (iteration) when A has generated a search point in A≥i . Then T = Tm =
Pm−1
i=1 (Ti+1 − Ti ). By assumption, Ti+1 − Ti is dominated by a geometric random
variable with parameter pi regardless what happened before time Ti . Consequently,
Lemma 38 gives the claim.
Note that a result like Theorem 36 implies various statements on the runtime.
P
1
By Corollary 33, the expected runtime satisfies E[T ] ≤ m−1
i=1 pi , which is the common version of the fitness level theorem [Weg01]. By using tail bounds for sums
of independent geometric random variables (see Section 10.4), we also obtain runtime bounds that hold with high probability. This was first proposed in [ZLLH12].
We defer a list of examples where previous results can profitably be turned into a
domination statement to Section 10.4, where we will also have the large deviation
bounds to exploit such statements.

8.3

Domination by Independent Random Variables

A situation often encountered in the analysis of algorithms is that a sequence of
random variables is not independent, but that each member of the sequence has a
good chance of having a desired property no matter what was the outcome of its
predecessors. In this case, the random variables in some sense can be treated as if
they were independent.
Lemma 37. Let X1 , . . . , Xn be arbitrary binary random variables and let
X1∗ , . . . , Xn∗ be independent binary random variables.
(a) If we have
Pr[Xi = 1 | X1 = x1 , . . . , Xi−1 = xi−1 ] ≤ Pr[Xi∗ = 1]
25

for all i ∈ [1..n] and all x1 , . . . , xi−1 ∈ {0, 1} with Pr[X1 = x1 , . . . , Xi−1 =
xi−1 ] > 0, then
n
X
i=1

Xi 

n
X

Xi∗ .

i=1

(b) If we have
Pr[Xi = 1 | X1 = x1 , . . . , Xi−1 = xi−1 ] ≥ Pr[Xi∗ = 1]
for all i ∈ [1..n] and all x1 , . . . , xi−1 ∈ {0, 1} with Pr[X1 = x1 , . . . , Xi−1 =
xi−1 ] > 0, then
n
X
i=1

Xi∗ 

n
X

Xi .

i=1

Note that here and in the following, we view “X1 = x1 , . . . , Xi−1 = xi−1 ” for
i = 1 as an empty intersection of events, that is, an intersection over an empty
index set. As most textbooks, we define this to be the whole probability space.
Both parts of the lemma are simple corollaries from the following, slightly
technical, general result, which might be of independent interest.
For two sequences (X1 , . . . , Xn ) and (X1∗ , . . . , Xn∗ ) of random variables, we say
that (X1∗ , . . . , Xn∗ ) unconditionally sequentially dominates (X1 , . . . , Xn ) if for all
i ∈ [1..n] and all x1 , . . . , xi−1 ∈ R with Pr[X1 = x1 , . . . , Xi−1 = xi−1 ] > 0, we have
(Xi | X1 = x1 , . . . , Xi−1 = xi−1 )  Xi∗ . Analogously, we speak of unconditional
sequential subdomination if the last condition is replaced by Xi∗  (Xi | X1 =
x1 , . . . , Xi−1 = xi−1 ).
The following lemma shows that unconditional sequential (sub-)domination
and independence of the Xi∗ imply (sub-)domination for the sums of these random
variables. Note that unconditional sequential (sub-)domination is inherited by
subsequences, so the following lemma immediately extends to sums over arbitrary
subsets I of the index set [1..n].
Lemma 38. Let X1 , . . . , Xn be arbitrary discrete random variables.
X1∗ , . . . , Xn∗ be independent discrete random variables.

Let

(a) If (X1∗ , . . . , Xn∗ ) unconditionally sequentially dominates (X1 , . . . , Xn ), then
Pn
Pn
∗
i=1 Xi 
i=1 Xi .

(b) If (X1∗ , . . . , Xn∗ ) unconditionally sequentially subdominates (X1 , . . . , Xn ),
P
P
then ni=1 Xi∗  ni=1 Xi .

Proof. The two parts of the lemma imply each other (as seen by multiplying the
random variables with −1), so it suffices to prove the first statement.
26

Since the statement of the theorem is independent of the correlation between
the Xi and the Xi∗ , we may assume that they are independent. Let λ ∈ R. Define
Pj := Pr

X
j

n
X

Xi +

i=j+1

i=1

Xi∗ ≥ λ



for j ∈ [0..n]. We show Pj+1 ≤ Pj for all j ∈ [0..n − 1].
For m ∈ R, let Ωm denote the set of all (x1 , . . . , xj , xj+2 , . . . , xn ) ∈ Rn−1 such
P
that Pr[X1 = x1 , . . . , Xj = xj ] > 0 and i∈[1..n]\{j+1} xi = λ − m. Let M := {m ∈
R | Ωm 6= ∅}. Then
Pj+1 = Pr

 j+1
X

n
X

Xi∗ ≥ λ

Xi +

Xi∗

Xi +

i=j+2

i=1

=

X

Pr

i=1

m∈M

=

X
j

n
X



i=j+2

X

X

m∈M (x1 ,...,xj ,xj+2 ,...,xn )∈Ωm



= λ − m ∧ Xj+1 ≥ m



h

Pr X1 = x1 , . . . , Xj = xj ·

h

i

Pr Xj+1 ≥ m X1 = x1 , . . . , Xj = xj ·
≤

X

Pr

Xi +

X
j
i=1

Xi +

n
X

i=j+2

i=1

m∈M

= Pr

X
j

n
X

i=j+1

Xi∗



n
Y

h

Pr Xi∗ = xi

i=j+2

h

i

i

∗
Xi∗ = λ − m · Pr Xj+1
≥m

≥λ



= Pj .
Thus, we have
Pr

X
n
i=1

8.4



Xi ≥ λ = Pn ≤ Pn−1 ≤ · · · ≤ P1 ≤ P0 = Pr

X
n
i=1

Xi∗



≥λ .

Coupling

Coupling is an analysis technique that consists of defining two unrelated random
variables over the same probability space to ease comparing them. As an example,
let us regard standard-bit mutation with rate p and with rate q, where p < q.
Intuitively, it seem obvious that we flip more bits when using the higher rate q.
27

We could make this precise by looking at the distributions of the random variables
Xp and Xq describing the numbers of bits that flip and computing that Xp  Xq .
For that, we would need to show that for all k ∈ [0..n], we have
k
X
i=0

k
X
n i
n i
p (1 − p)n−i ≥
q (1 − q)n−i .
i
i
i=0

!

!

Coupling is a way to get the same result in a more natural manner.
Consider the following random experiment. For each i ∈ [1..n], let ri be a
random number chosen independently and uniformly distributed in [0, 1]. Let X̃p
be the number of ri that are less than p and let Xq be the number of ri that are less
than q. We immediately see that X̃p ∼ Bin(n, p) and X̃q ∼ Bin(n, q). However,
we know more. We defined X̃p and X̃q in a common probability space in a way
that we have X̃p ≤ X̃q with probability one: Xp and Xq , viewed as functions
on the (hidden) probability space Ω = {(r1 , . . . , rn ) | r1 , . . . , rn ∈ [0, 1]} satisfy
X̃p (ω) ≤ X̃q (ω) for all ω ∈ Ω. Consequently, by the trivial Lemma 35, we have
Xp  X̃p  X̃q  Xq and hence Xp  Xq .
The same argument works for geometric distributions. We summarize these
findings (and two more) in the following lemma. Part (b) follows from the obvious
embedding (which is a coupling as well) of the Bin(n, p) probability space into the
one of Bin(m, p). The first inequality of part (c) is easily computed right from the
definition of domination (and holds in fact for all random variables), the second
part was proved and used in [KW17].
Lemma 39. Let X and Y be two random variables. Let p, q ∈ [0, 1] with p ≤ q.
(a) If X ∼ Bin(n, p) and Y ∼ Bin(n, q), then X  Y .
(b) If n ≤ m, X ∼ Bin(n, p) and Y ∼ Bin(m, p), then X  Y .
(c) If X ∼ Bin(n, p) and x ∈ [0..n], then X  (X | X ≥ x)  (X + x).
(d) If p > 0, X ∼ Geom(p), and Y ∼ Geom(q), then X  Y .
Let us now formally define what we mean by coupling. Let X and Y be two
random variables not necessarily defined over the same probability space. We
say that (X̃, Ỹ ) is a coupling of (X, Y ) if X̃ and Ỹ are defined over a common
probability space and if X and X ′ as well as Y and Y ′ are identically distributed.
This definition itself is very weak. (X, Y ) have many couplings and most of
them are not interesting. So the art of coupling as a proof and analysis technique
is to find a coupling of (X, Y ) that allows to derive some useful information.
It is not a coincidence that we could use coupling to prove stochastic domination. The following theorem is well-known.
28

Theorem 40. Let X and Y be two random variables. Then the following two
statements are equivalent.
(a) X  Y .
(b) There is a coupling (X̃, Ỹ ) of (X, Y ) such that X̃ ≤ Ỹ .
We remark without further details that coupling as a proof technique found
numerous powerful applications beyond its connection to stochastic domination.

8.5

Domination in Fitness or Distance

So far we have used stochastic domination to compare runtime distributions. We
now show that stochastic domination is a very elegant proof tool also when applied
to other distributions. To do so, we give a short and elegant proof for the result of
Witt [Wit13] that compares the runtimes of mutation-based algorithms. The main
reason why our proof is significantly shorter than the one of Witt is that we use
the notion of stochastic domination also for the distance from the optimum. This
will also be an example where we heavily exploit the connection between coupling
and stochastic domination (Theorem 40).
To state this result, we need the notion of a (µ, p) mutation-based algorithm
introduced in [Sud13]. This class of algorithms is called only mutation-based
in [Sud13], but since (i) it does not include all adaptive algorithms using mutation only, e.g., those regarded in [JW06, OLN09, BDN10, BLS14, DGWY17],
(ii) it does not include all algorithms using a different mutation operator than
standard-bit mutation, e.g., those in [DDY16a, DDY16b, LOW17, DLMN17], and
(iii) this notion collides with the notion of unary unbiased black-box complexity algorithms (see [LW12]), which without greater justification could also be called the
class of mutation-based algorithms, we feel that a notion making these restrictions
precise is more appropriate.
The class of (µ, p) mutation-based algorithms comprises all algorithms which
first generate a set of µ search points uniformly and independently at random from
{0, 1}n and then repeat generating new search points from any of the previous ones
via standard-bit mutation with probability p. This class includes all (µ + λ) and
(µ, λ) EAs which only use standard-bit mutation with static mutation rate p.
Denote by (1 + 1) EAµ the following algorithm in this class. It first generates
µ random search points. From these, it selects uniformly at random one with
highest fitness and then continues from this search point as a (1 + 1) EA, that
is, repeatedly generates a new search point from the current one via standard-bit
mutation with rate p and replaces the previous one by the new one if the new one
is not worse (in terms of the fitness). This algorithm was called (1 + 1) EA with
BestOf(µ) initialization in [dPdLDD15].
29

For any algorithm A from the class of (µ, p) mutation-based algorithms and
any fitness function f : {0, 1}n → R, let us denote by T (A, f ) the runtime of the
algorithm A on the fitness function f , that is, the number of the first individual
generated that is an optimal solution. Usually, this will be µ plus the number
of the iteration in which the optimum was generated. To cover also the case
that one of the random initial individuals is optimal, let us assume that these
initial individuals are generated sequentially. As a final technicality, for reasons
of convenience, let us assume that the (1 + 1) EAµ in iteration µ + 1 does not
choose as parent a random one of the previous search points with maximal fitness,
but the last one with maximal fitness. Since the first µ individuals are generated
independently, this modification does not change the distribution of this parent.
In this language, Witt [Wit13] shows the following remarkable result.
Theorem 41. For any (µ, p) mutation-based algorithm A and any f : {0, 1}n → R
with unique global optimum,
T ((1 + 1) EAµ , OneMax)  T (A, f ).
This result significantly extends results of a similar flavor in [BE08, DJW12,
Sud13]. The importance of such types of results is that they allow to prove lower
bounds for the performance of many algorithm on essentially arbitrary fitness
functions by just regarding the performance of the (1 + 1) EAµ on OneMax.
Let us denote by |x|1 the number of ones in the bit string x ∈ {0, 1}n . In
other words, |x|1 = kxk1 , but the former is nicer to read. Then Witt [Wit13] has
shown the following natural domination relation between offspring generated via
standard-bit mutation.
Lemma 42. Let x, y ∈ {0, 1}n . Let p ∈ [0, 21 ]. Let x′ , y ′ be obtained from x, y via
standard-bit mutation with rate p. If |x|1 ≤ |y|1, then |x′ |1  |y ′|1 .
We are now ready to give our alternate proof for Theorem 41. While it is
clearly shorter that the original one in [Wit13], we also feel that it is more natural.
In very simple words, it shows that T (A, f ) dominates T ((1 + 1) EAµ , OneMax)
because the search points generated in the run of the (1 + 1) EAµ on OneMax
always are at least as close to the optimum (in the domination or coupling sense)
as the ones in the run of A on f .
Proof. Since A treats bit-positions and bit-values in a symmetric fashion, we may
without loss of generality assume that the unique optimum of f is (1, . . . , 1).
Let x(1) , x(2) , . . . be the sequence of search points generated in a run of A
on the fitness function f . Hence x(1) , . . . , x(µ) are independently and uniformly
distributed in {0, 1}n and all subsequent search points are generated from suitably
chosen previous ones via standard-bit mutation with rate p. Let y (1) , y (2) , . . . be
30

the sequence of search points generated in a run of the (1 + 1) EAµ on the fitness
function OneMax.
We show how to couple these random sequences of search points in a way that
(t)
|x̃ |1 ≤ |ỹ (t) |1 for all t ∈ N. We take as common probability space Ω simply the
space that (x(t) )t∈N is defined on and let x̃(t) = x(t) for all t ∈ N.
We define the ỹ (t) inductively as follows. For t ∈ [1..µ], let ỹ (t) = x(t) . Note
that this trivially implies |x̃(t) |1 ≤ |ỹ (t) |1 for these search points. Let t > µ and
′
′
assume that |x̃(t ) |1 ≤ |ỹ (t ) |1 for all t′ < t. Let s ∈ [1..t − 1] be maximal such that
ỹ (s) has maximal OneMax-fitness among ỹ (1) , . . . , ỹ (t−1) . Let r ∈ [1..t − 1] be such
that x(t) was generated from x(r) in the run of A on f . By induction, we have
|x(r) |1 ≤ |ỹ (r) |1 . By the choice of s we have |ỹ (r) |1 ≤ |ỹ (s) |1 . Consequently, we have
|x(r) |1 ≤ |ỹ (s)|1 . By Lemma 42 and Theorem 40, there is a random ỹ (t) (defined on
Ω) such that ỹ (t) has the distribution of being obtained from ỹ (s) via standard-bit
mutation with rate p and such that |x(t) |1 ≤ |ỹ (t) |1 .
With this construction, the sequence (ỹ (t) )t∈N has the same distribution as
(y (t) )t∈N . This is because the first µ elements are random and then each subsequent
one is generated via standard-bit mutation from the current-best one, which is just
the way the (1 + 1) EAµ is defined. At the same time, we have |x̃(t) |1 ≤ |ỹ (t) |1
for all t ∈ N. Consequently, we have min{t ∈ N | |ỹ (t) |1 = n} ≤ min{t ∈
N | |x(t) |1 = n}. Since T ((1 + 1) EAµ , OneMax) and min{t ∈ N | |ỹ (t) |1 = n} are
identically distributed and also T (A, f ) and min{t ∈ N | |x(t) |1 = n} are identically
distributed, we have T ((1 + 1) EAµ , OneMax)  T (A, f ).
While not explicitly using the notion of stochastic domination, the result and
proof in [BE08] bear some similarity to those above. In very simple words and
omitting many details, the result [BE08, Theorem1] states the following. Assume
that you run the (1 + 1) EA and some other algorithm A (from a relatively large
class of algorithms) to maximize a function f . Denote by x(t) and y (t) the best
individual produced by the (1 + 1) EA and A up to iteration t. Assume that
for all t and all possible runs of the algorithms up to iteration t we have that
f (x(t) ) ≥ f (y (t) ) implies f (x(t+1) )  f (y (t+1) ). Assume further that the random
initial individual of the (1 + 1) EA is at least as good (in terms of f ) as all initial
individuals of algorithm A. Then f (x(t) )  f (y (t) ) for all t.
The proof of this result (like the one of the fitness domination statement in
our proof of Theorem 41) uses induction over the time t. Since [BE08] do not use
the notion of stochastic domination explicitly, they cannot simply couple the two
processes, but have to compare the two distributions manually using an argument
they call Abel transform. While not fully exploiting the power of stochastic domination, [BE08] might be the first paper in the theory of evolutionary algorithms
to formulate results and proofs via stochastic domination.

31

9

The Coupon Collector Process

The coupon collector process is one of the central building blocks in the analysis of
randomized algorithms. It is particularly important in the theory of randomized
search heuristics, since the unorganized progress of these algorithms often leads to
situations very similar to the coupon collector process.
The coupon collector process is the following simple randomized process. Assume that there are n types of coupons available. Whenever you buy a certain
product, you get one coupon with a type chosen uniformly at random from the
n types. How long does it take until you have a coupon of each type? We denote,
in this section, the random variable describing the first round after which we have
all types by Tn and call it coupon collecting time. Hence in simple words, this is
the number of rounds it takes to obtain all types.
As an easy example showing the coupon collector problem arising in the theory
of randomized search heuristics, let us regard how the randomized local search
(RLS) heuristic optimizes strictly monotonically increasing functions. The RLS
heuristic when maximizing a given function f : {0, 1}n → R starts with a random
search point. Then, in each iteration of the process, a single random bit is flipped
in the current solution. If this gives a solution worse than the current one (in terms
of f ), then the new solution is discarded. Otherwise, the process is continued from
this new solution.
Assume that f is strictly monotonically increasing, that is, flipping any 0-bit
to 1 increases the function value. Then the optimization process of RLS on f
strongly resembles a coupon collector process. In each round, we flip a random
bit. If this bit was 1 in our current solution, then nothing changes (we discard
the new solution as it has a smaller f -value). If this bit was 0, then we keep the
new solution, which now has one extra 1. Hence taking the 1- bits as coupons, in
each round we obtain a random coupon. This has no effect if we had this coupon
already, but is good if not.
We observe that the optimization time (number of solutions evaluated until
the optimal solution is found) of RLS on strictly monotonic functions is exactly
the coupon collecting time when we start with an initial stake of coupons that
follows a Bin(n, 21 ) distribution. This shows that the optimization time is at most
the classic coupon collector time (where we start with no coupons). See [DD16]
for a very precise analysis of this process.
The expectation of the coupon collecting time is easy to determine. Recall
P
from Section 4.2 the definition of the harmonic number Hn := nk=1 k1 .
Theorem 43 (Coupon collector, expectation). The expected time to collect all n
coupons is E[Tn ] = nHn = (1 + o(1))n ln n.

32

Proof. Given that we already have k different coupons for some k ∈ [0..n − 1], the
. By
probability that the next coupon is one that we do not already have, is n−k
n
the waiting time argument (Lemma 19), we see that the time Tn,k needed to obtain
n
a new coupon given that we have exactly k different ones, satisfies E[Tn,k ] = n−k
.
Pn−1
Clearly, the total time Tn needed to obtain all coupons is k=0 Tn,k . Hence, by
Pn−1
linearity of expectation (Lemma 20), E[Tn ] = k=0
E[Tn,k ] = nHn .
We proceed by trying to gain more information on Tn than just the expectation.
The tools discussed so far (and one to come in a later section) lead to the following
results.
• Markov’s inequality (Lemma 23) gives Pr[Tn ≥ λnHn ] ≤

1
λ

for all λ ≥ 1.

• Chebyshev’s inequality (Lemma 25) can be used to prove Pr[|Tn − nHn | ≥
6
π2
This builds on the fact (implicit in
εn] ≤ 6ε
2 for all ε ≥ π 2 ≈ 0.6079.
the proof above) that the coupon collector time is the sum of independent
Pn−1
geometric random variables Tn = k=0
Geom( n−k
). Hence the variance is
n
π 2 n2
Var[Tn ] = 6 .
n−1
), Witt’s Chernoff bound for geomet• Again exploiting Tn = k=0
Geom( n−k
n
ric random variables (Theorem 78) gives

P

Pr[Tn ≥ E[Tn ] + εn] ≤


exp(− 3ε2 )
π2
exp(− ε )
4

if ε ≤
if ε >

π2
6
π2
6

2

Pr[Tn ≤ E[Tn ] − εn] ≤ exp(− 3ε
)
π2
for all ε ≥ 0. See [Wit14] for the details.

Interestingly, asymptotically much stronger bounds can be derived by fairly
elementary means. These are the basis for Theorem 79, hence for that reason we
did not mention this result in the list above. The key idea is to not regard how the
number of coupons increases over time, but instead to regard the event that we
miss a particular coupon for some period of time. Note that the probability that
a particular coupon is not obtained for t rounds is (1 − n1 )t . By a union bound
argument (see Lemma 12), the probability that there is a coupon not obtained
within t rounds, and equivalently, that Tn > t, satisfies
Pr[Tn > t] ≤ n(1 − n1 )t .
Using the simple estimate of Lemma 1, we obtain the following (equivalent)
bounds.

33

Theorem 44 (Coupon collector, upper tail). For all ε ≥ 0,
Pr[Tn ≥ (1 + ε)n ln n] ≤ n−ε ,
Pr[Tn ≥ n ln n + εn] ≤ exp(−ε).

(25)
(26)

Surprisingly, prior to the following result from [Doe11], no good lower bound
for the coupon collecting time was published.
Theorem 45 (Coupon collector, lower tail). For all ε ≥ 0,
Pr[Tn ≤ (1 − ε)(n − 1) ln n] ≤ exp(−nε ),
Pr[Tn ≤ (n − 1) ln n − ε(n − 1)] ≤ exp(−eε ).

(27)
(28)

Theorem 45 was proven in [Doe11] by showing that the events of having a
coupon after a certain time are 1-negatively correlated. The following proof defers
this work to Lemma 71.
Proof. Let t = (1 − ε)(n − 1) ln n. For i ∈ [1..n], let Xi be the indicator random
variable for the event that a coupon of type i is obtained within the first t rounds.
Then Pr[Xi = 1] = 1 − (1 − n1 )t ≤ 1 − exp(−(1 − ε) ln n) = 1 − n−1+ε , where the
estimate follows from Corollary 4.
Since in the coupon collector process in each round j we choose a random set
Sj of cardinality 1, by Lemma 71 the Xi are negatively correlated. Consequently,
Pr[Tn ≤ (1 − ε)(n − 1) ln n] = Pr[∀i ∈ [1..n] : Xi = 1]
≤

n
Y

Pr[Xi = 1]

i=1

≤ (1 − n−1+ε )n ≤ exp(−nε )
by Lemma 1.
We may remark that good mathematical understanding of the coupon collector process not only is important because such processes directly show up in some
randomized algorithms, but also because it might give us the right intuitive understanding of other processes. Consider, for example, a run of the (1 + 1) EA on
some pseudo-Boolean function f : {0, 1}n → R with a unique global maximum.
The following intuitive consideration leads us to believe that the (1 + 1) EA
with high probability needs at least roughly n ln n2 iterations to find the optimum
of f : By the strong concentration of the binomial distribution, the initial search
point differs in at least roughly n2 bits from the global optimum. To find the global
optimum, it is necessary (but clearly not sufficient) that each of these missing bits
is flipped at least once in some mutation step. Now that the (1 + 1) EA in average
34

flips one bit per iteration, this looks like a coupon collector process started with an
initial stake of n2 coupons, so we expect to need at least roughly n ln n2 iterations
to perform the n ln n2 bit-flips necessary to have each missing bit flipped at least
once. Clearly, this argumentation is not rigorous, but it suggested to us the right
answer.
Theorem 46. The optimization time T of the (1 + 1) EA on any function f :
{0, 1}n → R with unique global maximum satisfies
Pr[T ≤ (1 − ε)(n − 1) ln n2 ] ≤ exp(−nε ).
Proof. By symmetry, we may assume that the unique global optimum of f is
(1, . . . , 1). Let t = (1 − ε)(n − 1) ln n2 . For all i ∈ [1..n], let Yi denote the event
that the i-th bit was zero in the initial search point and was not flipped in any
application of the mutation operator in the first t iterations. Let Xi = 1 − Yi.
Then Pr[Xi = 1] = 1 − 12 (1 − n1 )t ≤ 1 − n−1+ε . The events Xi are independent, so
we compute
Pr[T ≤ t] ≤ Pr[∀i ∈ [1..n] : Xi = 1]
=

n
Y

Pr[Xi = 1]

i=1

= (1 − n−1+ε )n = exp(−nε ).
We stated the above theorem to give a simple example how understanding the
coupon collector process can help understanding also randomized search heuristics
that do not directly simulate a coupon collecting process. We remark that the
theorem above is not best possible, in particular, it does not outrule an expected
optimization time of n ln n2 . In contrast it is known that the optimization time of
the (1 + 1) EA on the OneMax function is E[T ] ≥ en ln n − O(n), see [DFW11],
improving over the slightly weaker E[T ] ≥ en ln n − O(n log log n) from, independently, [DFW10] and [Sud13], where the latter holds for a much broader
class of mutation-based algorithms. Since it has been observed that OneMax
is the easiest function with unique global optimum for many mutation-based algorithms [DJW12, Sud13, Wit13], these results take over to all pseudo-Boolean
functions with unique global optimum.

10

Large Deviation Bounds

Often, we are not only interested in the expectation of some random variable, but
we need a bound that holds with high probability. We have seen in the proof of
35

Theorem 14 that such high-probability statements can be very useful: If a certain
bad event occurs in each iteration with a very small probability only, then a simple
union bound is enough to argue that this event is unlikely to occur even over a large
number of iterations. The better the original high-probability statement is, the
more iterations we can cover. For this reason, the tools discussed in this chapter
are among the most employed in the theory of randomized search heuristics.
Since computing the expectation often is easy, a very common approach is to
first compute the expectation of a random variable and then bound the probability
that the random variable deviates from this expectation by a too large amount.
The tools for this second step are called tail inequalities or large deviation inequalities, and this is the topic of this section. In a sense, Markov’s and Chebyshev’s
inequality discussed in Section 6 can be seen as large deviation inequalities as well,
but usually the term is reserved for exponential tail bounds.
A large number of large deviation bounds have been developed in the past.
They differ in the situations they are applicable to, but also in their sharpness.
Often, the sharpest bounds give expressions for the tail probability that are very
difficult to work with. Hence some experience is needed to choose a tail bound
that is not overly complicated, but sharp enough to give the desired result.
To give the novice to this topic some orientation, here is a short list of results
that are particularly useful and which are sufficient in many situations.
(a) The simple multiplicative Chernoff bounds (33) and (40) showing that for
sums of independent [0, 1] random variables, a constant factor deviation from
the expectation occurs only with probability negatively exponential in the
expectation.
(b) The additive Chernoff bounds of Theorems 53 and 55 showing that a sum
of n independent random variables deviates from the expectation by more
2
than an additive term of λ only with probability exp(−Ω( λn )).
(c) The fact that essentially all large deviation bounds can be used also with
a pessimistic estimate for the expectation instead of the precise expectation
(Section 10.1.8).
(d) The method of bounded differences (Theorem 72), which states that the
additive Chernoff bounds remain valid if X is functionally dependent of
independent random variables each having a small influence on X.
For the experienced reader, the following results may be interesting as they go
beyond what most introductions to tail bounds cover.
(a) In Section 10.2.2 we show that essentially all large deviation bounds usually
stated for sums of independent random variables are also valid for negatively correlated random variables. An important application of this result
36

are distributions arising from sampling without replacement or with partial
replacement.
(b) In Section 10.4, we present a number of large deviation bounds for sums of
independent geometrically distributed random variables. These seem to be
particularly useful in the analysis of randomized search heuristics, whereas
they are rarely used in classic randomized algorithms.
(c) In Theorem 73, we present a version of the bounded differences method which
only requires that the t-th random variable has a bounded influence on the
expected outcome resulting from variables t + 1 to n. This is much weaker
than the common bounded differences assumption that each random variable, regardless how we condition on the remaining variables, has a bounded
influence on the result. We feel that this new version (which is an easy consequence of known results) may be very useful in the analysis of iterative
improvement heuristics. In particular, it may lead to elementary proofs for
results which so far could only be proven via tail bounds for martingales.

10.1

Chernoff Bounds for Sums of Independent Bounded
Random Variables

In this longer subsection, we assume that our random variable of interest is the
sum of independent random variables, each taking values in some bounded range.
The bounds presented below are all known under names like Chernoff or
Hoeffding bounds, referring to the seminal papers by Chernoff [Che52] and
Hoeffding [Hoe63]. Since the first bounds of this type were proven by Bernstein [Ber24]—via the exponential moments method that is used in essentially all
proofs of such results, see Section 10.1.7—the name Bernstein inequalities would be
more appropriate. We shall not be that precise and instead use the most common
name Chernoff inequalities for all such bounds.
For the readers’ convenience, we shall not be shy to write out also minor reformulations of some results. We believe that it helps a lot to have seen them and
we think that it is convenient, both for using the bounds or for referring to them,
if all natural version are visible in the text.
10.1.1

Multiplicative Chernoff Bounds for the Upper Tail

The multiplicative Chernoff bounds presented in this and the next section bound
the probability to deviate from the expectation by at least a given factor. Since
in many algorithmic analyses we are interested only in the asymptotic order of
magnitude of some quantity, a constant-factor deviation can be easily tolerated
37

and knowing that larger deviations are very unlikely is just what we want to
know. For this reason, the multiplicative Chernoff bounds are often the right tool.
The following theorem collects a number of bounds for the upper tail, that is,
for deviations above the expectation.
Theorem 47. Let X1 , . . . , Xn be independent random variables taking values in
P
[0, 1]. Let X = ni=1 Xi . Let δ ≥ 0. Then
Pr[X ≥ (1 + δ)E[X]]
≤

1
1+δ

!(1+δ)E[X]
!E[X]

n − E[X]
n − (1 + δ)E[X]

!n−(1+δ)E[X]

(29)

eδ
≤
= exp(−((1 + δ) ln(1 + δ) − δ)E[X])
(1 + δ)1+δ
!
δ 2 E[X]
≤ exp −
2 + 32 δ
!
min{δ 2 , δ}E[X]
≤ exp −
,
3
where the bound in (29) is read as 0 for δ >
For δ ≤ 1, equation (32) simplifies to

n−E[X]
E[X]

Pr[X ≥ (1 + δ)E[X]] ≤ exp

and as ( E[X]
)n for δ =
n

δ 2 E[X]
.
−
3
!

(30)
(31)
(32)
n−E[X]
.
E[X]

(33)

The first and strongest bound (29) was first stated explicitly by
Hoeffding [Hoe63]. It improves over Chernoff’s [Che52] tail bounds in particular by not requiring that the Xi are identically distributed. Hoeffding also shows
that (29) is the best bound that can be shown via the exponential moments methods under the assumptions of Theorem 47.
For E[X] small, say E[X] = o(n) when taking a view asymptotic in n → ∞,
the second bound (30) is easier to use, but essentially as strong as (29). More
precisely, it is larger only by a factor of (1 + o(1))E[X] , since we estimated
n − E[X]
n − (1 + δ)E[X]

!n−(1+δ)E[X]

δE[X]
= 1+
n − (1 + δ)E[X]

!n−(1+δ)E[X]

≤ eδE[X] (34)

using Lemma 1.
3δ2
Equation (31) is derived from (30) by noting that (1 + δ) ln(1 + δ) − δ ≥ 6+2δ
holds for all δ ≥ 0, see Theorem 2.3 and Lemma 2.4 in McDiarmid [McD98].
Equations (32) and (33) are trivial simplifications of (31).
38

f (x) = (1 + x) ln(1 + x) − x
x2
f (x) = 2+2x/3
f (x) = min{x2 , x}/3

f (x)

1.5

1

0.5

0

0.5

1

1.5

2

2.5

x
Figure 3: Visual comparison of the bounds (30), (31), (32). Depicted is the term
f (x) leading to the bound Pr[X ≥ (1 + x)E[X]] ≤ exp(−f (x)E[X]).
In general, to successfully use Chernoff bound in one’s research, it greatly
helps to look a little behind the formulas and understand their meaning. Very
roughly speaking, we can distinguish three different regimes relative to δ, namely
that the tail bound is of order exp(−Θ(δ log(δ)E[X])), exp(−Θ(δE[X])), and
exp(−Θ(δ 2 E[X])).
Superexponential regime: Equation (30) shows a tail bound of order
−Θ(δE[X])
δ
= exp(−Θ(δ log(δ)E[X])), where the asymptotics are for δ → ∞. In
this regime, the deviation δE[X] from the expectation E[X] is much larger than
the expectation itself. It is not very often that we need to analyze such large deviations, so this Chernoff bound is rarely used. It can be useful in the analysis of
evolutionary algorithms with larger offspring populations, where the most extreme
behavior among the offspring can deviate significantly from the expected behavior.
See [DK15, DD17] for examples how to use Chernoff bounds for large deviations
occurring in the analysis of the (1 + λ) EA. Note that in [JJW05], the first theoretical work on the (1 + λ) EA, such Chernoff bounds could have been used as
well, but the authors found it easier to directly estimate the tail probability by
estimating binomial coefficients.
Weaker forms of (30) are
Pr[X ≥ (1 + δ)E[X]] ≤

e
(1 + δ)

Pr[X ≥ (1 + δ)E[X]] ≤

e
δ

39

!(1+δ)E[X]

!δE[X]

,

,

(35)
(36)

where the first one is stronger for those values of δ where the tail probability is
less than one (that is, δ > e − 1).
It is not totally obvious how to find a value for δ ensuring that ( δe )δ is less than
a desired bound. The following lemma solves this problem.
Lemma 48. Let t ≥ ee

1/e

≈ 4.24044349... . Let δ =

Proof. We compute δ ln δe = δ ln



ln t
ln t
e ln( e ln
)
ln t



ln t
.
ln t
ln( e ln
)
ln t

Then ( eδ )δ ≤ 1t .

≥ δ ln( e lnlnlnt t ) = ln t.

We use this estimate to bound the number of bits flipped in an application of
the standard-bit mutation operator. The standard-bit mutation operator takes as
input a bit-string x ∈ {0, 1}n of length n and returns the bit-string y ∈ {0, 1}n
obtained from flipping each bit of x independently at random with probability n1 ,
that is, for each i ∈ [1..n] independently we have Pr[yi = 1 − xi ] = n1 and Pr[yi =
xi ] = 1 − n1 . Let us denote by H(x, y) := |{i ∈ [1..n] | xi 6= yi } the Hamming
distance of x and y, that is, the number of bits x and y differ in. By linearity
of expectation, it is clear that the expected Hamming distance of x and y is
E[H(x, y)] = 1, see Lemma 21. Using Chernoff bounds, we now give an upper
bound on how far we can exceed this value. Such arguments are often useful
in the analysis of evolutionary algorithms, see, e.g., Lemma 26 in [DK15] for an
example.
Lemma 49. (a) Let x ∈ {0, 1}n and y be obtained from x via standard-bit mutation with mutation rate αn . Then Pr[H(x, y) ≥ k] ≤ ( eα
)k .
k
(b) Let 0 < p ≤ exp(−α exp( 1e )).

Let k ≥ kp :=

ln(1/p)



ln

Pr[H(x, y) ≥ k] ≤ p.

ln(1/p1/α )
e ln ln(1/p1/α )

.

Then

(c) Let T ∈ N and 0 < p ≤ T1 exp(−α exp( 1e )). Let y1 , . . . , yT be obtained from
ln(T /p)
.
x1 , . . . , xT , respectively, via standard-bit mutation. Let k ≥  ln((T
/p)1/α )
ln

e ln ln((T /p)1/α )

Then

Pr[∃i ∈ [1..T ] : H(xi , yi) ≥ k] ≤ p.
Proof. Note that H(x, y) ∼ Bin(n, αn ), hence H(x, y) can be written as a sum of n
independent random variables X1 , . . . , Xn with Pr[Xi = 1] = αn and Pr[Xi = 0] =
1 − αn for all i ∈ [1..n]. Since E[H(x, y)] = α, we can apply equation (35) with
(δ + 1) = αk . This proves (a).
For part (b), we use Lemma 48 and compute Pr[H(x, y) ≥ k] ≤ Pr[H(x, y) ≥
kp ] ≤ (( kpe/α )kp /α )α ≤ (p1/α )α = p. Similarly, for (c) we obtain Pr[H(xi, yi ) ≥ k] ≤
p
and use the union bound (Lemma 12).
T
40

Observe that the bounds in Lemma 49 are independent of n. Also, the bounds
in parts (b) and (c) depend only mildly on α. By applying part (c) with p = n−c1
and T = nc2 , we see that the probability that an evolutionary algorithm using
standard-bit mutation with rate αn , α a constant, flips more than (c1 +c2 +o(1)) lnlnlnnn
bits in any of the first nc2 applications of the mutation operator, is at most n−c1 .
Exponential regime: When δ = Θ(1), then all bounds give a tail probability of order exp(−Θ(δE[X])). Note that the difference between these bounds
often is not very large. For δ = 1, the bounds in (30), (31), and (32) become
(0.67957...)E[X], (0.68728...)E[X] , and (0.71653...)E[X] , respectively. So there is often no reason to use the unwieldy equation (30).
We remark that also for large δ, where the bound (30) gives the better asymptotics exp(−Θ(δ log(δ)E[X])), one can, with the help of Section 10.1.8 resort to
the easier-to-use bounds (31) and (32) when the additional logarithmic term is
not needed. For example, when X is again the number of bits that flip in an
application of the standard-bit mutation operator with mutation rate p = αn , then
for all c > 0 and n ∈ N with c ln n ≥ α equation (32) with E[X] ≤ µ+ := c ln n
and the argument of Section 10.1.8 gives Pr[X ≥ 2c ln n] = Pr[X ≥ (1 + 1)µ+ ] ≤
exp(− 31 µ+ ) = n−c/3 , which in many applications is fully sufficient.
A different way of stating an exp(−Θ(δE[X])) tail bound, following directly
from applying (35) for δ ≥ 2e − 1, is the following.
Corollary 50. Under the assumptions of Theorem 47, we have
Pr[X ≥ k] ≤ 2−k

(37)

for all k ≥ 2eE[X].
Sub-exponential regime: When δ ≤ 1, the tail probability is of order
exp(−Θ(δ 2 E[X])). We need δ to be at least of order (E[X])−1/2 to obtain useful statements. Note that for E[X] close to n2 , Theorem 53 below gives slightly
stronger bounds.
10.1.2

Multiplicative Chernoff Bounds for the Lower Tail

In principle, of course, there is no difference between bounds for the upper and
lower tail. If in the situation of Theorem 47 we set Yi := 1 − Xi , then the Yi
are independent random variables taking values in [0, 1] and any upper tail bound
P
for X turns into a lower tail bound for Y := ni=1 Yi via Pr[Y ≤ t] = Pr[X ≥
n − t]. However, since this transformation also changes the expectation, that is,
E[Y ] = n − E[X], a convenient bound like (33) becomes Pr[Y ≤ (1 − δ)E[Y ]] ≤
E[Y ] 2
exp(− 13 (1 + δ n−E[Y
) (n − E[Y ])).
]
For this reason, usually the tail bounds for the lower tail are either proven
completely separately (however, using similar ideas) or are derived from simplifying
41

f (x) = −x − (1 − x) ln(1 − x)
2
f (x) = x2

0.8

f (x)

0.6
0.4
0.2
0

0.2

0.4

0.6

0.8

x
Figure 4: Visual comparison of the bounds (39) and (40). Depicted is the term
f (x) leading to the bound Pr[X ≤ (1 − x)E[X]] ≤ exp(−f (x)E[X]).
the result of applying the above symmetry argument to (29). Either approach can
be used to show the following bounds. As a visible result of the asymmetry of
the situation for upper and lower bounds, note the better constant of 21 in the
exponent of (40) as compared to the 13 in (33).
Theorem 51. Let X1 , . . . , Xn be independent random variables taking values in
P
[0, 1]. Let X = ni=1 Xi . Let δ ∈ [0, 1]. Then
Pr[X ≤ (1 − δ)E[X]] ≤

1
1−δ

!(1−δ)E[X]

!E[X]

e−δ
≤
(1 − δ)1−δ
!
δ 2 E[X]
≤ exp −
.
2

n − E[X]
n − (1 − δ)E[X]

!n−(1−δ)E[X]

(38)
(39)
(40)

For the not so interesting boundary cases, recall our definition 00 := 1. The
first bound (38) follows from (29) by regarding the random variables Yi := 1 − Xi.
P
, we compute
Setting Y = ni=1 Yi and δ ′ = δ E[X]
E[Y ]
Pr[X ≤ (1 − δ)E[X]] = Pr[Y ≥ (1 + δ ′ )E[Y ]]
≤

1
1 + δ′

!(1+δ′ )E[Y ]

42

n − E[Y ]
n − (1 + δ ′ )E[Y ]

!n−(1+δ′ )E[Y ]

=

n − E[X]
n − (1 − δ)E[X]

!n−(1−δ)E[X]

1
1−δ

!(1−δ)E[X]

.

Obviously, in an analoguous fashion, (29) can be derived from (38), so both
bounds are equivalent. Equation (39) follows from (38) using an elementary estimate analoguous to (34). Equation (40) follows from (39) using elementary
calculus, see, e.g., the proof of Theorem 4.5 in [MU05].
Theorems 47 and 51 in particular show that constant-factor deviations from
the expectation appear only with exponentially small probability.
Corollary 52. Let X1 , . . . , Xn be independent random variables taking values in
P
[0, 1]. Let X = ni=1 Xi . Let δ ∈ [0, 1]. Then
h

i

Pr |X − E[X]| ≥ δE[X] ≤ 2 exp
10.1.3

δ 2 E[X]
−
.
3
!

Additive Chernoff Bounds

We now present a few bounds for the probability that a random variable deviates
from its expectation by an additive term independent of the expectation. The
advantage of such bounds is that they are identical for upper and lower tails and
that they are invariant under additive rescalings.
Already from Theorem 47, equation (29), by careful estimates (see, e.g.,
Hoeffding [Hoe63]) and exploiting the obvious symmetry, we obtain the following
estimates. When E[X] is close to n2 , this additive Chernoff bound gives (slightly)
stronger results than the simplified bounds of Theorems 47 and 51.
Theorem 53. Let X1 , . . . , Xn be independent random variables taking values in
P
[0, 1]. Let X = ni=1 Xi . Then for all λ ≥ 0,
Pr[X ≥ E[X] + λ] ≤ exp
Pr[X ≤ E[X] − λ] ≤ exp

2λ2
,
−
n
!
2λ2
−
.
n
!

(41)
(42)

A second advantage of additive Chernoff bounds is that they are often very
easy to apply. As a typical application in evolutionary computation, let us regard
the number of ones kxk1 in a random search point x ∈ {0, 1}, which could, e.g.,
be an initial solution in an evolutionary algorithm.
Lemma 54. Let x ∈ {0, 1}n be chosen uniformly at random. Then
Pr



n
2λ2
kxk1 −
.
≥ λ ≤ 2 exp −
2
n


43

!

Proof. Note that if x ∈ {0, 1}n is uniformly distributed, then the xi are independent random variables uniformly distributed in {0, 1}. Consequently, kxk1 =
Pn
n
i=1 xi is a sum of independent random variables and E[kxk1 ] = 2 . The claim now
follows immediately from applying Theorem 53 to the events “kxk1 ≥ E[kxk1 ]+ λ”
and “kxk1 ≤ E[kxk1 ] − λ”.
The following theorem, again due to Hoeffding [Hoe63], non-trivially extends
Theorem 53 by allowing the Xi to take values in arbitrary intervals [ai , bi ].
Theorem 55. Let X1 , . . . , Xn be independent random variables. Assume that each
P
Xi takes values in a real interval [ai , bi ] of length ci := bi − ai . Let X = ni=1 Xi .
Then for all λ > 0,
Pr[X ≥ E[X] + λ] ≤ exp
Pr[X ≤ E[X] − λ] ≤ exp

2λ2

!

− Pn

,

(43)

.

(44)

2
i=1 ci
!
2

2λ
− Pn

2
i=1 ci

For comparison, we now reformulate Theorems 47 and 51 as additive bounds.
There is no greater intellectual challenge hidden, but we feel that it helps to have
seen these bounds at least once. Note that, since the resulting bounds depend on
the expectation, we need that the Xi take values in [0, 1]. In other words, different
from the bounds presented so far in this subsection, the following bounds are not
invariant under additive rescaling and are not symmetric for upper and lower tails.
Theorem 56 (equivalent to Theorem 47). Let X1 , . . . , Xn be independent random
P
variables taking values in [0, 1]. Let X = ni=1 Xi . Let λ ≥ 0. Then
Pr(X ≥ E[X] + λ)
≤

E[X]
E[X] + λ

≤ eλ
≤ exp
≤ exp

!E[X]+λ

E[X]
E[X] + λ

n − E[X]
n − E[X] − λ

!E[X]+λ

= exp

!n−E[X]−λ

(45)
!

λ
+λ
− (E[X] + λ) ln 1 +
E[X]

λ2
−
2E[X] + 23 λ
(
)!
1
λ2
− min
,λ ,
3
E[X]
!

!

(46)
(47)
(48)

)n for λ =
where the bound in (45) is read as 0 for λ > n − E[X] and as ( E[X]
n
n − E[X]. For λ ≤ E[X], equation (48) simplifies to
Pr[X ≥ E[X] + λ] ≤ exp
44

λ2
−
.
3E[X]
!

(49)

Theorem 57 (equivalent to Theorem 51). Let X1 , . . . , Xn be independent random
P
variables taking values in [0, 1]. Let X = ni=1 Xi . Let δ ∈ [0, 1]. Then
Pr[X ≤ E[X] − λ] ≤

E[X]
E[X] − λ

!E[X]−λ

!n−E[X]+λ

!E[X]−λ

E[X]
≤e
E[X] − λ
!
λ2
.
≤ exp −
2E[X]
−λ

10.1.4

n − E[X]
n − E[X] + λ

(50)
(51)
(52)

Chernoff Bounds Using the Variance

There are several versions of Chernoff bounds that take into account the variance.
In certain situations, they can give significantly stronger bounds than the estimates
discussed so far. Hoeffding [Hoe63] proves essentially the following result.
Theorem 58. Let X1 , . . . , Xn be independent random variables such that Xi ≤
P
P
E[Xi ] + 1 for all i = 1, . . . , n. Let X = ni=1 Xi . Let σ 2 = ni=1 Var(Xi ) = Var[X].
Then for all λ ≥ 0,
Pr[X ≥ E[X] + λ]
≤

≤ exp
= exp
≤ exp
≤ exp

2

σ
) n+σ
2

!− 1− λ n !n
λ ( n ) n+σ2
1−
n
!
!
!!
2
λ
σ
ln 1 + 2 − 1
−λ 1+
λ
σ
!
!
!!
λ
λ
λ
2
1 + 2 ln 1 + 2 − 2
−σ
σ
σ
σ
!
2
λ
− 2 2
2σ + 3 λ
(
)!
1
λ2
− min
,λ ,
3
σ2

λ
1+ 2
σ

!−(1+

λ
σ2

(53)

(54)

(55)
(56)
2

σ
n
where the term in (53) is understood to mean 0 when λ > n and ( n+σ
when
2)
λ = n.

The estimate from (53) to (54) is non-trivial and can be found, e.g., in
Hoeffding [Hoe63]. From (54) we derive (55) in the same way that was used
to derive (31) from (30).
By replacing Xi with −Xi , we obtain the analoguous bounds for the lower tail.
45

Corollary 59. If the condition Xi ≤ E[Xi ] + 1 in Theorem 58 is replaced by
Xi ≥ E[Xi ] − 1, then Pr[X ≤ E[X] − λ] satisfies the estimates of equations (53)
to (56).
As discussed in Hoeffding [Hoe63], the bound (54) is the same as inequality (8b)
in Bennett [Ben62], which is stronger than the bound (55) due to Bernstein [Ber24]
and the bound of exp(− 12 λ arcsinh( 2σλ2 )) due to Prokhorov [Pro56].
In comparison to the additive version of the usual Chernoff bounds for the upper
tail (Theorem 56), very roughly speaking, we see that the Chernoff bounds working
with the variance allow to replace the expectation of X by its variance. When the
Xi are binary random variables with Pr[Xi = 1] small, then E[X] ≈ Var[X]
and there is not much value of using Theorem 58. For this reason, Chernoff
bounds taking into account the variance have not been used a lot in the theory
of randomized search heuristics. They can, however, be convenient. For example,
when a search point y ∈ {0, 1}n is obtained from a given x ∈ {0, 1}n via standardbit mutation with probability p. Assume for simplicity that we are interested
in estimating the number of ones in y (the same argument would hold for the
Hamming distance of y to some other search point z ∈ {0, 1}∗, e.g., a unique
P
optimum). Now the number of ones in y is simply X = ni=1 yi and X is a sum of
independent binary random variables. The expectation of X may be big, namely
if x has many ones, but the variance is small (assuming that p is small), namely
Var[X] = np(1 − p). Consequently, here the Chernoff bounds of this subsection
are very useful. See, e.g., [DGWY17] for an example where this problem appeared
in a recent research paper.
When not too precise bounds are needed, looking separately at the number
of zeros and ones of x that flip (and bounding these via simple Chernoff bounds)
is a way to circumvent the use of Chernoff bounds taking into account the variance. Several research works follow this approach despite the often more technical
computations.
Chernoff bounds using the variance can also be useful in ant colony algorithms
and estimation of distribution algorithms, where again pheromone values or frequencies close to 0 or 1 can lead to a small variance. See [Wit17] for a recent
example.
The bounds of Theorem 58 can be written in a multiplicative form, e.g.,
Pr[X ≥ (1 + δ)E[X]]

!−(1+ δE[X] )

δE[X]
≤
1+
σ2
!
δ 2 E[X]2
≤ exp − 2 2
.
2σ + 3 δE[X]
σ2

σ2
n+σ 2

δE[X]
1−
n

!−(1− δE[X] )
n

n
n+σ 2

!n

(57)
(58)

46

This is useful when working with relative errors, however, it seems that unlike for
some previous bounds (compare, e.g., (30) and (46)) the multiplicative forms are
not much simpler here.
Obviously, the case that all Xi satisfy Xi ≤ E[Xi ] + b for some number b
(instead of 1) can be reduced to the case b = 1 by dividing all random variable
by b. For the reader’s convenience, we here state the resulting Chernoff bounds.
Theorem 60 (equivalent to Theorem 58 and Corollary 59). Let X1 , . . . , Xn be
independent random variables. Let b be such that Xi ≤ E[Xi ] + b for all i =
P
P
1, . . . , n. Let X = ni=1 Xi . Let σ 2 = ni=1 Var(Xi ) = Var[X]. Then for all λ ≥ 0,
!−(1+ bλ )

σ2
nb2 +σ 2

2

≤ exp

!−(1− λ ) nb !n
nb nb2 +σ 2
λ
1−
nb
!
!
!!
σ2
bλ
1+
ln 1 + 2 − 1
bλ
σ
!
2
λ
− 2
σ (2 + 23 σbλ2 )

≤ exp

1
λ2 λ
− min
,
3
σ2 b

bλ
Pr[X ≥ E[X] + λ] ≤
1+ 2
σ
λ
≤ exp −
b

σ2

(

)!

,

(59)
(60)
(61)
(62)

2

where the term in (59) is understood to mean 0 when λ > nb and ( nb2σ+σ2 )n when
λ = nb.
When we have Xi ≥ E[Xi ] − b instead of Xi ≤ E[Xi ] + b for all i = 1, . . . , n,
then the above estimates hold for Pr[X ≤ E[X] − λ].
10.1.5

Relation Between the Different Chernoff Bounds

We proceed by discussing how the bounds presented so far are related. The main
finding will be that the Chernoff bounds depending on the variance imply all
other bounds discussed so far with the exception of the additive Chernoff bound
for different variable ranges (Theorem 55).
Surprisingly, this fact is not stated that explicitly in Hoeffding’s paper [Hoe63].
More precisely, in [Hoe63] the analogue of Theorems 58 and 60 uses the additional
assumption that all Xi have the same expectation. Since this assumption is not
made for the theorems not involving the variance, Hoeffding explicitely states that
the latter are stronger in this respect (see the penultimate paragraph of Section 3
of [Hoe63].
It is however quite obvious that the common-expectation assumption can be
easily removed. From random variables with arbitrary means we can obtain random variables all having mean zero by subtracting their expectation. This operation does not change the variance and does not change the distribution of X −E[X].
47

Consequently, Hoeffding’s result for variables with identical expectations immediately yields our version of this result (Theorem 58 and 60). Theorem 58 implies
Theorem 47 via the equivalent version of Theorem 56, see again the penultimate
paragraph of Section 3 of [Hoe63].
Consequently, the first (strongest) bound in Theorem 58 (equivalently the first
bound of Theorem 60) implies the first (strongest) bound of Theorem 47, which
is equivalent to the first (strongest) bound in Theorem 51. Essentially all other
bounds presented so far can be derived from these main theorems via simple,
sometimes tedious, estimates. The sole exception is Theorem 55, which can lead to
significantly stronger estimates when the random variables have ranges of different
size.
As an example, let X1 , . . . , Xn be independent random variables such that
X1 , . . . , Xn−1 take the values 0 and (n − 1)−1/2 with equal probability 12 and such
P
that Xn takes
the values 0 and 1 with equal probability 21 . Let X = ni=1 Xi . Then
√
E[X] = 12 ( n − 1 + 1). Theorem 55, taking ci = (n − 1)−1/2 for i ∈ [1..n − 1] and
cn = 1, yields the estimate
Pr[X ≥ E[X] + λ] ≤ exp
Note that Var[X] =

1
2

2λ2

− Pn

2
i=1 ci

!

= exp(−λ2 ).

(63)

=: σ 2 . Consequently, the strongest Chernoff bound of
λ

nσ 2

Theorem 58, equation (53), gives an estimate larger than (1 + σλ2 )−(1+ σ2 ) n+σ =
exp(−Θ(λ log λ)). Consequently, in this case Theorem 55 gives a significantly
stronger estimate than Theorem 58.
10.1.6

Tightness of Chernoff Bounds, Lower Bounds for Deviations

As a very general and not at all precise rule of thumb, we can say that often the
sharpest Chernoff bound presented so far gives an estimate for the tail probability
that is near-tight. This is good to know from the perspective of proof design, since
it indicates that failing to prove a desired statement usually cannot be overcome by
trying to invent sharper Chernoff bounds. We shall not try to make this statement
precise.
However, occasionally, we also need lower bounds for the deviation from the
expectation as a crucial argument in our analysis. For example, when generating
several offspring independently in parallel, as, e.g., in a (1 + λ) EA, we expect the
best of these to be significantly better than the expectation and the efficiency of
the algorithm relies on such large deviations from the expectation.
Such lower bounds for deviations seem to be harder to work with. For this
reason, we only briefly give some indications how to handle them and refer the
reader to the literature. We note that there is a substantial body of mathematics
48

literature on this topic, see, e.g., [Nag01] and the references therein, which however
is not always easy to use for algorithmic problems.
Estimating binomial coefficients: While more advanced methods are available, surprisingly often estimating the sum of binomial coefficients arising in the
expression of the tail probability is a good approach. In the theory of randomized search heuristics, this approach was used, among others, in the analysis of the
(1+λ) EA in [JJW05, DK15, GW17, DGWY17] and the (1+(λ, λ)) GA in [DD17].
The following elementary bound was shown in [Doe14].
Lemma 61. Let n ∈ N and X ∼ Bin(n,

1
).
2



Then Pr X ≤ E[X] −

1
2

q



E[X] ≥ 18 .

Approximation via the normal distribution: The generic approach of approximating binomial distributions via normal distributions, surprisingly, is not
often used in the theory of randomized search. In [OW15], it was used to give
an elegant proof of the fact that a binomial random variable
X with p ≤ 12 with
q
constant probability deviates from its expectation by Ω( E[X]). This matches
the case of δ = Θ(E[X]−1/2 ) in (40).
Lemma 62. Let X ∼ Bin(n, p) with p ≤ 21 . Then Pr[X ≤ E[X] −

Pr[X ≥ E[X] +

q

1
E[X] ]
2

are both Ω(1).

q

1
E[X] ]
2

and

In [dPdLDD15],
the normal approximation was used to show that the best of
√
n
k ∈ ω(n) ∩ o( n) independent random
q initial search points in {0, 1} with probability 1 − o(1) has a distance of n2 − n2 (ln k − 12 ln ln k ± ck ) from the optimum,
where ck is an arbitrary sequence tending to infinity.
Order statistics: The last example actually says something about the maximum order statistics of k independent Bin(n, 12 ) random variables. In general, the
maximum order statistics is strongly related to lower bounds for tail probabilities
as the following elementary argument (more or less explicit in all works on the
(1 + λ) EA) shows: Let X1 , . . . , Xλ be independent random variables following the
same distribution. Let Xmax = max{Xi | i ∈ [1..λ]}. Then
Pr[X ∗ ≥ D] ≤ λ Pr[X1 ≥ D];

Pr[X ∗ ≥ D] = 1 − (1 − Pr[X1 ≥ D])λ ≥ 1 − exp(λ Pr[X1 ≥ D]).
Consequently, Pr[X ∗ ≥ D] is constant if and only if Pr[X1 ≥ D] = Θ( λ1 ).
For the maximum order statistics of binomially distributed random variables
with small success probability, Gießen and Witt [GW17] proved the following result
and used it in the analysis of the (1 + λ) EA.
49

Lemma 63. Let α ≥ 0 and c > 0 be constants. Let n ∈ N and let all of the
following asymptotics be for n → ∞. Let k = n(ln n)−α and λ = ω(1). Let Xmax
be the maximum of λ independent random variables with distribution Bin(k, nc ).
1
ln λ
Then E[Xmax ] = (1 ± o(1)) 1+α
.
ln ln λ
Extremal situations: Occasionally, it is desirable to understand which situation gives the smallest or the largest deviations. For example, let X1 , . . . , Xn be
independent binary random variables with expectations E[Xi ] = pi . Then it could
P
be useful to know that X = ni=1 Xi deviates most (in some suitable sense) from
its expectation when all pi are 12 . Such statements can be made formal and can be
proven with the notions of majorization and Schur-convexity. We refer to [Sch00]
for a nice treatment of this topic. Such arguments have been used to analyze
estimation-of-distribution algorithms in [SW16].
Staying on one side of the expectation and Feige’s inequality: When it
suffices to know that with reasonable probability we stay (more or less) on one
side of the expectation, then the following results can be useful.
A very general bound is Feige’s inequality [Fei06], which has found applications
in the analysis of randomized search heuristics, among others, in [ST12, DL15,
CDEL16, LN17].
Lemma 64 (Feige’s inequality). Let X1 , . . . , Xn be independent non-negative ranP
dom variables with expectations µi := E[Xi ] satisfying µi ≤ 1. Let X = ni=1 Xi .
Then
δ
1
, δ+1
}.
Pr[X ≤ E[X] + δ] ≥ min{ 13
For binomial distributions, we have stronger guarantees. Besides bounds comparing the binomial distribution with its normal approximation [Slu77], the following specific bounds are known.
Lemma 65. Let n ∈ N, p ∈ [0, 1], and k = ⌊np⌋. Let X ∼ Bin(n, p).
(a) If

1
n

< p, then Pr[X ≥ E[X]] > 41 .

(b) If 0.29/n ≤ p < 1, then Pr[X > E[X]] ≥ 14 .
1
,
n

(c) If

1
n

≤p≤1−

(d) If

1
n

≤ p < 1, then Pr[X > E[X]] >

then Pr[X ≥ E[X]] ≥

50

1
2

−

√

1 √ np(1−p)
√
.
2 2
np(1−p)+1+1

q

n
.
2πk(n−k)

(e) If

1
n

≤ p < 1 − n1 , then Pr[X > E[X] + 1] ≥ 0.037.

Surprisingly, all these results are quite recent. Bound (a) from [GM14] appears
to be the first general result of this type at all.1 It was followed up by estimate (c)
from [PR16], which gives stronger estimates when np(1 − p) > 8. Result (d)
from [Doe17] is the only one to give a bound tending to 12 for both np and n(1 − p)
tending to infinity. Estimates (b) and (e) are also from [Doe17]. A lower bound
for the probability of exceeding the expectation by more than one, like (e), was
needed in the analysis of an evolutionary algorithm with self-adjusting mutation
rate (proof of Lemma 3 of the extended version of [DGWY17]).
10.1.7

Proofs of the Chernoff Bounds

As discussed in the previous subsection, all Chernoff bounds stated so far can
be derived from the strongest bounds of Theorem 55 or 58 via elementary estimates that have nothing to do with probability theory. We shall not detail these
estimates—the reader can find them all in the literature, e.g., in [Hoe63]. We shall,
however, sketch how to prove these two central inequalities (43) and (53). One reason for this is that we can then argue in Section 10.2.2 that these proofs (and thus
also all Chernoff bounds presented so far) in fact not only hold for independent
random variables, but also negatively correlated ones.
A second reason is that occasionally, it can be profitable to have this central
argument ready to prove Chernoff bounds for particular distributions, for which
the classic bounds are not applicable or do not give sufficient results. This has
been done, e.g., in [DFW11, OW11, OW12, DJWZ13, LW14, Wit14, BLS14].
The central step in almost all proofs of Chernoff bounds, going back to Bernstein [Ber24], is the following one-line argument. Let h > 0. Then
Pr[X ≥ t] ≤ Pr[ehX ≥ eht ] ≤

n
Y
E[ehX ]
−ht
E[ehXi ].
=
e
eht
i=1

Here the first inequality simply stems from the fact that the function x 7→
ehx is monotonically increasing. The second inequality is Markov’s inequality
(Lemma 23) applied to the (non-negative) random variable ehX . The last equality
exploits the independence of the Xi , which carries over to the ehXi .
It now remains to estimate E[ehXi ] and choose h as to minimize the resulting
expression. We do this exemplarily for the case that all Xi take values in [0, 1] and
that E[X] < t < n. Since the exponential function is convex, E[ehXi ] is maximized
(which is the worst-case for your estimate) when Xi is concentrated on the values
For p ∈ [ n1 , 12 ], this result follows from the proof of Lemma 6.4 in [RT11]. The lemma itself
only states the bound Pr[X ≥ E[X]] ≤ min{p, 14 } for p ≤ 21 . The assumption p ≤ 12 appears to
be crucial for the proof.
1

51

0 and 1, that is, we have Pr[Xi = 1] = E[Xi ] and Pr[Xi = 0] = 1 − E[Xi ]. In
this case, E[ehXi ] = (1 − E[Xi ])e0 + E[Xi ]eh . By the inequality of arithmetic and
geometric means, we compute
n
Y

i=1

E[ehXi ] ≤
≤
≤

n
Y

(1 − E[Xi] + E[Xi ]eh )

i=1

n
1X
(1 − E[Xi ] + E[Xi ]eh )
n i=1

1
(n − E[X] + E[X]eh )
n

!n

!n

.

This gives the tail estimate Pr[X ≥ t] ≤ e−ht ( n1 (n − E[X] + E[X]eh ))n , which is
minimized by taking
!
(n − E[X])t
h = ln
,
(n − t)E[X]

which then gives the strongest multiplicative Chernoff bound (29) by rewriting
t = (1 + δ)E[X].
10.1.8

Chernoff Bounds with Estimates for the Expectation

Often we do not know the precise value of the expectation or it is tedious to compute it. In such cases, we can exploit the fact that all Chernoff bounds discussed
in this work are valid also when the expectation is replaced by an upper or lower
bound for it. This is obvious for many bounds, e.g., from equations (41), (42),
and (40) we immediately derive the estimates
2λ2
Pr[X ≥ µ + λ] ≤ Pr[X ≥ µ + λ] ≤ exp −
,
n
!
2
2λ
Pr[X ≤ µ− − λ] ≤ Pr[X ≤ µ − λ] ≤ exp −
,
n
!
δ2µ
−
≤ exp
Pr[X ≤ (1 − δ)µ ] ≤ Pr[X ≤ (1 − δ)µ] ≤ exp −
2
!

+

δ 2 µ−
−
2

!

for all µ+ ≥ E[X] =: µ and µ− ≤ E[X].
This is less obvious for a bound like Pr[X ≥ (1 + δ)µ+ ] ≤ exp(− 31 δ 2 µ+ ), since
now also the probability of the tail event decreases for increasing µ+ . However,
also for such bounds we can replace E[X] by an estimate as the following argument
shows.

52

Theorem 66. (a) Upper tail: Let X1 , . . . , Xn be independent random variables
P
taking values in [0, 1]. Let X = ni=1 Xi . Let µ+ ≥ E[X]. Then for all
δ ≥ 0,
+

Pr[X ≥ (1 + δ)µ ] ≤

1
1+δ

!(1+δ)µ+

n − µ+
n − (1 + δ)µ+
+

!n−(1+δ)µ+
+

,

(64)
+

and as ( µn )n for δ = n−µ
.
where this bound is read as 0 for δ > n−µ
µ+
µ+
Consequently, all Chernoff bounds of Theorem 47 (including equations (35)
and (36) and Corollary 50) as well as those of Theorem 56 are valid when all
occurrences of E[X] are replaced by µ+ . The additive bounds (41) and (43)
as well as those of Theorem 58 and 60 are trivially valid with the expectation
replaced by an upper bound for it.
(b) Lower tail: All Chernoff bounds of Theorem 51 and 57, the ones in equations (42) and (44), as well as those of Corollary 59 are valid when all
occurrences of E[X] are replaced by µ− ≤ E[X].
Proof. We first show (64). There is nothing to do when (1 + δ)µ+ > n, so let
+ −E[X]
us assume (1 + δ)µ+ ≤ n. Let γ = µn−E[X]
. For all i ∈ [1..n], define Yi by
Yi = Xi + γ(1 − Xi ). Since γ ≤ 1, Yi ≤ 1. By definition, Yi ≥ Xi , and thus also
P
Y ≥ X for Y := ni=1 Yi . Also, µ+ = E[Y ]. Hence
Pr[X ≥ (1 + δ)µ+ ] ≤ Pr[Y ≥ (1 + δ)µ+ ] = Pr[Y ≥ (1 + δ)E[Y ]].

Now (64) follows immediately from Theorem 47, equation (29). Since (64) implies
all other Chernoff bounds of Theorem 47 (including equations (35) and (36) and
Corollary 50) via elementary estimates, all these bounds are valid with E[X] replaced by µ+ as well. This extends to Theorem 56, since it is just a reformulation
of Theorem 47. For the remaining (additive) bounds, replacing E[X] by an upper bound only decreases the probability of the tail event, so clearly these remain
valid.
To prove our claim on lower tail bounds, it suffices to note that all bounds in
Theorem 51 are monotonically decreasing in E[X]. So replacing E[X] by some
µ− < E[X] makes the tail event less likely and increases the probability in the
statement. Similarly, the additive bounds are not affected when replacing E[X]
with µ− .
We note without proof that the variance of the random variable Y constructed
above is at most the one of X. Since the tail bound in Theorem 58 is increasing in σ 2 , the same argument as above also shows that multiplicative versions of
Theorem 58 such as equation (57) remain valid when all occurrences of E[X] are
replaced by an upper bound µ+ ≥ E[X].
53

10.2

Chernoff Bounds for Sums of Dependent Random
Variables

In the previous subsection, we discussed large deviation bounds for the classic
setting of sums of independent random variables. In the analysis of algorithms,
often we cannot fully satisfy the assumption of independence. The dependencies
may appear minor, maybe even in our favor in some sense, so we could hope for
some good large deviations bounds.
In this section, we discuss three such situations which all lead to (essentially)
the known Chernoff bounds being applicable despite perfect independence missing.
The first of these was already discussed in Section 8.3, so we just note here how it
also implies the usual Chernoff bounds.
10.2.1

Unconditional Sequential Domination

In the analysis of sequential random processes such as iterative randomized algorithms, we rarely encounter that the events in different iterations are independent,
simply because the actions of our algorithm depend on the results of the previous
iterations. However, due to the independent randomness used, we can often say
that, independent of what happened in iterations 1, . . . , t − 1, in iteration t we
have a particular event with at least some probability p.
This property was made precise in the definition of unconditional sequential
domination before Lemma 38. This lemma then showed that unconditional sequential domination can lead to domination between the sums of the random
variables. This, however, immediately yields that tail bounds for the one set take
over to the other. We make this elementary insight precise in the following lemma.
This type of argument was used, among others, in works on shortest path problems [DHK11, DHK12]. Here one can show that, in each iteration, independent
of the past, with at least a certain probability an extra edge of a desired path is
found.
Lemma 67. Let (X1 , . . . , Xn ) and (X1∗ , . . . , Xn∗ ) be finite sequences of discrete
random variables. Assume that X1∗ , . . . , Xn∗ are independent.
(a) If (X1∗ , . . . , Xn∗ ) unconditionally sequentially dominates (X1 , . . . , Xn ), then
P
P
for all λ ∈ R, we have Pr[ ni=1 Xi ≥ λ] ≤ Pr[ ni=1 Xi∗ ≥ λ] and the latter expression can be bounded by Chernoff bounds for the upper tail of independent
random variables.
(b) If (X1∗ , . . . , Xn∗ ) unconditionally sequentially subdominates (X1 , . . . , Xn ),
P
P
then for all λ ∈ R, we have Pr[ ni=1 Xi ≤ λ] ≤ Pr[ ni=1 Xi∗ ≤ λ] and
the latter expression can be bounded by Chernoff bounds for the lower tail of
independent random variables.
54

10.2.2

Negative Correlation

Occasionally, we encounter random variables that are not independent, but that
display an intuitively even better negative correlation behavior. Take as example
the situation that we do not flip bits independently with probability nk , but that
we flip a set of exactly k bits chosen uniformly at random among all sets of k out
of n bits. Let X1 , . . . , Xn be the indicator random variables for the events that
bit 1, . . . , n flips. Clearly, the Xi are not independent. If X1 = 1, then Pr[X2 =
k−1
1] = n−1
, which is different from the unconditional probability nk . However, things
feel even better than independent: Knowing that X1 = 1 actually reduces the
probability that X2 = 1. This intuition is made precise in the following notion of
negative correlation.
Let X1 , . . . , Xn binary random variables. We say that X1 , . . . , Xn are
1-negatively correlated if for all I ⊆ [1..n] we have
Pr[∀i ∈ I : Xi = 1] ≤

Y

Pr[Xi = 1].

i∈I

We say that X1 , . . . , Xn are 0-negatively correlated if for all I ⊆ [1..n] we have
Pr[∀i ∈ I : Xi = 0] ≤

Y

Pr[Xi = 0].

i∈I

Finally, we call X1 , . . . , Xn negatively correlated if they are both 0-negatively correlated and 1-negatively correlated.
In simple words, these conditions require that the event that a set of variables
is all zero or all one, is at most as likely as in the case of independent random
variables. It seems natural that sums of such random variables are at least as
strongly concentrated as independent random variable, and in fact, Panconesi and
Srinivasan [PS97] were able to prove that negatively correlated random variables
admit Chernoff bounds. To be precise, they only proved that 1-negative correlation implies Chernoff bounds for the upper tail, but it is not too difficult to show
(see below) that the main argument works for all bounds proven via Bernstein’s
exponential moments method. In particular, for sums of 1-negatively correlated
random variable we obtain all Chernoff bounds for the upper tail that were presented in this work for independent random variables (as far as they can be applied
to binary random variables). We prove a slightly more general result as this helps
arguing that we can also work with upper bounds for the expectation instead of the
precise expectation. Further below, we then use a symmetry argument to argue
that 0-negative correlation implies all lower tail bounds presented so far.
Theorem 68 (1-negative correlation implies upper tail bounds). Let X1 , . . . , Xn
be 1-negatively correlated binary random variables. Let a1 , . . . , an , b1 , . . . , bn ∈ R
with ai ≤ bi for all i ∈ [1..n]. Let Y1 , . . . , Yn be random variables with Pr[Yi =
P
ai ] = Pr[Xi = 0] and Pr[Yi = bi ] = Pr[Xi = 1]. Let Y = ni=1 Yi .
55

(a) If a1 , . . . , an , b1 , . . . , bn ∈ [0, 1], then Y satisfies the Chernoff bounds given
in equations (29) to (33), (35) to (37), (41), (45) to (49), and (53) to (58),
P
where in the latter we use σ 2 := ni=1 Var[Yi ].

(b) Without the restriction to [0, 1] made in the previous paragraph, Y satisfies
the Chernoff bound of (43) with ci := bi − ai and the bounds of (59) to (62)
P
with σ 2 := ni=1 Var[Yi].

All these results also hold when E[Y ] is replaced by some µ+ ≥ E[Y ].

Proof. Let X1′ , . . . , Xn′ be independent binary random variables such that for all
i ∈ [1..n], the random variables Xi and Xi′ are identically distributed. Let ci :=
bi −ai for all i ∈ [1..n]. Note that Yi = ai +ci Xi for all i ∈ [1..n]. Let Yi′ = ai +ci Xi′ .
P
Let Y ′ = ni=1 Yi′ .
We first show that the 1-negative correlation of the Xi implies E[Y ℓ ] ≤ E[(Y ′ )ℓ ]
for all ℓ ∈ N0 . There is nothing to show for ℓ = 0 and
ℓ = 1, so let ℓ ≥ 2. Since

Pn
Pn
Pℓ
P
ℓ Pn
ℓ
Y = ( i=1 ai ) + ( i=1 ci Xi ), we have Y = k=0 k ( i=1 ai )ℓ−k ( ni=1 ci Xi )k . By
P
P
linearity of expectation, it suffices to show E[( ni=1 ci Xi )k ] ≤ E[( ni=1 ci Xi′ )k ].
P
P
Q
We have ( ni=1 ci Xi )k = (i1 ,...,ik )∈[1..n]k kj=1 cij Xij . Applying the definition of
1-negative correlation to the set I = {i1 , . . . , ik }, we compute
E

"

k
Y

j=1

#

cij Xij =

k
Y

j=1

≤
=

k
Y

!

cij Pr[∀j ∈ [1..k] : Xij = 1]
cij

j=1
k
Y

cij

j=1

!
!

Y

!

Pr[Xi = 1]

i∈I

Y

!

Pr[Xi′ = 1] = E

i∈I

"

k
Y

#

cij Xi′j .

j=1

Consequently, by linearity of expectation, E[( ni=1 ci Xi )k ] ≤ E[( ni=1 ci Xi′ )k ] for
all k ∈ N and thus E[Y ℓ ] ≤ E[(Y ′ )ℓ ].
We recall from Section 10.1.7 that essentially all large deviation bounds were
proven via upper bounds on the exponential moment E[ehY ]. Since the random
variable Y is bounded, by Fubini’s theorem we have
P

hY

E[e

∞
X

∞
X
hℓ Y ℓ
hℓ E[Y ℓ ]
]=E
=
.
ℓ!
ℓ=0 ℓ!
ℓ=0

"

#

′

P

(65)

Since E[Y ℓ ] ≤ E[(Y ′ )ℓ ], we have E[ehY ] ≤ E[ehY ]. Consequently, we obtain for Y
all Chernoff bounds which we could prove with the classic methods for Y ′ .
It remains to show that we can also work with an upper bound µ+ ≥ E[Y ].
For this, note that when we apply the construction of Theorem 66 to our random
56

variables Yi, that is, we define Zi = Yi + γ(1 − Yi ) for a suitable γ ∈ [0, 1], then the
resulting random variables Zi satisfy the same properties as the Yi, that is, there
are a′i and c′i such that Zi = a′i + c′i Xi . Consequently, we have Pr[Y ≥ (1 + δ)µ+ ] ≤
P
Pr[Z ≥ (1 + δ)µ+ ] = Pr[Z ≥ (1 + δ)E[Z]] for the sum Z = ni=1 Zi and the last
expression can bounded via the results we just proved.
Theorem 69 (0-negative correlation implies lower tail bounds). Let X1 , . . . , Xn
be 0-negatively correlated binary random variables. Let a1 , . . . , an , b1 , . . . , bn ∈ R
with ai ≤ bi for all i ∈ [1..n]. Let Y1 , . . . , Yn be random variables with Pr[Yi =
P
ai ] = Pr[Xi = 0] and Pr[Yi = bi ] = Pr[Xi = 1]. Let Y = ni=1 Yi .
(a) If a1 , . . . , an , b1 , . . . , bn ∈ [0, 1], then Y satisfies the Chernoff bounds given
in equations (38) to (40), (42), (50) to (52), and those in Corollary 59 with
P
σ 2 := ni=1 Var[Yi].

(b) Without the restriction to [0, 1] made in the previous paragraph, Y satisfies
the Chernoff bound of (44) with ci := bi − ai and those of the last paragraph
P
of Theorem 60 with σ 2 := ni=1 Var[Yi].

All these results also hold when E[Y ] is replaced by some µ− ≤ E[Y ].

Proof. Let Ỹi := 1 − Yi . Then the Ỹi satisfy the assumptions of Theorem 68 (with
ãi = 1 − bi , b̃i = 1 − ai , and X̃i = 1 − Xi ; note that the latter are 1-negatively
correlated since the Xi are 0-negatively correlated, note further that ãi , b̃i ∈ [0, 1] if
ai , bi ∈ [0, 1]). Hence Theorem 68 gives the usual Chernoff bounds for the Ỹi. As in
Section 10.1.2, these translate into the estimates (38) to (40) and these imply (50)
to (52). Bound (41) for the Ỹi immediately translates to (42) for the Yi . Finally, the
results of Theorem 58 imply those of Corollary 59. All these results are obviously
weaker when E[Y ] is replaced by some µ− ≤ E[Y ].
10.2.3

Hypergeometric Distribution

It remains to point out some situations where we encounter negatively correlated
random variables. One typical situations (but by far not the only one) is sampling
without replacement, which leads to the hypergeometric distribution.
Say we choose randomly n elements from a given N-element set S without
replacement. For a given m-element subset T of S, we wonder how many of
its elements we have chosen. This random variable is called hypergeometrically
distributed with parameters N, n and m.
More formally, let S be any N-element set. Let T ⊆ S have exactly m elements. Let U be a subset of S chosen uniformly among all n-element subsets of

57

S. Then X = |U ∩ T | is a random variable with hypergeometric distribution (with
parameters N, n and m). By definition,
Pr[X = k] =

 
m
k

N −m
n−k
 
N
n



for all k ∈ [max{0, n + m − N}.. min{n, m}].
||T |
It is easy to see that E[X] = |U|S|
= mn
: Enumerate T = {t1 , . . . , tm } in an
N
arbitrary manner (before choosing U). For i = 1, . . . , m, let Xi be the indicator
|
= Nn . Since
random variable for the event ti ∈ U. Clearly, Pr[Xi = 1] = |U
|S|
Pm
X = i=1 Xi , we have E[X] = mn
by linearity of expectation (Lemma 20).
N
It is also obvious that the Xi are not independent. If n < m and X1 = . . . =
Xn = 1, then necessarily we have Xi = 0 for i > n. Fortunately, however, these
dependencies are of the negative correlation type. This is intuitively clear, but
also straight-forward to prove.
Let I ⊆ [1..m], W = {ti | i ∈ I}, and w = |W | = |I|. Then Pr[∀i ∈ I : Xi =
1] = Pr[W ⊆ U]. Since U is uniformly
chosen, it suffices to count the number of

|S\W |
U that contain W , these are |U \W | , and to compare them with the total number
of possible U. Hence
N −w
Pr[W ⊆ U] =
n−w

!

N
n

!

n
n · . . . · (n − w + 1)
<
=
N · . . . · (N − w + 1)
N


w

=

Y

Pr[Xi = 1].

i∈I

In a similar fashion, we have
Pr[∀i ∈ I : Xi = 0] = Pr[U ∩ W = ∅]
!

!

N
N −w
=
n
n
(N − n) . . . (N − n − w + 1)
=
N . . . (N − w + 1)


N −n w Y
≤
=
Pr[Xi = 0],
N
i∈I





where we read N −w
= 0 when n < N − w.
n
Together with Theorems 68 and 69, we obtain the following theorem.
Theorem 70. Let N ∈ N. Let S be some set of cardinality N, for convenience,
S = [1..N]. Let n ≤ N and let U be a subset of S having cardinality n uniformly
chosen among all such subsets. For i ∈ [1..N] let Xi be the indicator random
variable for the event i ∈ U. Then X1 , . . . , XN are negatively correlated.
58

Consequently, if X is a random variable having a hypergeometric distribution
with parameters N, n, and m, then the usual Chernoff bounds for sums of n
independent binary random variables (listed in Theorems 68 and 69) hold.
Note that for hypergeometric distributions we have symmetry in n and m, that
is, the hypergeometric distribution with parameters N, n, and m is the same as
the hypergeometric distribution with parameters N, m, and n. Hence for Chernoff
bounds depending on the number of random variables, e.g., Theorem 53, we can
make this number being min{n, m} by interpreting the random experiment in the
right fashion.
That the hypergeometric distribution satisfies the Chernoff bounds of Theorem 53 has recently in some works been attributed to Chvátal [Chv79], but this is
not correct. As Chvátal writes, the aim of his note is solely to give an elementary
proof of the fact that the hypergeometric distribution satisfies the strongest Chernoff bound of Theorem 47 (which implies the bounds of Theorem 53), whereas the
result itself is from Hoeffding [Hoe63].
For a hypergeometric random variable X with parameters N, n, and m,
N
and z ≥ n2 , then Pr[X = z] ≤ ( 2em
)z . With
[BLS14] show that if m < 2e
N
Theorem 70, we can use the usual Chernoff bound of equation (46) and obtain the
stronger bound
z−E[X]

Pr[X ≥ z] ≤ e

E[X]
z

!z

≤

eE[X]
z

!z

enm
=
zN


z

,

(66)

)z for z ≥ n/2.
which is at most ( 2em
N
Theorem 70 can be extended to point-wise maxima of several families like (Xi )
in Theorem 70 if these are independent. This result was used in the analysis of a
population-based genetic algorithm in [DD17], but might be useful also in other
areas of discrete algorithmics.
Lemma 71. Let k, N ∈ N. For all j ∈ [1..k], let nj ∈ [1..N]. Let S be some
set of cardinality N, for convenience, S = [1..N]. For all j ∈ [1..k], let Uj be a
subset of S having cardinality nj uniformly chosen among all such subsets. Let
the Uj be stochastically independent. For all i ∈ S, let Xi be the indicator random
variable for the event that i ∈ Uj for some j ∈ [1..k]. Then the random variables
X1 , . . . , XN are negatively correlated.
Note that the situation in the lemma above can be seen as sampling with partial
P
replacement. We sample a total of j nj elements, but we replace the elements
chosen only after round n1 , n1 + n2 , ... We expect that other partial replacement
scenarios also lead to negatively correlated random variables, and thus to the usual
Chernoff bounds.
59

We remark that negative correlation can be useful also without Chernoff
bounds. For example, in Section 9 we used the lemma above to prove a lower
bound on the coupon collector time (equivalently, on the runtime of the randomized local search heuristic on monotonic fuctions).

10.3

Chernoff Bounds for Functions of Independent Variables, Martingales, and Bounds for Maxima

So far we discussed tail bounds for random variables which can be written as sum
of (more or less) independent random variables. Sometimes, the random variable
we are interested in is determined by the outcomes of many independent random
variables, however, not simply as a sum of these. Nevertheless, if each of the
independent random variables only has a limited influence on the outcome, then
bounds similar to those of Theorem 55 can be proven. Such bounds can be found
under the names Azuma’s inequality, Martingale inequalities, or method of bounded
differences.
We shall try to avoid the use of martingales, which need some deeper understanding of probability theory, and first present two bounds due to McDiarmid [McD98] that need martingales in their proof, but not in their statement.
Theorem 72 (Method of bounded differences). Let X1 , . . . , Xn be independent
random variables taking values in the sets Ω1 , . . . , Ωn , respectively. Let Ω := Ω1 ×
. . . × Ωn . Let f : Ω → R. For all i ∈ [1..n] let ci > 0 be such that for all ω, ω̄ ∈ Ω
we have that if for all j 6= i, ωj = ω̄j , then |f (ω) − f (ω̄)| ≤ ci .
Let X = f (X1 , . . . , Xn ). Then for all λ ≥ 0,
Pr[X ≥ E[X] + λ] ≤ exp
Pr[X ≤ E[X] − λ] ≤ exp

2λ2

− Pn

!

2
i=1 ci
!
2

2λ
− Pn

2
i=1 ci

,
.

The version of Azuma’s inequality given above is due to McDiarmid [McD98]
P
and is stronger than the bound exp(−λ2 /2 ni=1 c2i ) given by several other authors.
Theorem 72 found numerous applications in discrete mathematics and computer science, however, only few in the analysis of randomized search heuristics
(the only one we are aware of is [BD17]). All other analyses of randomized search
heuristics that needed Chernoff-type bounds for random variables that are determined by independent random variables, but in a way other than as simple sum,
resorted to the use of martingales.
One reason for this might be that the bounded differences assumption is easily proven in discrete mathematics problems like the analysis of random graphs,
60

whereas in algorithms the sequential nature of the use of randomness may make
it hard to argue that a particular random variable sampled now has a bounded
influence on the final result regardless of how we condition on all future random
variables. A more natural condition might be that the outcome of the current
random variable has only a limited influence on the expected result determined by
the future random variables. For this reason, we are optimistic that the following
result might become useful in the analysis of randomized search heuristics. This
result is a weak version of Theorem 3.7 in [McD98].
Theorem 73 (Method of bounded conditional expectations). Let X1 , . . . , Xn be
independent random variables taking values in the sets Ω1 , . . . , Ωn , respectively.
Let Ω := Ω1 × . . . × Ωn . Let f : Ω → R. For all i ∈ [1..n] let ci > 0 be such that
for all ω1 ∈ Ω1 , . . . , ωi−1 ∈ Ωi−1 and all ωi , ω̄i ∈ Ωi we have
|E[f (ω1 , . . . , ωi−1 , ωi , Xi+1 , . . . , Xn )] − E[f (ω1 , . . . , ωi−1, ω̄i , Xi+1 , . . . , Xn )]| ≤ ci .
Let X = f (X1 , . . . , Xn ). Then for all λ ≥ 0,
Pr[X ≥ E[X] + λ] ≤ exp
Pr[X ≤ E[X] − λ] ≤ exp

λ2

!

− Pn 2 ,
2 i=1 ci
!
λ2
− Pn 2 .
2 i=1 ci

Here is an example of how the new theorem can be helpful. The compact
genetic algorithms (cGA) maximizes a function f : {0, 1}n → R as follows. There
is a (hypothetical) population size K ∈ N, which we assume to be an even integer.
The cGA sets the initial frequency vector τ (0) ∈ [0, 1]n to τ (0) = ( 21 , . . . , 12 ). Then,
in each iteration t = 1, 2, . . . it generates two search points x(t,1) , x(t,2) ∈ {0, 1}n
randomly such that, independently for all j ∈ {1, 2} and i ∈ [1..n], we have
(t,j)
(t)
Pr[xi = 1] = τi . If f (x(t,1) ) < f (x(t,2) ), then we swap the two variables, that
is, we set (x(t,1) , x(t,2) ) ← (x(t,2) , x(t,1) ). Finally, in this iteration, we update the
frequency vector by setting τ (t+1) ← τ (t) + K1 (x(t,1) − x(t,2) ).
(t)
Let us analyze the behavior of the frequency τi of a neutral bit i ∈ [1..n], that
(t)
is, one that has no influence on the fitness. To ease reading, let Xt := τi . We
have X0 = 12 with probability one. Once Xt is determined, we have
Pr[Xt+1 = Xt + K1 ] = Xt (1 − Xt ),
Pr[Xt+1 = Xt − K1 ] = Xt (1 − Xt ),
Pr[Xt+1 = Xt ] = 1 − 2Xt (1 − Xt ).
In particular, we have E[Xt+1 | X0 , . . . , Xt ] = E[Xt+1 | Xt ] = Xt . By induction,
we have E[XT | Xt ] = Xt for all T > t.
61



2



K
, XT has
Our aim is to show that with probability at least 1 − 2 exp − 32T
not yet converged to one of the absorbing states 0 and 1. We first write the
frequencies as results of independent random variables. For convenience, these
will be continuous random variables, but it is easy to see that instead we could
have used discrete ones as well. For all t = 1, 2, . . . let Rt be a random number
uniformly distributed in the interval [0, 1]. Define Y0 , Y1 , . . . as follows. We have
Y0 = 12 with probability one. For t ∈ N0 , we set

Pr[Yt+1 = Yt + K1 ] if Rt ≥ 1 − Yt (1 − Yt ),
Pr[Yt+1 = Yt − K1 ] if Rt ≤ Yt (1 − Yt ),
Pr[Xt+1 = Xt ] else.
It is easy to see that (X0 , X1 , . . . ) and (Y0 , Y1, . . . ) are identically distributed.
Note that YT is a function g of (R1 , . . . , RT ). For concrete values r1 , . . . , rt ∈
[0, 1], we have E[g(r1, . . . , rt , Rt+1 , . . . , RT )] = E[YT | Yt ] = Yt . Consequently,
for all r t ∈ [0, 1], the two expectations E[g(r1, . . . , rt−1 , rt , Rt+1 , . . . , RT )] and
E[g(r1, . . . , rt−1 , rt , Rt+1 , . . . , RT )] are two possible outcomes of Yt given a common value for Yt−1 (which is determined by r1 , . . . , rt−1 ), and hence differ by at
most ct = K2 . We can thus apply Theorem 73 as follows.
h

Pr[YT ∈ {0, 1}] = Pr |YT − 12 | ≥
h

1
2

i

= Pr |g(R1 , . . . , RT ) − E[g(R1, . . . , RT )]| ≥

( 1 )2
≤ 2 exp − 2 2 2
2T ( K )

!

K2
= 2 exp −
32T

!

1
2

i

.

Note that it is not obvious how to obtain this result with the classic method
of bounded differences (Theorem 72). In particular, the above construction does
not satisfy the bounded differences condition, that is, there are values r1 , . . . , rT
and rt such that g(r1 , . . . , rT ) and g(r1 , . . . , rt−1 , r t , rt+1 , . . . , rT ) differ by significantly more than K2 . For this reason, we are optimistic that Theorem 73 will find
applications in the theory of randomized search heuristics.
Both Theorem 72 and 73 are special cases of the following martingale result,
which is often attributed to Azuma [Azu67] despite the fact that it was proposed
already in Hoeffding [Hoe63].
Theorem 74 (Azuma-Hoeffding inequality). Let X0 , X1 , . . . , Xn be a martingale.
Let c1 , . . . , cn > 0 with |Xi − Xi−1 | ≤ ci for all i ∈ [1..n]. Then for any λ ≥ 0,
Pr[Xn − X0 ≥ λ] ≤ exp
62

λ2

!

− Pn 2 .
2 i=1 ci

This result has found several applications in the theory of randomized search
heuristics, e.g., in [DK15, Köt16, DDY16b].
We note that the theorem above is a direct extension of Theorem 55 to Martingales. In a similar vein, there are Martingale versions of most other Chernoff
bounds presented in this work. We refer to McDiarmid [McD98] for more details.
Tail bounds for maxima and minima of partial sums: We end this section
with a gem already contained in Hoeffding. It builds on the following elementary
observation: If X0 , X1 , . . . , Xn is a martingale, then Y0 , Y1 , . . . , Yn defined as follows
also forms a martingale. Let λ ∈ R. Let i ∈ [0..n] minimal with Xi ≥ λ, if such
an Xi exists, and i = n + 1 otherwise. Let Yj = Xj for j ≤ i and Yj = Xi
for j > i. Then Yn ≥ λ if and only if maxi∈[1..n] Xi ≥ λ. Since Y0 , . . . , Yn is a
martingale with martingales differences bounded as least as well as for X0 , . . . , Xn
(and also all other variation measures at least as good as for X0 , . . . , Xn ), all large
deviation bounds provable for the martingale X0 , . . . , Xn via the Bernstein method
are valid also for Y0 , . . . , Yn , that is, for maxi∈[1..n] Xi . Since we did not introduce
martingales here, we omit the details and only state some implications of this
observation. The reader finds more details in [Hoe63, end of Section 2] and [McD98,
end of Section 3.5]. It seems that both authors do not see this extension as very
important (see also the comment at the end of Section 2 in [McD98]). We feel that
this might be different for randomized search heuristics. For example, to prove
that a randomized search heuristic has at least some optimization time T , we need
to show that the distance of each of the first T − 1 solutions from the optimum is
positive, that is, that the minimum of these differences is positive.
Theorem 75 (Tail bounds for maxima and minima). Let X1 , . . . , Xn be indepenP
dent random variables. For all i ∈ [1..n], let Si = ij=1 Xi . Assume that one of
the results in Section 10.1 yields the tail bound Pr[Sn ≥ E[Sn ] + λ] ≤ p. Then we
also have
Pr[∃i ∈ [1..n] : Si ≥ E[Si ] + λ] ≤ p.
(67)
In an analogous manner, each tail bound Pr[Sn ≤ E[Sn ] − λ] ≤ p derivable from
Section 10.1 can be strengthened to Pr[∃i ∈ [1..n] : Si ≤ E[Si ] − λ] ≤ p.
Note that if the Xi in the theorem are non-negative, then trivially equation (67)
implies the uniform bound
Pr[∃i ∈ [1..n] : Si ≥ E[Sn ] + λ] ≤ p.

(68)

Note also that the deviation parameter λ does not scale with i. In particular, a
bound like Pr[∃i ∈ [1..n] : Si ≥ (1 + δ)E[Si ]] ≤ p cannot be derived.
63

10.4

Chernoff Bounds for Geometric Random Variables

As visible from Lemma 80 below, sums of independent geometric random variables
occur frequently in the analysis of randomized search heuristics. Surprisingly, it
was only in 2007 that a Chernoff-type bound was used to analyze such sums
in the theory of randomized search heuristics [DHK07] (for subsequent uses see,
e.g., [BBD+ 09, DHK11, ZLLH12, DJWZ13, DD17]). Even more surprisingly, only
recently Witt [Wit14] proved good tail bounds for sums of geometric random
variables having significantly different success probabilities. Note that geometric
random variables are unbounded. Hence the Chernoff bounds presented so far
cannot be applied directly.
We start this subsection with simple Chernoff bounds for sums of identically
distributed geometric random variables as these can be derived from Chernoff
bounds for sums of independent 0, 1 random variables discussed so far. We remark
that a sum X of n independent geometric distributions with success probability
p > 0 is closely related to the negative binomial distribution NB(n, 1 − p) with
parameters n and 1 − p: We have X ∼ NB(n, 1 − p) + n.
Theorem 76. Let X1 , . . . , Xn be independent geometric random variables with
P
common success probability p > 0. Let X := ni=1 Xi and µ := E[X] = np .
(a) For all δ ≥ 0,

δ2 n − 1
Pr[X ≥ (1 + δ)µ] ≤ exp −
2 1+δ

!

1
≤ exp − min{δ 2 , δ}(n − 1) .
4
(69)




(b) For all 0 ≤ δ ≤ 1,
(1 − δ)(µ − n)
Pr[X ≤ (1 − δ)µ] ≤ (1 − δ)
(1 − δ)µ − n
≤ (1 − δ)n exp(δn)
n

2

≤ exp −

!(1−δ)µ−n

!

δ n
,
2 − 43 δ

(70)
(71)
(72)

where the first bound reads as pn for (1 − δ)µ = n and as 0 for (1 − δ)µ < n.
For 0 ≤ δ < 1, we also have
2δ 2 pn
,
Pr[X ≤ (1 − δ)µ] ≤ exp −
(1 − δ)
!
2p3 λ2
Pr[X ≤ µ − λ] ≤ exp −
.
n
!

64

(73)
(74)

Bounds (73) and (74) are interesting only for relatively large values of p. Since
part (a) has been proven in [BBD+ 09], we only prove (b). The main idea in both
cases is exploiting the natural relation between a sum of independent identically
distributed geometric random variables and a sequence of Bernoulli events.
Proof. Let Z1 , Z2 , . . . be independent binary random variables with Pr[Zi = 1] = p
P
for all i ∈ N. Let n < K ≤ np . Let YK = K
i=1 Zi . Then X ≤ K if and only if
YK ≥ n. Consequently, by Theorem 47,
Pr[X ≤ K] = Pr[YK ≥ n]
"

n
= Pr YK ≥ 1 +
−1
Kp

!!

#

E[YK ]

Kp n K − Kp K−n
n
K−n


Kp n
exp(n − Kp)
≤
n
!
pλ2
≤ exp
,
2K + 32 λ
≤



 



where we used the shorthand λ := µ − K for the absolute deviation. From Theorem 53, we derive
Pr[X ≤ K] = Pr[YK ≥ n]
= Pr[YK ≥ E[YK ] + (n − Kp)]

2(n − Kp)2
≤ exp −
K
!
!
2p2 λ2
2p2 λ2
≤ exp −
.
= exp −
µ−λ
µ
!

Replacing K by (1 − δ)µ and λ by δµ in these equations gives the claim.
When the geometric random variables have different success probabilities, the
following bounds can be employed.
Theorem 77. Let X1 , . . . , Xn be independent geometric random variables with
success probabilities p1 , . . . , pn > 0. Let pmin := min{pi | i ∈ [1..n]}. Let X :=
Pn
Pn 1
i=1 Xi and µ = E[X] =
i=1 pi .

65

(a) For all δ ≥ 0,
1
(1 − pmin)µ(δ−ln(1+δ))
1+δ
≤ exp(−pmin µ(δ − ln(1 + δ)))

Pr[X ≥ (1 + δ)µ] ≤

!n

δµpmin
exp(−δµpmin )
n
!
(δµpmin)2
.
≤ exp −
2n(1 + δµpnmin )
≤ 1+

(75)
(76)
(77)
(78)

(b) For all 0 ≤ δ ≤ 1,
Pr[X ≤ (1 − δ)µ] ≤ (1 − δ)pminµ exp(−δpmin µ)

(79)

≤ exp −

!

(80)

≤ exp(− 12 δ 2 µpmin ).

(81)

δ 2 µpmin
2 − 34 δ

Estimates (75) and (76) are from [Jan17], bound (77) is from [Sch00], and (78)
follows from the previous by standard estimates. Consequently, these bounds
are not only more general, but also stronger than our elementary bound (69) for
identically distributed geometric random variables.
For the lower tail bounds, (79) from [Jan17] is identical to (71) for identically distributed variables. Hence (70) is the strongest estimate for identically
distributed geometric random variables. Equation (79) gives (80) via the same
estimate that gives (72) from (71). Estimate (81) appeared already in [Sch00].
Overall, it remains surprising that such useful bounds were proven only relatively late and have not yet appeared in a scientific journal.
The bounds of Theorem 77 allow the geometric random variables to have different success probabilities, however, the tail probability depends only on the smallest
of them. This is partially justified by the fact that the corresponding geometric
random variable has the largest variance, and thus might be most detrimental to
the desired strong concentration. If the success probabilities vary significantly,
however, then this approach gives overly pessimistic tail bounds. Witt [Wit14]
proves the following result, which can lead to stronger estimates.
Theorem 78. Let X1 , . . . , Xn be independent geometric random variables with
P
P
success probabilities p1 , . . . , pn > 0. Let X = ni=1 Xi , s = ni=1 ( p1i )2 , and pmin :=

66

min{pi | i ∈ [1..n]}. Then for all λ ≥ 0,
λ2
1
, λpmin
Pr[X ≥ E[X] + λ] ≤ exp − min
4
s
!
λ2
Pr[X ≤ E[X] − λ] ≤ exp −
.
2s
(

)!

,

(82)
(83)

In the analysis of randomized search heuristics, apparently we often encounter
sums of independent geometrically distributed random variables X1 , . . . , Xn with
success probabilities pi proportional to i. For this case, the following result
from [DD17] gives stronger tail bounds than the previous result. See Section 4.2
for the definition of the harmonic number Hn .
Theorem 79. Let X1 , . . . , Xn be independent geometric random variables with
success probabilities p1 , . . . , pn . Assume that there is a number C ≤ 1 such that
P
pi ≥ C ni for all i ∈ [1..n]. Let X = ni=1 Xi . Then
E[X] ≤

1
nHn
C

Pr[X ≥ (1 +

≤

1
n(1
C

+ ln n),

δ) C1 n ln n]

−δ

≤n

(84)

for all δ ≥ 0.

(85)

As announced in Section 8.2, we now present a few examples where the existing
literature only gives an upper bound for the expected runtime, but where a closer
look at the proofs easily gives more details about the distribution, which in particular allows to obtain tail bounds for the runtime. We note that similar results so
far have only been presented for the (1 + 1) EA optimizing the LeadingOnes test
function [DJWZ13] and for RLS optimizing the OneMax test function [Wit14].
Zhou et al. [ZLLH12] implicitly give several results of this type, however, the resulting runtime guarantees are not optimal due to the use of an inferior Chernoff
bound for geometric random variables.
Lemma 80. (a) The runtime T of the (1 + 1) EA on the OneMax function is
P
i
dominated by the independent sum ni=1 Geom( en
) [DJW02]. Hence E[T ] ≤
−δ
enHn and Pr[T ≥ (1 + δ)en ln n] ≤ n for all δ ≥ 0.
(b) For any function f : {0, 1}n → R, the runtime T of the (1 + 1) EA is
dominated by Geom(n−n ) [DJW02]. Hence E[T ] ≤ nn and Pr[T ≥ γnn ] ≤
n
(1 − n−n )γn ≤ e−γ for all γ ≥ 0.
(c) The runtime T of the (1 + 1) EA finding Eulerian
graphs using perfect matchings in the adjacency lists
ing the edge-based mutation operator is dominated by
Pm/3
i
Hence E[T ] ≤ 2emHm/3
i=1 Geom( 2em ) [DJ07].
δ)em ln m3 ] ≤ ( m3 )−δ for all δ ≥ 0.
67

cycles in undirected
as genotype and usthe independent sum
and Pr[T ≥ 2(1 +

(d) The runtime of the (1 + 1) EA sorting an array of length n by minimizing the number of inversions is dominated by the independent sum
 
P(n2 )
4e n
3i
H(n) ≤ 2e
n2 (1 + 2 ln n)
)
[STW04].
Hence
E[T
]
≤
Geom(
i=1
3 2
3
4e(n
2
2)
and Pr[T ≥ (1 + δ) 4e
n2 ln n] ≤
3

 −δ
n
2

.

(e) The runtime of the multi-criteria (1 + 1) EA for the single-source shortest
path problem in a graph G can be described as follows. Let ℓ be such that
there is a shortest path from the source to any vertex having at most ℓ edges.
Then there are random variables Gij , i ∈ [1..ℓ], j ∈ [1..n − 1], such that
(i) Gij ∼ Geom( en12 ) for all i ∈ [1..ℓ] and j ∈ [1..n − 1], (ii) for all j ∈
[1..n−1] the variables G1j , . . . , Gℓj are independent, and (iii) T is dominated
P
by max{ ℓi=1 G
| j ∈ [1..n − 1]} [STW04, DHK11]. Consequently, for δ =
qij
4 ln(n−1)
4 ln(n−1)
1
} and T0 := (1 + δ) pℓ , we have E[T ] ≤ (1 + ln(n−1)
)T0
max{ ℓ−1 ,
ℓ−1
−ε
and Pr[T ≥ (1 + ε)T0 ] ≤ (n − 1) for all ε ≥ 0.
Proof. We shall not show the domination statements as these can be easily derived
from the original analyses cited in the theorem. Given the domination result,
parts (a), (c), and (d) follow immediately from Theorem 79. Part (b) follows
directly from the law of the geometric distribution.
To prove part (e), let X1 , . . . , Xℓ be independent geometrically distributed
Pℓ
random variables with parameter p = en1 2 . Let X =
Let δ =
i=1 Xi .
q

2

δ
max{ 4 ln(n−1)
, 4 ln(n−1)
}. Then, by (69), Pr[X ≥ (1 + δ)E[X]] ≤ exp(− 12 1+δ
(ℓ −
ℓ−1
ℓ−1
1 4 ln(n−1)
1
1
2
1)) ≤ exp(− 4 min{δ , δ}(ℓ − 1)) ≤ exp(− 4 ℓ−1 (ℓ − 1)) = n−1 . For all ε > 0,
again by (69), we compute

1 (δ + ε + δε)2
Pr[X ≥ (1 + ε)(1 + δ)E[X]] ≤ exp −
(ℓ − 1)
2 (1 + δ)(1 + ε)
!
1 δ 2 (1 + ε)2
(ℓ − 1)
≤ exp −
2 (1 + δ)(1 + ε)
!

!1+ε

1 δ2
≤ exp −
(ℓ − 1)
21+δ

≤ (n − 1)−(1+ε) .

Let Y1 , . . . , Yn−1 be random variables with distribution equal to the one of X. We
do not make any assumption on the correlation of the Yi , in particular, they do
not need to be independent. Let Y = max{Yi | i ∈ [1..n − 1]} and recall that
the runtime T is dominated by Y . Let T0 = (1 + δ)E[X] = (1 + δ) pℓ . Then
Pr[Y ≥ (1 + ε)T0 ] ≤ (n − 1) Pr[X ≥ (1 + ε)T0 ] ≤ (n − 1)−ε by the union bound

68

(Lemma 12). By Corollary 18,
!

1
T0 .
E[Y ] ≤ 1 +
ln(n − 1)
We note that not all classic proofs reveal details on the distribution. For
results obtained via random walk arguments, e.g., the optimization of the short
path function SPCn [JW01], monotone polynomials [WW05], or vertex covers on
paths-like graphs [OHY09], as well as for results proven via additive drift [HY01],
the proofs often give little information about the runtime distribution (an exception
is the analysis of the needle and the OneMax function in [GKS99]).
For results obtained via the average weight decrease method [NW07] or multiplicative drift analysis [DG13], the proof also does not give information on
the runtime distribution. However, the probabilistic runtime bound of type
Pr[T ≥ T0 + λ] ≤ (1 − δ)λ obtained from these methods implies that the runtime is dominated by T  T0 − 1 + Geom(1 − δ).

10.5

Tail Bounds for the Binomial Distribution

For binomially distributed random variables, slightly stronger tail bounds exist.
The difference is small, but since they have been used in the analysis of randomized
search heuristics, we briefly describe them here.
In this section, let X always be a binomially distributed random variable with
P
parameters n and p, that is, X = ni=1 Xi with independent Xi satisfying Pr[Xi =
1] = p and Pr[Xi = 0] = 1 − p. The following estimate seems well-known (e.g., it
was used in [JJW05] without proof or reference). Gießen and Witt [GW17] give an
elementary proof via estimates of binomial coefficients and the binomial identity.
We find the proof below more intuitive.
Lemma 81. Let X ∼ Bin(n, p). Let k ∈ [0..n]. Then
!

n k
p .
Pr[X ≥ k] ≤
k
Proof. For all T ⊆ [1..n] with |T | = k let AT be the event that Xi = 1 for all
i ∈ T . Clearly, Pr[AT ] = pk . The event “X ≥ k” is the
  union of the events AT
P
with T as above. Hence Pr[X ≥ k] ≤ T Pr[AT ] = nk pk by the union bound
(Lemma 12).
 

)k , which often is an apWhen estimating the binomial coefficient by nk ≤ ( en
k
propriate way to derive more understandable expressions, the above bound reverts
69

to equation (35), a slightly weaker version of the classic multiplicative bound (30).
Since we are not aware of an application of Lemma 81 that does not estimate the
binomial coefficient in this way, its main value might be its simplicity.
The following tail bound for the binomial distribution was shown by
Klar [Kla00], again with elementary arguments. In many cases, it is significantly
stronger than Lemma 81. However, again we do not see an example where this tail
bound would have improved an existing analysis of a randomized search heuristics.
Lemma 82. Let X ∼ Bin(n, p) and k ∈ [np..n]. Then
Pr[X ≥ k] ≤

(k + 1)(1 − p)
Pr[X = k].
k + 1 − (n + 1)p

Note that, trivially, Pr[X = k] ≤ Pr[X ≥ k], so it is immediately clear that this
(k+1)(1−p)
). With elementary
estimate is quite tight (the gap is at most the factor k+1−(n+1)p
arguments, Lemma 82 gives the slightly weaker estimate
Pr[X ≥ k] ≤

k − kp
Pr[X = k],
k − np

(86)

which appeared also in [Fel68, equation (VI.3.4)]. For p = n1 , the typical mutation
rate in standard-bit mutation, Lemma 82 gives
Pr[X ≥ k] ≤

k+1
Pr[X = k].
k

(87)

1 n−k
)
Pr[X = k] and
Writing Lemma 81 in the equivalent form Pr[X ≥ k] ≤ ( 1−p
1 n−k
noting that ( 1−p )
≥ exp(p(n − k)), we see that in many cases Lemma 82 gives
substantially better estimates.

References
[Azu67]

Kazuoki Azuma. Weighted sums of certain dependent variables. Tohoku Mathematical Journal, 3:357–367, 1967.

[BBD+ 09]

Surender Baswana, Somenath Biswas, Benjamin Doerr, Tobias
Friedrich, Piyush P. Kurur, and Frank Neumann. Computing single
source shortest paths using single-objective fitness. In 10th Workshop
on Foundations of Genetic Algorithms, FOGA 2009, pages 59–66.
ACM, 2009.

[BD17]

Maxim Buzdalov and Benjamin Doerr. Runtime analysis of the
(1 + (λ, λ)) genetic algorithm on random satisfiable 3-CNF formulas. In Genetic and Evolutionary Computation Conference, GECCO
70

2017, pages 1343–1350. ACM, 2017.
http://arxiv.org/abs/1704.04366.

Full version available at

[BDN10]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. Optimal
fixed and adaptive mutation rates for the LeadingOnes problem. In
11th International Conference on Parallel Problem Solving from Nature, PPSN 2010, pages 1–10. Springer, 2010.

[BE08]

Pavel A. Borisovsky and Anton V. Eremeev. Comparing evolutionary
algorithms to the (1+1)-EA. Theoretical Computer Science, 403:33–
41, 2008.

[Ben62]

George Bennett. Probability inequalities for the sum of independent
random variables. Journal of the American Statistical Association,
57:33–45, 1962.

[Ber24]

Sergey N. Bernstein. On a modification of Chebyshev’s inequality
and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine,
Sect. Math. 1, 4:38–49, 1924.

[Bie53]

Irénée-Jules Bienaymé. Considérations à l’appui de la découverte de
Laplace. Comptes Rendus de l’Académie des Sciences, 37:309–324,
1853.

[BLS14]

Golnaz Badkobeh, Per Kristian Lehre, and Dirk Sudholt. Unbiased
black-box complexity of parallel search. In Parallel Problem Solving
from Nature, PPSN 2014, pages 892–901. Springer, 2014.

[CDEL16]

Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. Level-based analysis of genetic algorithms and other
search processes. CoRR, abs/1407.7663v2, 2016.

[Che52]

Herman Chernoff. A measure of asymptotic efficiency for tests of a
hypothesis based on the sum of observations. Annals of Mathematical
Statistics, 23:493–507, 1952.

[Chv79]

Vasek Chvátal. The tail of the hypergeometric distribution. Discrete
Mathematics, 25:285–287, 1979.

[DD16]

Benjamin Doerr and Carola Doerr. The impact of random initialization on the runtime of randomized search heuristics. Algorithmica,
75:529–553, 2016.

71

[DD17]

Benjamin Doerr and Carola Doerr. Optimal static and self-adjusting
parameter choices for the (1+(λ, λ)) genetic algorithm. Algorithmica,
2017. To appear.

[DDY16a]

Benjamin Doerr, Carola Doerr, and Jing Yang. k-bit mutation with
self-adjusting k outperforms standard bit mutation. In 14th International Conference on Parallel Problem Solving from Nature, PPSN
2016, pages 824–834. Springer, 2016.

[DDY16b]

Benjamin Doerr, Carola Doerr, and Jing Yang. Optimal parameter
choices via precise black-box analysis. In Genetic and Evolutionary
Computation Conference, GECCO 2016, pages 1123–1130. ACM,
2016.

[DFW10]

Benjamin Doerr, Mahmoud Fouz, and Carsten Witt. Quasirandom
evolutionary algorithms. In Genetic and Evolutionary Computation
Conference, GECCO 2010, pages 1457–1464. ACM, 2010.

[DFW11]

Benjamin Doerr, Mahmoud Fouz, and Carsten Witt. Sharp bounds
by probability-generating functions and variable drift. In Genetic
and Evolutionary Computation Conference, GECCO 2011, pages
2083–2090. ACM, 2011.

[DG13]

Benjamin Doerr and Leslie Ann Goldberg. Adaptive drift analysis.
Algorithmica, 65:224–250, 2013.

[DGWY17]

Benjamin Doerr, Christian Gießen, Carsten Witt, and Jing
Yang. The (1+λ) evolutionary algorithm with self-adjusting mutation rate.
In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 2017. Full version available at
http://arxiv.org/abs/1704.02191.

[DHK07]

Benjamin Doerr, Edda Happ, and Christian Klein. A tight bound
for the (1 + 1)-EA for the single source shortest path problem.
In Congress on Evolutionary Computation, CEC 2007, pages 1890–
1895. IEEE, 2007.

[DHK11]

Benjamin Doerr, Edda Happ, and Christian Klein. Tight analysis
of the (1+1)-EA for the single source shortest path problem. Evolutionary Computation, 19:673–691, 2011.

[DHK12]

Benjamin Doerr, Edda Happ, and Christian Klein. Crossover can
provably be useful in evolutionary computation. Theoretical Computer Science, 425:17–33, 2012.
72

[DJ07]

Benjamin Doerr and Daniel Johannsen. Adjacency list matchings:
an ideal genotype for cycle covers. In Genetic and Evolutionary
Computation Conference, GECCO 2007, pages 1203–1210. ACM,
2007.

[DJW02]

Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis
of the (1+1) evolutionary algorithm. Theoretical Computer Science,
276:51–81, 2002.

[DJW12]

Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. Algorithmica, 64:673–697, 2012.

[DJWZ13]

Benjamin Doerr, Thomas Jansen, Carsten Witt, and Christine
Zarges. A method to derive fixed budget results from expected optimisation times. In Genetic and Evolutionary Computation Conference, GECCO 2013, pages 1581–1588. ACM, 2013.

[DK15]

Benjamin Doerr and Marvin Künnemann. Optimizing linear functions with the (1+λ) evolutionary algorithm—different asymptotic
runtimes for different instances. Theoretical Computer Science,
561:3–23, 2015.

[DL15]

Duc-Cuong Dang and Per Kristian Lehre. Simplified runtime analysis of estimation of distribution algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2015, pages 513–518.
ACM, 2015.

[DLMN17]

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy
Nguyen. Fast genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 2017. Full version available at http://arxiv.org/abs/1703.03334.

[Doe11]

Benjamin Doerr. Analyzing randomized search heuristics: Tools
from probability theory. In Anne Auger and Benjamin Doerr, editors, Theory of Randomized Search Heuristics, pages 1–20. World
Scientific, 2011.

[Doe14]

Benjamin Doerr. A lower bound for the discrepancy of a random
point set. Journal of Complexity, 30:16–20, 2014.

[Doe17]

Benjamin Doerr. An elementary analysis of the probability that a
binomial random variable exceeds its expectation. ArXiv e-prints,
arXiv:1712.00519, 2017.
73

[Doe18]

Benjamin Doerr. Better runtime guarantees via stochastic domination. In Evolutionary Computation in Combinatorial Optimization,
EvoCOP 2018. Springer, 2018.

[dPdLDD15] Axel de Perthuis de Laillevault, Benjamin Doerr, and Carola Doerr.
Money for nothing: Speeding up evolutionary algorithms through
better initialization. In Genetic and Evolutionary Computation Conference, GECCO 2015, pages 815–822. ACM, 2015.
[DW14]

Benjamin Doerr and Carola Winzen. Ranking-based black-box complexity. Algorithmica, 68:571–609, 2014.

[Fei06]

Uriel Feige. On sums of independent random variables with unbounded variance and estimating the average degree in a graph.
SIAM Journal of Computing, 35:964–984, 2006.

[Fel68]

William Feller. An Introduction to Probability Theory and Its Applications, volume I. Wiley, third edition, 1968.

[GKS99]

Josselin Garnier, Leila Kallel, and Marc Schoenauer. Rigorous hitting times for binary mutations. Evolutionary Computation, 7:173–
203, 1999.

[GM14]

Spencer Greenberg and Mehryar Mohri. Tight lower bound on the
probability of a binomial exceeding its expectation. Statistics and
Probability Letters, 86:91–98, 2014.

[GW17]

Christian Gießen and Carsten Witt. The interplay of population size
and mutation probability in the (1 + λ) EA on OneMax. Algorithmica, 78:587–609, 2017.

[Hoe63]

Wassily Hoeffding. Probability inequalities for sums of bounded
random variables. Journal of the American Statistical Association,
58:13–30, 1963.

[HPR+ 14]

Hsien-Kuei Hwang, Alois Panholzer, Nicolas Rolin, Tsung-Hsi Tsai,
and Wei-Mei Chen. Probabilistic analysis of the (1+1)-evolutionary
algorithm. CoRR, abs/1409.4955, 2014.

[HY01]

Jun He and Xin Yao. Drift analysis and average time complexity of
evolutionary algorithms. Artificial Intelligence, 127:51–81, 2001.

[Jan17]

Swante Janson. Tail bounds for sums of geometric and exponential
variables. ArXiv e-prints, arXiv:1709.08157, 2017.
74

[JJW05]

Thomas Jansen, Kenneth A. De Jong, and Ingo Wegener. On the
choice of the offspring population size in evolutionary algorithms.
Evolutionary Computation, 13:413–440, 2005.

[JW01]

Thomas Jansen and Ingo Wegener. Evolutionary algorithms - how to
cope with plateaus of constant fitness and when to reject strings of
the same fitness. IEEE Transactions on Evolutionary Computation,
5:589–599, 2001.

[JW06]

Thomas Jansen and Ingo Wegener. On the analysis of a dynamic
evolutionary algorithm. Journal of Discrete Algorithms, 4:181–199,
2006.

[Kla00]

Bernhard Klar. Bounds on tail probabilities of discrete distributions.
Probability in the Engineering and Informational Sciences, 14:161–
171, 2000.

[Köt16]

Timo Kötzing. Concentration of first hitting times under additive
drift. Algorithmica, 75:490–506, 2016.

[KW17]

Martin S. Krejca and Carsten Witt. Lower bounds on the run time
of the univariate marginal distribution algorithm on OneMax. In
Foundations of Genetic Algorithms, FOGA 2017, pages 65–79. ACM,
2017.

[LN17]

Per Kristian Lehre and Phan Trung Hai Nguyen. Improved runtime bounds for the univariate marginal distribution algorithm via
anti-concentration. In Genetic and Evolutionary Computation Conference, GECCO 2017, pages 1383–1390. ACM, 2017.

[LOW17]

Andrei Lissovoi, Pietro Simone Oliveto, and John Alasdair Warwicker. On the runtime analysis of generalised selection hyperheuristics for pseudo-boolean optimisation. In Genetic and Evolutionary Computation Conference, GECCO 2017, pages 849–856.
ACM, 2017.

[LW12]

Per Kristian Lehre and Carsten Witt. Black-box search by unbiased
variation. Algorithmica, 64:623–642, 2012.

[LW14]

Per Kristian Lehre and Carsten Witt. Concentrated hitting times
of randomized search heuristics with variable drift. In 25th International Symposium on Algorithms and Computation, ISAAC 2014,
pages 686–697. Springer, 2014.
75

[McD98]

Colin McDiarmid. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, volume 16, pages 195–248. Springer,
Berlin, 1998.

[MS02]

Alfred Müller and Dietrich Stoyan. Comparison Methods for Stochastic Models and Risks. Wiley, 2002.

[MU05]

Michael Mitzenmacher and Eli Upfal. Probability and Computing—
Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.

[Nag01]

S. V. Nagaev. Lower bounds on large deviation probabilities for
sums of independent random variables. Theory of Probability and
Its Applications, 46:79–102, 2001.

[NSW10]

Frank Neumann, Dirk Sudholt, and Carsten Witt. A few ants are
enough: ACO with iteration-best update. In Genetic and Evolutionary Computation Conference, GECCO 2010, pages 63–70. ACM,
2010.

[NW07]

Frank Neumann and Ingo Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science, 378:32–40, 2007.

[OHY09]

Pietro Simone Oliveto, Jun He, and Xin Yao. Analysis of the (1+1)EA for finding approximate solutions to vertex cover problems. IEEE
Transactions on Evolutionary Computation, 13:1006–1029, 2009.

[OLN09]

Pietro Simone Oliveto, Per Kristian Lehre, and Frank Neumann.
Theoretical analysis of rank-based mutation - combining exploration
and exploitation. In Congress on Evolutionary Computation, CEC
2009, pages 1455–1462. IEEE, 2009.

[OW11]

Pietro Simone Oliveto and Carsten Witt. Simplified drift analysis
for proving lower bounds in evolutionary computation. Algorithmica,
59:369–386, 2011.

[OW12]

Pietro Simone Oliveto and Carsten Witt. Erratum: Simplified
drift analysis for proving lower bounds in evolutionary computation.
CoRR, abs/1211.7184, 2012.

[OW15]

Pietro Simone Oliveto and Carsten Witt. Improved time complexity analysis of the simple genetic algorithm. Theoretical Computer
Science, 605:21–41, 2015.
76

[PR16]

Christos Pelekis and Jan Ramon. A lower bound on the probability
that a binomial random variable is exceeding its mean. Statistics
and Probability Letters, 119:305–309, 2016.

[Pro56]

Yuri Prokhorov. Convergence of random processes and limit theorems in probability theory. Theory of Probability and Its Applications, 1:157–214, 1956.

[PS97]

Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding
bounds. SIAM Journal on Computing, 26:350–368, 1997.

[Rob55]

Herbert Robbins. A remark on Stirling’s formula. American Mathematical Monthly, 62:26–29, 1955.

[RT11]

Philippe Rigollet and Xin Tong. Neyman-Pearson classification, convexity and stochastic constraints. Journal of Machine Learning Research, 12:2831–2855, 2011.

[Sch00]

Christian Scheideler. Probabilistic Methods for Coordination Problems. University of Paderborn, 2000. Habilitation thesis. Available at
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.70.1319.

[Slu77]

Eric V. Slud. Distribution inequalities for the binomial law. Annals
of Probability, 5:404–412, 1977.

[ST12]

Dirk Sudholt and Christian Thyssen. A simple ant colony optimizer
for stochastic shortest path problems. Algorithmica, 64:643–672,
2012.

[STW04]

Jens Scharnow, Karsten Tinnefeld, and Ingo Wegener. The analysis
of evolutionary algorithms on sorting and shortest paths problems.
Journal of Mathematical Modelling and Algorithms, 3:349–366, 2004.

[Sud13]

Dirk Sudholt. A new method for lower bounds on the running time of
evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 17:418–435, 2013.

[SW16]

Dirk Sudholt and Carsten Witt. Update strength in EDAs and ACO:
how to avoid genetic drift. In Genetic and Evolutionary Computation Conference, GECCO 2016, pages 61–68. ACM, 2016. Extended
version CoRR abs/1607.04063.

[Tch67]

Pafnuty Tchebichef.
Des valeurs moyennes.
Journal de
mathématiques pures et appliquées, série 2, 12:177–184, 1867.
77

[Tch74]

Pafnuty Tchebichef. Sur les valeurs limites des intégrales. Journal
de mathématiques pures et appliquées, série 2, 19:157–160, 1874.

[Weg01]

Ingo Wegener. Theoretical aspects of evolutionary algorithms. In International Colloquium on Automata, Languages and Programming,
ICALP 2001, pages 64–78. Springer, 2001.

[Wit13]

Carsten Witt. Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability
& Computing, 22:294–318, 2013.

[Wit14]

Carsten Witt. Fitness levels with tail bounds for the analysis of randomized search heuristics. Information Processing Letters, 114:38–
41, 2014.

[Wit17]

Carsten Witt. Upper bounds on the runtime of the univariate
marginal distribution algorithm on onemax. In Genetic and Evolutionary Computation Conference, GECCO 2017, pages 1415–1422.
ACM, 2017.

[WW05]

Ingo Wegener and Carsten Witt. On the optimization of monotone
polynomials by simple randomized search heuristics. Combinatorics,
Probability & Computing, 14:225–247, 2005.

[ZLLH12]

Dong Zhou, Dan Luo, Ruqian Lu, and Zhangang Han. The use of
tail inequalities on the probable computational time of randomized
search heuristics. Theoretical Computer Science, 436:106–117, 2012.

78

