‘Wald's Lemma' for sums of order statistics of i.i.d. random variables (Q3978282)

Considered is a sequence \(X_ 1,X_ 2,\dots\) of positive, i.i.d. random variables with known distribution function having a finite mean \(\mu\). For a given \(s>0\), let \(N_ n=N(n,s)\) be the largest number \(k\) such that the sum of the smallest \(k\) \(X\)'s does not exceed \(s\), and \(M_ n=M(n,s)\) be the largest number \(k\) such that the sum of the largest \(k\) \(X\)'s does not exceed \(k\). This context allows the nice interpretation as ` baker's problem', describing the situation where a baker opens his shop in the morning finding \(n\) clients in front of the door, all waiting for fresh rolls. The baker has a supply of \(s\) rolls and the customers' demands \(X_ 1,\dots,X_ n\) are i.i.d. with common distribution function \(F\). The interesting question arising from this is what is the number of demands he can serve completely if he serves the smallest demands first, the demands in order of arrival (FCFS), or the largest demands first? In mathematical formulation we ask for the asymptotic behaviour of \(E(X_ n)\), \(E(M_ n)\), \(N_ n\), \(M_ n\), and the corresponding `stopped' order statistics \(X_{(N_ n)}\) and \(X_{(n-M_ n+1)}\) as \(n\to\infty\). This is done in the present paper in case of continuous \(X\)'s both for fixed \(s\), and where \(s=s_ n\) is an increasing function of \(s\). In the large-sample case \((n\to\infty)\) and large-supply case \((s_ n/n\to\sigma)\) we have for \(n\to\infty\) \(\lim N_ n/n=1\) a.s. and \(\lim E(N_ n)/n=1\). Let \(\sigma\in(0,\mu)\), \(\sigma=\int^ \tau_ a x dF(x)\), \(F(a)=0\), and \(s_ 1,s_ 2,\dots\) a sequence such that \(\lim s_ n/n=\sigma\). Then for \(n\to\infty\) follows a.s. \[ \lim X_{N_ n,n}=\tau,\quad\lim N_ n/n=F(\tau),\quad\lim E(N_ n)/n=F(\tau). \] A corresponding theorem holds for \(\lim X_{n-M_ n+1,n}\), \(\lim M_ n/n\) and \(\lim E(M_ n)/n\). In case of large-samples \((n\to\infty)\) and small-supply (\(s\) fixed) a central and rather general condition is given by \[ \limsup F(\lambda x)/F(x)<1\qquad\text{for}\qquad 0<\lambda<1\qquad\text{and}\qquad x\to 0+. \] If \(t_ n\) is defined by \(n\int^{t_ n}_ 0 x dF(x)=s\) we have \(N_ n\sim nF(t_ n)\) in probability as \(n\to\infty\); moreover \(E(N_ n)\leq nF(t_ n) \forall n\). Additional remarks and comments are made especially for the (FCFS)- case.