he coupon-collector's problem revisited 517 where(8)follows from the conditional expectation inequality and(9)from P(Bk. B P时,B)=P(B (pk/(pk+pi+pr)j (Pk/(Pk+Pi) pk+ pi Pk+ Pi+ pr Therefore. we obtain our second upper bound for E[1=∑11-P(A分小 E[U]≤ (Pk/(Pk +Pi)) +ik(Pk+ Pi//(Pk+Pi+pr) To obtain a lower bound, let X; denote the time of the first type-i event, and let denote the time of the j th type-k event in the Poissonization scheme(which results in T and Xifor i# k being independent). Then, from(4) P(4=E∏ Using the well-known result that elf(X)g(X)> elf(X)elg(X)] whenever f and g ar increasing functions [4, p. 339], which easily generalizes to the product of any number of positive increasing functions, the preceding equation yields that P(45≥E-cr =∏IP(T>X) ∏[-P(T<X) pk Pi t pk Thus, we have the lower bound E[Um]≥ k=1i≠k Pi t pk Remark 2. (i) Our computational experiments verify that the bounds given in(7)work well for probabilities Pi which are roughly the same, while the bounds given in(10)and(11)are erw (ii) For the equal-probabilities case, the explicit expression for E[Um ]of Proposition 1 is faster to compute than the recursive expression of Proposition 2. However, for large m(say m> 150). the explicit expression(but not the recursive one) is computationally unstableThe coupon-collector's problem revisited where (8) follows from the conditional expectation inequality and (9) from P(BkrBki) P(Bj k Bk ) = n' ,ir j,r ,i' P(Bkj P(Bj,) (Pk/(Pk + Pi + Pr))j (Pk/(Pk + Pi))' = ( Pk + Pi ) Pk + Pi + Pr J Therefore, we obtain our second upper bound for E[Uj ] = km1[1 - P(Ak)]: E[Ujm] <m-L m ?(Pk/(Pk+ PiW (10) JE[? < m Ek - 1 + Erfi,k(Pk + Pi)J/(Pk + Pi + Pr (10) To obtain a lower bound, let Xi denote the time of the first type-i event, and let Tk denote the time of the jth type-k event in the Poissonization scheme (which results in Tk and Xi for i = k being independent). Then, from (4), 1-P(A5)=E fl(-e-PT'k -i:k Using the well-known result that E[f(X)g(X)] > E[f(X)]E[g(X)] whenever f and g are increasing functions [4, p. 339], which easily generalizes to the product of any number of positive increasing functions, the preceding equation yields that 1-P(Ak) > E[1-e PiT"] ifk = P(Tk > Xi) i#k = H[ - p(Tf < Xi)] i#k i9k- t-k -( Pi +Pk J Thus, we have the lower bound k= ik - ( ) Pk iO urputi l i if i i k Remark 2. (i) Our computational experiments verify that the bounds given in (7) work well for probabilities pi which are roughly the same, while the bounds given in (10) and (11) are tighter otherwise. (ii) For the equal-probabilities case, the explicit expression for E[Uj ] of Proposition 1 is faster to compute than the recursive expression of Proposition 2. However, for large m (say m > 150), the explicit expression (but not the recursive one) is computationally unstable. 517