Collecting Coupons with Random Initial Stake
Benjamin Doerr1,2 , Carola Doerr2,3
1

arXiv:1308.6384v1 [cs.DM] 29 Aug 2013

2

École Polytechnique, Palaiseau, France
Max Planck Institute for Informatics, Saarbrücken, Germany
3
Université Paris Diderot - Paris 7, LIAFA, Paris, France
January 18, 2018

Abstract
Motivated by a problem in the theory of randomized search heuristics, we give a very
precise analysis for the coupon collector problem where the collector starts with a random
set of coupons (chosen uniformly from all sets).
We show that the expected number of rounds until we have a coupon of each type is
nHn/2 − 1/2 ± o(1), where Hn/2 denotes the (n/2)th harmonic number when n is even, and
Hn/2 := (1/2)H⌊n/2⌋ + (1/2)H⌈n/2⌉ when n is odd. Consequently, the coupon collector with
random initial stake is by half a round faster than the one starting with exactly n/2 coupons
(apart from additive o(1) terms).
This result implies that classic simple heuristic called randomized local search needs an
expected number of nHn/2 − 1/2 ± o(1) iterations to find the optimum of any monotonic
function defined on bit-strings of length n.

Keywords: Coupon Collector; Randomized Local Search; Runtime Analysis

1

Introduction

The coupon collector problem ask for how many coupons, chosen independently at random
from n different types, one needs to draw until one has a coupon of each type. It is well
known and easy to prove that this number equals nHn , where Hn denotes the nth harmonic
number Hn := 1 + 12 + 31 + . . . + n1 . The harmonic numbers are well understood. We have
1
± Θ(n−2 ), where γ ≈ 0.5772156649 . . . is the Euler-Mascheroni constant.
Hn = ln n + γ + 2n
Consequently, the coupon collector needs n ln n + γn + 1/2 ± o(1) rounds to finish.
If we assume that we start the coupon collector process being already in possession of k
different types of coupons, then the expected number of rounds becomes nHn−k , and again the
precise estimates for the harmonic numbers give very precise values for these numbers.
Motivated by works in the theory of randomized search heuristics (see the following section),
in this note we regard the coupon collector problem where we start with a random set of different
coupon types. In other words, at the start of the process we already have each type with
probability 1/2, mutually independent among all types. Since in expectation we start with n/2
different coupons and the actual number of different coupons is strongly concentrated around
this expectation, it seems natural that this coupon collector process should need roughly nHn/2
rounds, that is, roughly the same time as if we would assume that we start with exactly n/2
different coupons. In fact, this was shown recently, however, the bound is less precise than
the ones stated for the original coupon collector. In [2], Witt shows that the coupon collector
process with random initial setting takes an expected number of nHn/2 ± o(n) rounds to finish.
1

In this work, we derive a bound sharp up to additive o(1) terms. Interestingly, the answer
is by an additive term of 1/2 lower than nHn/2 .
Theorem 1. The coupon collector starting with a random set of different coupons takes nHn/2 −
1/2 ± o(1) = n ln(n/2) + γn + 1/2 ± o(1) rounds to finish, where Hn/2 is the (n/2)th harmonic
number when n is even, and Hn/2 := 12 H⌊n/2⌋ + 12 H⌈n/2⌉ when n is odd.
Before proving the theorem, we briefly describe the motivation for this coupon collector
variant stemming from the theory of randomized search heuristics.

2

Optimizing Monotonic Functions via Randomized Local
Search

Randomized Local Search (RLS) is a simple hill-climbing heuristic. When used to maximize
pseudo-Boolean functions f : {0, 1}n → R, RLS starts with a random initial search point
x ∈ {0, 1}n . In each iteration it creates from x a new search point (offspring) y by choosing
a position j ∈ [n] := {1, 2, . . . , n} uniformly at random and flipping in x the entry in the jth
position. It replaces x by y if and only if f (y) ≥ f (x), i.e., if and only if the objective value
(fitness) of y is at least as large as the fitness of x.
Algorithm 1: Randomized Local Search for maximizing f : {0, 1}n → R.
1
2
3
4
5

Initialization: Sample x ∈ {0, 1}n uniformly at random;
Optimization: for t = 1, 2, 3, . . . do
Choose j ∈ [n] uniformly at random;
Set y ← x ⊕ enj ; //mutation step
if f (y) ≥ f (x) then x ← y ; //selection step

