##
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.

**back to list of papers**