516 L. ADLER ET AL. Proof. With y =In(x) Because In(x)in increasing in x, by the Ostrowski condition for Schur concavity(see [31)it suffices to show that rie ( x2)>x2e-(1-e)ifx1<x2 But this inequality follows because xe /(1-e)is a decreasing function of x Lower and upper bounds on E[U], fairly tight for va (1/m, 1/m,., 1/m), can be obtained from the inequalities (-e-mkrm-I ≤4-en)≤(1-e8) where mk=mini*lpi)and gk=(+k Pi)(m-l. That is, &k is the geometric mean of the alues Pi for i#k. The second inequality of(6) follows from Lemma I We obtain from(4)and (6)that 1-P(A)≤/pe e-gkxm-l x (Pkx) Pk pk Pk where A= rgk Pk. Substituting the preceding inequality into(5)and considering both equalities of() gives EU"1≤∑ (-1) We will now derive a second set of lower and upper bounds for E[U]. Let b, denote the event that at least j coupons of type k arrive before the first of type i arrives. Then, using the 3.2.3 of [SD), we obtain that P(A)=P(∪b P(Bk k((pk+ pi)/(Pk+ pi+ pr))I. ADLER ETAL. Proof With y = In(x), -(1 -e-X) = xe-X ay Because ln(x) in increasing in x, by the Ostrowski condition for Schur concavity (see [3]) it suffices to show that xle-I (1-e-X2) > x2e-X2(1 -e-X) if XI < x2. But this inequality follows because xe-X /( - e-X) is a decreasing function of x. Lower and upper bounds on E[UJ], fairly tight for values of (Pl, P2, .... P) close to (1/m, l/m, .., l/m), can be obtained from the inequalities (1 - e-mkx)m-1 < nH( - ePix) < (1 - e- ") (6) i#k where mk = minigk{pi) and gk = (f-ifk Pi)l/(m-l) That is, gk is the geometric mean of the values pi for i : k. The second inequality of (6) follows from Lemma 1. We obtain from (4) and (6) that 1 - P(AJ) < ke PkX (p k ' (1 - e-gkx)m-1 dx - (j - 1)I m- p-(rm-+Pk)x (PkX)j- l m= (m- 1)(l)r ke-(rgk+ P k) dx r=O where A = rgk + Pk. Substituting the preceding inequality into (5) and considering both inequalities of (6) gives r= r rgk + Pk (j-)! = ri (m - 1 )(rl( Pk ) . ~0^ ~ ~ ~ = r rgk + Pk Pk where X = rgk ? Pk. Substituting the preceding inequality into (5) and considering both E( r) ) r +pk < E[Um] < EI)r ) r )rmk + Pk (r - rgl Pk r=0 k=l r=O k=lrgk?- (7) We will now derive a second set of lower and upper bounds for E[UJ ]. Let Bki denote the event that at least j coupons of type k arrive before the first of type i arrives. Then, using the conditional expectation inequality (Proposition 3.2.3 of [5]), we obtain that P(A?) - P(U Bj,i P(Bk, ) > p(Bj i) (8) i1 + P(M i 1 + Er:i,k J,r lB,) jk _ 1yF ? (Pk/(Pk + Pi))j i~k - r+ ri,k((Pk + Pi)/(Pk + Pi + Pr))' 516