The Collector’s Brotherhood Problem Using the Newman-Shepp Symbolic Method

Dominique Foata,^{1} Doron Zeilberger^{2}

To Gian-Carlo Rota, in memoriam

Abstract. Further computations are made on the traditional coupon collector’s problem when the collector shares his harvest with his younger brothers. When the book of the p-th brother of the collector is completed, the books of the younger brothers have certain numbers of empty spots. On the average, how many? Several answers can be brought to that question.

1. Introduction. This paper on the traditional and recurrent Collector’s Problem, that uses the Newman-Shepp method, one of those symbolic approaches dear to Gian-Carlo Rota, is dedicated to his memory.

Suppose that m different coupons are needed for a collector, to complete his picture-book. Each time, that is, at each purchase, he can get a given coupon with probability 1/m. If he does not have it yet, he sticks it on his book. Otherwise, he gives it to his younger brother. In his turn, the younger brother sticks it on his own book, if the coupon is new for him. Otherwise, the next younger brother will receive it and try to complete his own picture-book, using the same policy. The collector is labelled 0, the younger brother 1, the next younger brother 2, etc.

For p ≥ 0 let T_{p} be the time at which the person labelled p completes his book. Also for each k ≥ 1, n ≥ 1 and 1 ≤ i ≤ m let

