## Optimal selection of stochastic intervals under a sum constraint

### E.G. Coffman, Jr, L. Flatto and R.R. Weber, Adv. Appl. Prob.19 454-473, 1987. Abstract

We model a selection process arising in certain storage problems.  A sequence
$(X_1,\ldots,X_n)$ of non-negative, independent and identically distributed
random variables is given.  $F(x)$ denotes the common distribution of the
$X_i$'s.  With $F(x)$ given we seek a decision rule for selecting a maximum
number of $X_i$'s subject to the following constraints: (1) the sum of the
elements selected must not exceed a given constraint $c>0$, and (2) the $X_i$'s
must be inspected in strict sequence with the decision to accept or reject an
element being final at the time it is inspected.

we prove first that there exists such a rule of threshold type, i.e., the $i$th
element inspected is accepted if and only if it is no larger than a threshold
which depends only on $i$ and the sum of the elements already accepted.  Next,
we prove that if $F(x)\simAx^\alpha$ as $x\rightarrow 0$ for some $A$,
$\alpha>0$, hen for fixed $c$ the expected  number, $E_n(c)$, selected by an
optimal threshold is characterized by
$E_n(c) \sim \left[ A\left(\frac{\alpha+1} {\alpha} c\right)^\alpha n \right]^{1/(1+\alpha)} \quad\mathrm{as }n\rightarrow\infty.$
Asymptotics as $c\rightarrow\infty$ and $n\rightarrow\infty$ with $c/n$ help
fixed are derived, and connections with several closely related, well-known
problems are brought out and discussed.