Largest-first sequential selection with a sum constraint

Scan the order statistics XÅ(1Å)≥XÅ(2Å)≥ëëë≥XÅ(nÅ) of n independent samples from U[0,1] in the order listed. The i-th number scanned, XÅ(iÅ), is selected if and only if the sum of XÅ(iÅ) and the numbers already selected out of the first i-1 is no greater than 1. Let N(n) denote the total number selected. The authors prove that NÅ••limnÅ⇒Å•E[N(n)]=1+ΣkÅ≥1E[N(k)]/2^k’+¹•5/3, and that ℝNÅ•-E[N(n)]ℝ•n2’-ⁿ. The 5/3 bound is close; numerical evaluation of a recursive formula shows that NÅ•=1.64659337±3×10’-⁸. Similar convergence results are obtained for the function W(n)=1-S(n), where S(n) is the sum of the items selected.