A pseudo-Boolean function f : {0, 1} → R is called (strictly) monotonic if for all x, y ∈
{0, 1}n , we have f (x) < f (y) whenever x ≤ y (point-wise) and x 6= y. It is easy to see that RLS
optimizes all monotonic functions in an identical fashion. Since bits in x that are one never
change to zero, we in fact simulate a coupon collector process with random initial state. Since
the particular
P monotonic function is not important, often only the simple OneMax function
f : x 7→
i∈[n] xi , counting the number of ones, is regarded. Summarizing this discussion,
Theorem 1 is equivalent to the following statement.
Theorem 2. The expected number of iterations until RLS on OneMax or any other monotonic
function generates an optimal search point is nHn/2 − 1/2 ± o(1) = n ln(n/2) + γn + 1/2 ± o(1).

3

Proof of the Main Result

We first give the arguments for even values of n. The case of odd n will be dealt with at the
end of this section.
Even values of n. Let X be the random variable that describes the number of ones in the
initial search point. X is binomially distributed with parameters n and success probability 1/2.

2

The expected number of iterations until RLS on OneMax generates an optimal search point
can be written as
E[T ] =

n
X
i=0

E[T | X = i] Pr[X = i] .

(1)

By the definition of binomial distributions we have Pr[X = n/2 − a] = Pr[X = n/2 + a]
for all a ∈ [n/2]. The main idea of this proof is to show that the average runtime
1/2 (E[T | X = n/2 + a] + E[T | X = n/2 − a]) does not deviate from E[T | X = n/2] by much.
Let εa := 2 E[T | X = n/2] − (E[T | X = n/2 + a] + E[T | X = n/2 − a]). We can rewrite (1)
to
E[T ] = E[T | X = n/2] −

n/2
X

Pr[X = n/2 + a]εa .

(2)

a=1

Consequently, it suffices to show that
d :=

n/2
X
a=1

Pr[X = n/2 + a]εa = 1/2 ± o(1) .

Using the already mentioned fact that
E[T | X = k] =

n−1
X
i=k

n/(n − i) = n

n−k
X

1/i

i=1

we compute
εa = 2E[T | X = n/2] − (E[T | X = n/2 + a] + E[T | X = n/2 − a])


n/2
n/2−a
n/2+a
X
X
X
= 2n
1/i − n
1/i + n
1/i
i=1



i=1

n/2
X

= n

n/2+a

i=n/2−a+1

=n
=n

a−1 
X
i=0
a−1
X
i=0

i=1



1/i −

X

i=n/2+1

1/i

1
1
−
n/2 − i n/2 + i + 1



2i + 1
(n/2 − i)(n/2 + i + 1)

(3)

Consequently,
εa ≥ n
and thus d ≥

Pn/2

a=1 Pr[X
n/2
X
a=1

a−1
X
i=0

2i + 1
4a2
=
(n/2)2 + n/2
n+2

2

4a
= n/2 + a] n+2
. Fortunately,

2a2 Pr[X = n/2 + a] = E[(X − E[X])2 ] =: Var[X]
3

(4)

is just the variance of X, which is known to equal n/4, so we easily obtain the lower bound
d≥

2 Var[X]
n
=
= 1/2 − o(1) .
n+2
2(n + 2)

To bound the deviation d from above, using again (3) we estimate εa by
εa = n
≤n
≤n
=
Setting A :=

√

a−1
X

i=0
a−1
X
i=0

a−1
X
i=0

2i + 1
(n/2 − i)(n/2 + i + 1)
2i + 1
(n/2)2 − i2
2i + 1
− (a − 1)2

(n/2)2

na2
.
n2 /4 − (a − 1)2

cn ln n for a constant c to be fixed later, we split
d≤
≤

n/2
X

a=1
A
X

Pr[X = n/2 + a]

na2
n2 /4 − (a − 1)2

Pr[X = n/2 + a]

na2
n2 /4 − (A − 1)2

a=1

− Pr[X − n/2 > A]

(5)

n(n/2)2
.
n2 /4 − (n/2 − 1)2

