18.317 Combinatorics, Probability, and Computations on Groups 1 October 2001

Lecture 10

Lecturer: Igor Pak Scribe: Igor Pavlovsky

Coupon Collector’s Problem

Recall that the problem concerns a prudent shopper who tries, in several attempts, to collect a complete set of N different coupons. Each attempt provides the collector with a coupon randomly chosen from N known kinds, and there is an unlimited supply of coupons of each kind. It is easy to estimate the expected waiting time to collect all N coupons:

E[time to collect N coupons] = 1 + \frac{N}{N − 1} + \frac{N}{N − 2} + ⋯ + N = N(log N + γ + O(\frac{1}{N}))

Similarly,

E[time to collect \frac{N}{2} coupons] = 1 + \frac{N}{N − 1} + \frac{N}{N − 2} + ⋯ + \frac{N}{\frac{N}{2} + 1}

= N(log N + γ + O(\frac{1}{N}) − log \frac{N}{2} − γ − O(\frac{1}{N}))

= N log 2 + O(1)

Let’s explore the problem further. Suppose our collector attempts to obtain coupons T = αN times. We’d like to know how many different kinds of coupons he can be expected to have, and also how many of these are not repeated. For such estimates, we need the following tool:

Theorem 1 (Chernoff bound) Let X_{i}, i = 1 … n, be independent Poisson trials, with outcomes 1 and 0 with probabilities p_{i} and 1 − p_{i} respectively. Set X = ∑_{i=1}^{n} X_{i}, μ = E[X] = ∑ p_{i}. Then for every δ > 0, the following bounds hold:

Pr[X > (1 + δ)μ] < (\frac{e^{δ}}{(1 + δ)^{1+δ}} )^{μ}
Pr[X < (1 − δ)μ] < e^{−μδ^{2}/2}

In our situation, at every step

Pr[got a coupon we already have] < α
Pr[got a new coupon] > 1 − α

Consider the worst-case independent-trials processes defined by the above inequalities transformed into equalities. Bounds on these processes will give us the desired bounds for the coupon collector’s problem. Clearly,

E[number of repeated coupons] < αT
E[number of different coupons] > (1 − α)T

Therefore, by Chernoff bounds,

Pr[# rep coupons > (1 + δ)αT] < ϵ_{1}^{T}
Pr[# diff coupons < (1 − δ)(1 − α)T] < ϵ_{2}^{T}

where ϵ_{1}, ϵ_{2} depend on α and δ. Now, the event [# non-repeated coupons < A − B] is contained in the union of the events [# diff coupons< A] ∪ [# rep coupons > B]. Hence,

Pr[# non-rep coupons < (1 − δ)(1 − α)T − (1 + δ)αT] < ϵ_{1}^{T} + ϵ_{2}^{T} < ϵ^{T}

for large T and some ϵ dependent on α and δ. Recalling that T = αN, conclude

Theorem 2 After αN steps, the number of non-repeated coupons accumulated by the collector is greater than cN with probability > 1 − ϵ^{N} for large N. Here α, c, ϵ > 0, one of α or c may be chosen arbitrarily, and the other two parameters are produced by the theorem.

Mixing Time of Random Walks

We have finally arrived at our goal

Theorem 3 Let X_{t} be a lazy random walk on G starting at 1, with a random generating set of size k. Denote by sep(T) the separation distance after T steps. Then exists a constant c > 0 such that sep(c log |G|) < ϵ with probability > 1 − δ − γ, provided that k = 2 log |G| + 2 log \frac{1}{ϵ} + 2 log \frac{1}{δ} + log \frac{1}{γ}.

Proof: Combine the Erdős–Rényi machine and coupon collector’s problem to ensure enough non-repeated generators. Check parameters, done.

Our next aim is to prove that random Cayley graphs are expanders. We begin with a few observations on matrices and random walks. Let A be the transition matrix for the random walk X_{t+1} = X_{t} · g_{i} on G with generators g_{1}, …, g_{k}. If at each step the generator g_{i} is chosen uniformly, then the entries of A are numbers 0 and \frac{1}{k}. Let v = e_{1} be the initial state vector (begin at 1). The vector A^{t}v gives the probability distribution on G after t steps, and can be written as

A^{t}v = u + λ_{1}^{t}w_{1} + λ_{2}^{t}w_{2} + …

where λ_{1} ≥ λ_{2} ≥ … are the eigenvalues of A. If these eigenvalues are real, they clearly must lie between −1 and 1 for the distribution to converge to the uniform probability distribution U.