. ADLER ETAL E[Um]=>[1-P(A)] [1-P(Am)] (1) Let bj.i denote the event that at least j type-m coupons arrive before the first coupon of type i arrives. Then P(A) Bii and the inclusion-exclusion probability equality give(forj2 2) ∑P(B"n1…Bm Using(1), this gives the following result Next, using basic probability arguments, we obtain a recursive expression for E[U l that was first presented in [l] and [2]. Let C be the event that at least j type-k coupons have already arrived at the moment when each of the item types l,..., k-l has arrived. Also, let X be the number of types 1 ,., k- l that have not yet arrived when the first coupon of type k arrives With PK= P(Ck), we obtain that =∑P P/+ ∑P where pk =(k-1)/k for k=1,2 Substituting A=C for j2 2 into(D)gives E[UM]=m[1-Pil. j>2 Thus, using(2)and (3), we obtain that E[U2]=mI. ADLER ETAL. Thus, m E[Um] = E[1- P(Ak)] k=l =m[l - P(Am)]. (1) Let Be. denote the event that at least j type-m coupons arrive before the first coupon of J,I type i arrives. Then m-1 P(A) = P( Bji) and the inclusion-exclusion probability equality give (for j > 2) m-1 :(,~)_C-i)k+l P(BTmi P(A7) = (-1)k+ L ... B ) E P(Bj,, * BJ,ik k=1 il<i2<' <ik m-l = ( -1)k+l m-(k I) k=l Using (1), this gives the following result. Proposition 1. For j > 2, m (m) i-j Next, using basic probability arguments, we obtain a recursive expression for E[Uj ] that was first presented in [1] and [2]. Let Ck be the event that at least j type-k coupons have already arrived at the moment when each of the item types 1,..., k - 1 has arrived. Also, let Xk be the number of types 1, ..., k - 1 that have not yet arrived when the first coupon of type k arrives. With Pk = P(Ck), we obtain that k-I k = P (Ck Xk =r) r)(X r r=O k-I -= ? ' pr+l k / -1 r=O k -k E -i (2) r=l where Pk = (k - 1)/k fork = 1, 2,.... Substituting Am = Cm for j > 2 into (1) gives E[Um] = ml - Pm], j 2. (3) Thus, using (2) and (3), we obtain that m r m E[U=] =- m - r - r=l k r=1 k=l 514