X_{n,i}^{(k)} = \{ \begin{matrix}1, & if coupon i has occurred k times \\ & up to and including time n; \\ 0, & otherwise. \end{matrix}

Thus, X_{n}^{(k)} = ∑_{1≤i≤m} X_{n,i}^{(k)} is the number of coupons that have occurred k

times (exactly) up to and including time n. For each n ≥ 1 let X_{n}^{(0)} be the number of empty spots in the collector’s book at time n; by convention X_{0}^{(0)} = m.

AMS 2000 Classification: 05A15, 05E05, 60C05.

Keywords: Coupon collector’s problem, Surjection calculus, Newman-Shepp symbolic method, Hyperharmonic numbers.

1 Supported in part by the NSF, as a consultant on Zeilberger’s grant.

2 Supported in part by the NSF.

D. FOATA, D. ZEILBERGER

For each p ≥ 0 we have X_{T_{p}}^{(p)} = 0 and for each k ≥ p + 1 the number of coupons that have occurred k times up to and including time T_{p} is X_{T_{p}}^{(k)}. Consequently, the number of empty spots in the book of the brother

labelled k ≥ p + 1 at time T_{p} is X_{T_{p}}^{(p+1)} + X_{T_{p}}^{(p+2)} + ⋯ + X_{T_{p}}^{(k)}.

Several methods have been used to derive the probability distribution of T_{0} and its expected value 𝔼[T_{0}]. The evaluation 𝔼[T_{0}] = m H_{m}, where H_{m} is the harmonic number H_{m} = 1 + \frac{1}{2} + ⋯ + \frac{1}{m}, is a classic (see Feller (1968)). The evaluation 𝔼[X_{T_{0}}^{(1)}] = H_{m} is due to Pintacuda (1980) using a method based on the martingale stopping time theorem. Recently, Foata, Han and Lass (2001) have derived the generating function for the vector (T_{0}, X_{T_{0}}^{(1)}, X_{T_{0}}^{(2)}, …, X_{T_{0}}^{(k)}) (k ≥ 1) and, when k ≥ 2, obtained the evaluations 𝔼[X_{T_{0}}^{(k)}] = K_{m}^{(k)}, where K_{m}^{(k)} is the hyperharmonic number that can be defined by the generating function:

(1.1)  ∑_{k≥0} K_{m}^{(k)}t^{k} = \frac{1}{(1 − t/2)(1 − t/3) ⋯ (1 − t/m)}.

Now the natural question to ask is the following: what can be said when the stopping time T_{0} is replaced by T_{p} for an arbitrary p ≥ 0? Back to the early sixties Newman and Shepp (1960) obtained the integral expression

(1.2) 𝔼[T_{p}] = m ∫_{0}^{+∞}(1 − (1 − S_{p+1}(x)e^{−x})^{m}) dx,

where

(1.3) S_{p+1}(x) := 1 + \frac{x}{1!} + ⋯ + \frac{x^{p}}{p!} (p ≥ 0).

The purpose of this paper is to make use of the symbolic method developed by Newman and Shepp (op. cit.) to obtain the following formulas, all of them expressed in terms of integrals. For each 0 ≤ p < r consider the generating functions:

(1.4)  H_{T_{p}}(t) := ∑_{i≥0} P{T_{p} > i} t^{i};
(1.5)  G_{T_{p}}(t) := ∑_{i≥0} P{T_{p} = i} t^{i};
(1.6) G_{T_{p},X}(t, s) := ∑_{n,n_{1},...,n_{r}} P{T_{p} = n, X_{T_{p}}^{(p+1)} = n_{p+1}, …, X_{T_{p}}^{(r)} = n_{r}}
× t^{n}s_{p+1}^{n_{p+1}} ⋯ s_{r}^{n_{r}};
(1.7)  G_{X}^{(p)}(t) := ∑_{k≥p+1} 𝔼[X_{T_{p}}^{(k)}] t^{k}.

THE COLLECTOR’S BROTHERHOOD PROBLEM

We then establish the formulas:

(1.8) H_{T_{p}}(t) = m ∫_{0}^{+∞}(e^{−mx(1−t)} − (e^{−x(1−t)} − S_{p+1}(tx)e^{−x})^{m}) dx;

(1.9) G_{T_{p}}(t) = m(1 − t) ∫_{0}^{+∞}(e^{−x(1−t)} − e^{−x}S_{p+1}(tx))^{m} dx;

(1.10) G_{T_{p},X}(t, s) = \frac{ms_{p+1}t^{p+1}}{p!} ∫_{0}^{+∞} x^{p}e^{−mx}

× (e^{xt} − S_{r+1}(xt) + \frac{(xt)^{p+1}}{(p + 1)!}s_{p+1} + ⋯ + \frac{(xt)^{r}}{r!} s_{r})^{m−1} dx;

(1.11) G_{X}^{(p)}(t) = t^{p+1}

+ m(m − 1) ∫_{0}^{+∞}e^{−mx} \frac{x^{p}}{p!} (e^{xt} − S_{p+1}(xt))(e^{x} − S_{p+1}(x))^{m−2} dx.

By expanding the different integrands using the multinomial theorem we can express those integrals as finite sums over ℕ^{r+2} for some r. For instance, (1.10) may be rewritten as

(1.12) G_{T_{p},X}(t, s) = \frac{s_{p+1}t}{p!} ∑ \binom{m − 1}{a, b_{0}, …, b_{r}}(−1)^{b_{0}+···+b_{r}} (∏_{i=0}^{p}(\frac{1}{i!})^{b_{i}})

× ( ∏_{i=p+1}^{r}(\frac{s_{i} − 1}{i!})^{b_{i}} ) \frac{(t/m)^{p+1·b_{1}+···+r·b_{r}}}{(1 − at/m)^{1+p+1·b_{1}+···+r·b_{r}}} (p + ∑_{i=1}^{r}ib_{i})!,

that specializes to the formula derived by Foata et al. (2001) for the case p = 0. However the main difference between the latter case and the general case p ≥ 1 is the fact that when p = 0 identity (1.12) can directly lead to the explicit evaluations 𝔼[X_{T_{0}}^{(1)}] = H_{m} and 𝔼[X_{T_{0}}^{(k)}] = K_{m}^{(k)} (k ≥ 2) (the hyperharmonic number), while for p ≥ 1 the integral form that can be obtained from (1.10) has no further simplification.

In section 2 we discuss certain salient features of Surjection Calculus. In section 3 we recall the symbolic method developed by Newman and Shepp (op. cit.) and use it to prove identities (1.8) and (1.9). Identities (1.10) and (1.11) are proved in sections 4 and 5, respectively. We conclude the paper by some remarks on the holonomic aspects of the above integral identities.

Notice that the asymptotics of 𝔼[T_{p}] for an arbitraary p ≥ 0 have been derived by Newman and Shepp (op. cit.) and the asymptotic probability distribution of T_{p} has been calculated by Erdős and Rényi (1961). More recent work along those lines is due to Wilf (2001).

2. Surjection calculus. Let (t, s_{1}, s_{2}, …) be a sequence of commuting variables. If f maps a finite set A of integers into a (finite) set B of integers, let ν_{i}(f) denote the number of elements j ∈ B such that the preimage f^{−1}(j) is of cardinality i. Then, the weight π(f) of f is defined by: π(f) := ∏_{i≥1}s_{i}^{ν_{i}(f)} ; so that the relations ∑_{i}ν_{i}(f) = #B et ∑_{i}i ν_{i}(f) = #A. hold.

For each integer n let [n] := {1, 2, …, n} and for each pair of finite sets (A, B) let Surj_{≥p+1}(A, B) denote the set of all surjections f : A → B such that for all j ∈ B the inequality #f^{−1}(j) ≥ p + 1 holds. The following identity is the basic identity in Surjection Calculus (see, e.g., Foata (1974), p. 60):

(2.1)  ( ∑_{i≥p+1} s_{i} \frac{t^{i}}{i!} )^{m} = ∑_{n≥(p+1)m} \frac{t^{n}}{n!} ∑_{f∈Surj_{≥p+1}([n],[m])} π(f).

This implies, when all the s_{i}’s are equal to 1,

(2.2) (e^{t} − S_{p+1}(t))^{m} = ∑_{n≥(p+1)m} \frac{t^{n}}{n!} # Surj_{≥p+1}([n], [m]).

Next consider the subset A(n, m) of all surjections f in Surj_{≥p+1}([n], [m]) such that if f(n) = j then #f^{−1}(j) = p + 1. In other words, all values are taken at least p + 1 times, but the value taken at n occurs exactly p times in (f(1), f(2), …, f(n − 1)). Then, identity (2.1) implies

(2.3) ∑_{n≥m(p+1)} \frac{t^{n−1}}{(n − 1)!} ∑_{f∈A(n,m)} π(f) = ms_{p+1} \frac{t^{p}}{p!} ( ∑_{i≥p+1} s_{i} \frac{t^{i}}{i!} )^{m−1}.

Let 0 ≤ p < r, n := (n_{p+1}, n_{p+2}, …, n_{r}) and let A(n, m; n) be the subset of all surjections f in A(n, m) such that

ν_{i}(f) = n_{i} for i = p + 1, p + 2, …, r.

When s_{i} := 1 for all i ≥ r + 1, identity (2.3) rewrites as:

(2.4) ∑_{n≥m(p+1)} \frac{t^{n−1}}{(n − 1)!} ∑_{n} #A(n, m; n) ∏_{p+1≤i≤r} s_{i}^{n_{i}}

= ms_{p+1} \frac{t^{p}}{p!} (e^{t} − S_{r+1}(t) + s_{p+1} \frac{t^{p+1}}{(p + 1)!} + ⋯ + s_{r} \frac{t^{r}}{r!} )^{m−1}.

Now let i, j be two distinct integers in [m] and for each n ≥ (p+1)m let B(n − 1, i, j) be the set of surjections f : [n − 1] → [m] with the following properties: with I(f) := f^{−1}(i), J(f) := f^{−1}(j) then #J(f) = p and the restriction of f to [n−1]\J(f) belongs to Surj_{≥p+1}([n−1]\J(f), [m]\{j}). Then form the generating polynomial

(2.5)  F_{n−1}(t) = ∑_{f∈B(n−1,i,j)} t^{#I(f)}.

Still using (2.1) a little reflection shows that the following identity holds:

(2.6) ∑_{n≥(p+1)m} \frac{u^{n−1}}{(n − 1)!}F_{n−1}(t) = \frac{u^{p}}{p!} (e^{ut} −S_{p+1}(ut))(e^{u} −S_{p+1}(u))^{m−2}.

3. The Newman-Shepp symbolic method. Let m ≥ 1 and consider the algebra of power series in the variables u_{1}, u_{2}, …, u_{n}. If a = a(u_{1}, …, u_{n}) is such a series, write it as

a(u_{1}, …, u_{n}) = ∑_{i≥0} \frac{1}{i!} a_{i}(u_{1}, …, u_{n}),

where a_{i}(u_{1}, …, u_{n}) is the sum of all monomials of degree i in a. Now define

N_{m} a(u_{1}, …, u_{n}) := ∑_{i≥0} \frac{1}{m^{i}} a_{i}(u_{1}, …, u_{n}),

so that the exponential normalization has be replaced by the power normalization. We next reproduce the integral expression for N_{m} a(u_{1}, …, u_{n}) as derived by Newman and Shepp (op. cit.).

Lemma 3.1. We have the identity:

N_{m} a(u_{1}, …, u_{n}) = m ∫_{0}^{+∞} e^{−mx} a(xu_{1}, …, xu_{n}) dx.

For each n = 1, 2, … let Y_{n} be the label of the coupon which is obtained at time n. By assumption, the random variables Y_{n} (n = 1, 2, …) are assumed to be independent and uniformly distributed on the coupon label set {1, 2, …, m}. The event {T_{p} > n} is realized if and only if the mapping f : i ↦ Y_{i} (1 ≤ i ≤ n) belongs to the set Surj_{≥p+1}^{c}([n], [m]) := [m]^{n} \ Surj_{≥p+1}([n], [m]). Hence P{T_{p} > n} = # Surj_{≥p+1}^{c}([n], [m])/m^{n}. But it follows from (2.2) that

e^{mt} − (e^{t} − S_{p+1}(t))^{m} = ∑_{n≥0} \frac{t^{n}}{n!} # Surj_{≥p+1}^{c}([n], [m]),

so that

N_{m} (e^{mt} − (e^{t} − S_{p+1}(t))^{m}) = ∑_{n≥0} \frac{t^{n}}{m^{n}} # Surj_{≥p+1}^{c}([n], [m])

= ∑_{n≥0} P{T_{p} > n}t^{n} = H_{T_{p}}(t).

Hence, by Lemma 3.1

H_{T_{p}}(t) = m ∫_{0}^{+∞} e^{−mx}(e^{mtx} − (e^{tx} − S_{p+1}(tx))^{m}) dx,

which reduces to (1.8). To get (1.9) we make use of the traditional relation G_{T_{p}}(t) = 1−(1−t) H_{T_{p}}(t). Finally, when we plug t = 1 in (1.8), we recover formula (1.2) already derived by Newman and Shepp (op. cit.).

4. The multivariable generating function. Keep the same notations for the sequence (Y_{n}) (n = 1, 2, …) of coupon labels that occur at time n = 1, 2, … and for the variables X_{n}^{(k)} defined in the introduction. Then, the event {T_{p} = n, X_{T_{p}}^{(p+1)} = n_{p+1}, …, X_{T_{p}}^{(r)} = n_{r}} is realized if and only if the mapping f : i ↦ Y_{i} (1 ≤ i ≤ n) belongs to the set A(n, m; n) introduced in (2.4). Hence, P{T_{p} = n, X_{T_{p}}^{(p+1)} = n_{p+1}, …, X_{T_{p}}^{(r)} = n_{r}} = #A(n, m; n)/m^{n}. It follows from (2.4) that

N_{m}(ms_{p+1} \frac{t^{p}}{p!} (e^{t} − S_{r+1}(t) + s_{p+1} \frac{t^{p+1}}{(p + 1)!} + ⋯ + s_{r} \frac{t^{r}}{r!} )^{m−1})

= ∑_{n≥m(p+1)} \frac{t^{n−1}}{m^{n−1}} ∑_{n} #A(n, m; n) ∏_{p+1≤i≤r} s_{i}^{n_{i}},

so that, by multiplying both members by t/m,

t N_{m}(s_{p+1} \frac{t^{p}}{p!} (e^{t} − S_{r+1}(t) + s_{p+1} \frac{t^{p+1}}{(p + 1)!} + ⋯ + s_{r} \frac{t^{r}}{r!} )^{m−1})

= ∑_{n≥m(p+1)} \frac{t^{n}}{m^{n}} ∑_{n} #A(n, m; n) ∏_{p+1≤i≤r} s_{i}^{n_{i}}

= ∑_{n,n} P{T_{p} = n, X_{T_{p}}^{(p+1)} = n_{p+1}, …, X_{T_{p}}^{(r)} = n_{r}}t^{n}s_{p+1}^{n_{p+1}} ⋯ s_{r}^{n_{r}}

= G_{T_{p},X}(t, s).

This establishes identity (1.10) by using again Lemma 3.1.

THE COLLECTOR’S BROTHERHOOD PROBLEM

5. A generating function for the expected times. We may write

G_{X}^{(p)}(t) := ∑_{k≥p+1} 𝔼[X_{T_{p}}^{(k)}] t^{k} = ∑_{k≥p+1} ∑_{1≤i≤m} 𝔼[X_{T_{p},i}^{(k)}] t^{k}

= ∑_{k≥p+1} ∑_{1≤i≤m} P{X_{T_{p},i}^{(k)} = 1} t^{k}

= ∑_{k≥p+1} ∑_{1≤i≤m} ∑_{n≥(p+1)m} ∑_{1≤j≤m} P{X_{n,i}^{(k)} = 1, T_{p} = n, Y_{n} = j} t^{k}

= t^{p+1} + ∑_{n≥(p+1)m} ∑_{i} ∑_{j≠i} ∑_{k≥p+1} P{X_{n−1,i}^{(k)} = 1, T_{p} = n, Y_{n} = j} t^{k}.

Now the event {X_{n−1,i}^{(k)} = 1, T_{p} = n, Y_{n} = j} is realized if and only if the mapping f : k ↦ Y_{k} (1 ≤ k ≤ n − 1) belongs to the set B(n − 1, i, j) introduced in (2.5)–(2.6) and if Y_{n} = j. Hence, keeping the same notations,

∑_{k≥p+1} P\{X_{n−1,i}^{(k)} = 1, T_{p} = n, Y_{n} = j\}t^{k} = \frac{1}{m^{n}} F_{n−1}(t),

so that

G_{X}^{(p)}(t) = t^{p+1} + m(m − 1) ∑_{n≥(p+1)m} \frac{1}{m^{n}} F_{n−1}(t).

With the introduction of a new variable u define:

G_{X}^{(p)}(t, u) := t^{p+1} + (m − 1) ∑_{n≥(p+1)m} \frac{u^{n−1}}{m^{n−1}} F_{n−1}(t).

Then

\begin{aligned}G_{X}^{(p)}(t, u) & = N_{m}(t^{p+1} + (m − 1) ∑_{n≥(p+1)m} \frac{u^{n−1}}{(n − 1)!}F_{n−1}(t)) \\ & = N_{m}(t^{p+1} + (m − 1)\frac{u^{p}}{p!} (e^{ut} − S_{p+1}(ut))(e^{u} − S_{p+1}(u))^{m−2}) \end{aligned}

by using (2.6). Next applying Lemma 3.1 we get:

G_{X}^{(p)}(t, u) = t^{p+1}

+ m(m − 1) ∫_{0}^{+∞} e^{−mx} \frac{(ux)^{p}}{p!} (e^{uxt} − S_{p+1}(uxt))(e^{ux} − S_{p+1}(ux))^{m−2} dx,

which reduces to (1.11) by making u = 1.

6. Concluding Remarks. Identity (1.1) together with the evaluations 𝔼[X_{T_{0}}^{(1)}] = H_{m} and 𝔼[X_{T_{0}}^{(k)}] = K_{m}^{(k)} (k ≥ 2) can be rewritten as

(6.1) G_{X}^{(0)}(t) = ∑_{k≥1} 𝔼[X_{T_{0}}^{(k)}]t^{k} = −1+t+ \frac{1}{(1 − t/2)(1 − t/3) ⋯ (1 − t/m)}.

That identity, derived by Foata et al. (op. cit.), can also be obtained from its integral form (1.11). When p = 0, the factor x^{p} in the integrand vanishes. With the change of variables u = e^{−x} the integral in (1.11) reduces to the evaluation of two bêta integrals:

G_{X}^{(0)}(t) = t + m(m − 1) ∫_{0}^{1}(u^{−t+1} − u)(1 − u)^{m−2} du

= t + m(m − 1)(\frac{Γ(2 − t)Γ(m − 1)}{Γ(m − t + 1)} − \frac{Γ(2)Γ(m − 1)}{Γ(m + 1)})

= t + \frac{m!}{(m − t)(m − t − 1) ⋯ (2 − t)} − 1

= −1 + t + \frac{1}{(1 − t/2)(1 − t/3) ⋯ (1 − t/m)}.

Unfortunately, for p > 0, it does not seem to be possible to evaluate the integral in closed form, since then the integral representation is hybrid, involving a polynomial in the variable and its exponential. Hence it lies outside the jurisdiction of the holonomic paradigm, and in general there is no reason why the integral should evaluate to something ‘nice’, and indeed it, most probably, does not!

Acknowledgements. We owe to the search sagacity of Herb Wilf to have found track of the paper by Newman and Shepp. Those authors had entitled their paper “Double Dixie Cup Problem” without reference to the traditional Coupon Collector lore, which explains our difficulty to locate it through MathSciNet. We should also like to thank the anonymous referee for his careful reading of the paper and his useful remarks.

REFERENCES

Erdős, Paul; Rényi, Alfred (1961). On a classical problem of probability theory, Magyar. Tud. Akad. Mat. Kutató Int. Kőzl., 6, p. 215–220.

Feller, William (1968). An Introduction to Probability Theory and its Applications, Third edition, vol. 1. John Wiley & Sons, New York.

Foata, Dominique (1974). La série génératrice exponentielle dans les problèmes d’énumération. Les Presses de l’Université de Montréal, Montréal.

Foata, Dominique; Han Guo-Niu; Lass, Bodo (2001). Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes, Sém. Lothar. Combin., 47, B47a, 2001, 20 pages [http://mat.univie.ac.at/∼slc/].

Newman, Donald J.; Shepp, Lawrence (1960). The Double Dixie Cup Problem, Amer. Math. Monthly, 67, p. 58–61.

Pintacuda N. (1980). Coupon Collectors via the Martingales, Boll. Un. Mat. Ital. A, 17, p. 174–177.

Wilf, Herb (2001). Some finite structures of the coupon collector’s problem. Preprint.

Dominique Foata Département de mathématique Université Louis Pasteur 7, rue René-Descartes F-67084 Strasbourg, France

foata@math.u-strasbg.fr

Doron Zeilberger Department of Mathematics Hill Center-Busch Campus Rutgers, The State University of New Jersey 110 Frelinghuysen Rd Piscataway, NJ 08854-8019, USA

zeilberg@math.rutgers.edu