We first bound the last term in this expression. Using Chernoff’s bound (see, e.g., [1]), it is
easy to see that
Pr[X − n/2 > A] ≤ exp(−2c ln(n)) = 1/n2c .
Furthermore,
n(n/2)2
≤ n3 .
n2 /4 − (n/2 − 1)2
Thus, for c > 3/2 the last term in (5) is clearly o(1).
For bounding the other terms we use again fact (4) and the equality Var[X] = n/4 to obtain
A
X
a=1

Pr[X = n/2 + a]

na2
n Var[X]
≤
n2 /4 − (A − 1)2
2(n2 /4 − (A − 1)2 )
=

n2
= 1/2 + o(1) .
2n2 − 8(A − 1)2

Plugging this back into (5), we obtain the upper bound
d ≤ 1/2 + o(1) .

4

Odd values of n. It remains to consider odd values of n. The computations are very similar
to the ones above. We keep the notation from the proof above, but we set, for 1 ≤ a ≤ ⌊n/2⌋
εa := E[T | X = ⌊n/2⌋] + E[T | X = ⌈n/2⌉] − (E[T | X = ⌊n/2⌋ − a] + E[T | X = ⌈n/2⌉ + a]) .
Similarly to (2) we have
⌊n/2⌋

E[T ] = 1/2 (E[T | X = ⌈n/2⌉] + E[T | X = ⌊n/2⌋]) −

X
a=1

Pr[X = ⌊n/2⌋ − a]εa

and we thus need to show that
⌊n/2⌋

X
a=1

Pr[X = ⌊n/2⌋ − a]εa = 1/2 ± o(1) .

Again similarly as above we bound εa from below


⌊n/2⌋
⌈n/2⌉+a
a−1
X
X
X


εa = n
1/i −
1/i = n
i=⌊n/2⌋−a+1

a−1
X

=n

i=0

i=0

i=⌈n/2⌉+1

2i + 2
(⌈n/2⌉ − (1 + i))(⌈n/2⌉ + 1 + i)

!

1
1
−
⌊n/2⌋ − i ⌈n/2⌉ + 1 + i

≥n

4(a2 + a)
a2 + a
=
(⌈n/2⌉)2 − 1
n + 2 − 3/n

and from above
εa ≤

4n(a2 + a)
.
n2 − 4a2

The variance equals again n/4 and can be written as
⌊n/2⌋

Var[X] =

X
a=0

2 Pr[X = ⌊n/2⌋ − a](a + 1/2)2

= 1/2 +

⌊n/2⌋

X

2 Pr[X = ⌊n/2⌋ − a](a2 + a)

X

2 Pr[X = ⌊n/2⌋ − a](a2 + a) .

a=0

⌊n/2⌋

= 1/2 +

a=1

Thus,
⌊n/2⌋

X
a=1

⌊n/2⌋

Pr[X = ⌊n/2⌋ − a]εa ≥

X
a=1

Pr[X = ⌊n/2⌋ − a]

= (Var[X] − 1/2)

4(a2 + a)
n + 2 − 3/n

2
= 1/2 − o(1)
n + 2 − 3/n

and
⌊n/2⌋

⌊n/2⌋

X
a=1

Pr[X = ⌊n/2⌋ − a]εa ≤

X
a=1

5

!

Pr[X = ⌊n/2⌋ − a]

4n(a2 + a)
.
n2 − 4a2

Splitting the sum as in the proof for even values of n shows the desired inequality
⌊n/2⌋

X
a=1

Pr[X = ⌊n/2⌋ − a]εa ≤ 1/2 + o(1) .

Acknowledgements. Carola Doerr is supported by a postdoctoral research fellowship of the
Alexander von Humboldt Foundation and by the Agence Nationale de la Recherche under the
project ANR-09-JCJC-0067-01.

References
[1] B. Doerr.
Analyzing randomized search heuristics: Tools from probability theory.
In A. Auger and B. Doerr, editors, Theory of Randomized Search
Heuristics, pages 1–20. World Scientific Publishing, 2011.
Available online at
http://www.worldscientific.com/doi/suppl/10.1142/7438/suppl file/7438 chap01.pdf.
[2] C. Witt. The fitness level method with tail bounds. CoRR, abs/1307.4274, 2013. Available
online at http://arxiv.org/abs/1307.4274.

6

