Answers are grounded in this paper and cite their sources.
We shall introduce a set of random variables and give interpretations of them in terms of coupon collection. A person collects coupons with different colors. Let there be in all N different colors, which we label 1,2, ⋯, N. The different colors may occur with different frequencies. The colors of successive coupons are independent. Let J_ν be the color of the νth coupon. Our formal assumptions are: J₁, J₂, ⋯ are independent random variables, all with the following distribution {equation*}{1.1} P(J = s) = p_s, s = 1,2, ⋯, N{equation*} where {equation*}{1.2} p_s 0, p_1 + p_2 + ⋯ + p_N = 1.{equation*} Thus, pₛ is the probability that a coupon has color s. Let {equation*}{1.3} M_n = {#} different elements among (J_1, J_2, ⋯, J_n), n = 1,2, ⋯.{equation*} Thus, Mₙ is the number of different colors in the collection after n coupons. Let {equation*}{1.4} T_n = min \{ν: M_ν = n\}, n = 1,2, ⋯, N.{equation*} Tₙ is the number of coupons needed in order to get a collection with n different colors in. Define {align*} {1.5} D_ν &= 1 J_ν ∉ (J_1, J_2, ⋯, Jν-1), ν = 1,2, ⋯ \\ &= 0 otherwise.{align*} Thus, D_ν tells if the νth coupon adds a new color to the collection or not. We shall assume that the coupons also carry a bonus value, which is a real number. All coupons with the same color have the same bonus value, while the bonus value may differ from color to color. Let aₛ be the bonus value of coupons with color s, s = 1,2, ⋯, N. The bonus sum of a collection of coupons is obtained by adding the bonus values of the different colors which are represented in the collection. Thus, duplicates do not count. Formally we define the bonus sum as follows. {equation*}{1.6} Q_n = aJ_1D_1 + aJ_2D_2 + ⋯ + aJ_nD_n, n = 1,2, ⋯.{equation*} The random variable Qₙ will be referred to as the bonus sum after n coupons for a collector in the situation Ω = ((p₁, a₁), (p₂, a₂), ⋯, (pN, aN)). We define for $B > 0$ {equation*}{1.7} W(B) = min \{n: Q_n B\}.{equation*} $W(B)$ will be referred to as the waiting time to obtain bonus sum B for a coupon collector in the situation Ω. The following lemma, which is obvious, states that we have introduced a slight abundance of terminology and notation. LEMMA 1.1. The random variables Mₙ and Tₙ in (1.3) and (1.4) are respectively the bonus sum after n coupons and the waiting time to obtain bonus sum n for a coupon collector in the situation ((p₁), (p₂, 1), ⋯, (pₙ, 1)). Our main concern will be to study the random variable $W(B)$ and its particular case Tₙ. We confine ourselves to the case when all bonus values, aₛ, are positive. The main result is that $W(B)$, under general conditions, is asymptotically (as n and N increase simultaneously) normally distributed. We give a brief sketch of the idea of proof, which is well known. When all a's are positive, the distributions of the random variables $W(B)$ and Qₙ are related according to the formula {equation*}{1.8} P(W(B) > x) = P(Qₓ < B), x, B > 0.{equation*} With the aid of formula (1.8) one can "invert" results concerning either of the random variables Q or W to yield results concerning the other variable. In [5] we showed that Qₙ, under general conditions, is asymptotically normally distributed. The asymptotic normality of W will be derived by inversion of the results in [5]. The asymptotic behavior of the collector's waiting time has, to the best of our knowledge, earlier only been considered in the classical case, i.e. pₛ = 1/N and aₛ = 1, s = 1,2, ⋯, N. In [4] Section 3, Renyi derives results about M by first deriving results about T and then "inverting." His basic tool is the representation {equation*}{1.9} T_n = U_1 + U_2 + ⋯ + U_n{equation*} where Uᵥ is the waiting time from bonus sum ν - 1 to bonus sum ν. In the classical case U₁, U₂, ⋯ are independent random variables and P(U_ν = k) = ((ν - 1)/N)ᵏ⁻¹(N - ν + 1)/N, k = 1,2, ⋯. Thus, results concerning the asymptotic behavior of sums of independent random variables can be applied. A complete investigation along these lines is given by Baum and Billingsley in [1]. A generalized version of the problem is considered by Ivchenko and Medvedev in [2]. In their problem, as in our problem here, a representation of the type (1.9) no longer holds. They proceed along the path we shall follow here, i.e. to obtain results about the waiting time by "inverting" results concerning the bonus sum. The following notation will be used throughout the paper. E and σ² stand for expectation and variance. ᶜ denotes centering at expectation, i.e. Xᶜ = X - EX. X = L Y means that the random variables X and Y have the same distribution. ⇒ denotes convergence in law. The normal distribution with mean μ and variance σ² is denoted by N(μ, σ²). The integral part of a real number is denoted by .
No takes yet. Share an insight, caveat, or question.
Bengt Rosén (1970) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: