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