Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-25T06:01:24.328Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal Sequential selection of n random variables under a constraint

Published online by Cambridge University Press:  14 July 2016

R. W. Chen ,
V. N. Nair ,
A. M. Odlyzko ,
L. A. Shepp  and
Y. Vardi
R. W. Chen*
Affiliation:
University of Miami
V. N. Nair*
Affiliation:
University of Miami
A. M. Odlyzko*
Affiliation:
University of Miami
L. A. Shepp*
Affiliation:
University of Miami
Y. Vardi*
Affiliation:
AT&T Bell Laboratories
*
∗Postal address: Department of Mathematics, University of Miami, Coral Gables, FL 33124, U.S.A.
∗∗Postal address: Mathematics and Statistics Research Center, AT&T Bell Laboratories, Murray Hill, NJ 07974, U.S.A.
∗∗Postal address: Mathematics and Statistics Research Center, AT&T Bell Laboratories, Murray Hill, NJ 07974, U.S.A.
∗∗Postal address: Mathematics and Statistics Research Center, AT&T Bell Laboratories, Murray Hill, NJ 07974, U.S.A.
∗∗Postal address: Mathematics and Statistics Research Center, AT&T Bell Laboratories, Murray Hill, NJ 07974, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

We observe a sequence {Xk}k≧1 of i.i.d. non-negative random variables one at a time. After each observation, we select or reject the observed variable. A variable that is rejected may not be recalled. We want to select N variables as soon as possible subject to the constraint that the sum of the N selected variables does not exceed some prescribed value C > 0. In this paper, we develop a sequential selection procedure that minimizes the expected number of observed variables, and we study some of its properties. We also consider the situation where N → ∞and C/N → α > 0. Some applications are briefly discussed.

Keywords

BELLMAN EQUATIONDYNAMIC PROGRAMMINGENGINEERING APPLICATIONSSECRETARY PROBLEM
Type
Research Papers
Information
Journal of Applied Probability , Volume 21 , Issue 3 , September 1984 , pp. 537 - 547
Copyright
Copyright © Applied Probability Trust 1984 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This author's research was done while consulting at Bell Laboratories.

References

[1] Campbell, G. and Samuels, S. M. (1981) Choosing the best of the current crop. Adv. Appl Prob. 15, 510–532.Google Scholar
[2] Chow, Y. S. Moriguiti, S., Robbins, H. and Samuels, S. M. (1964) Optimal selection based on relative rank. Israel J. Math. 2, 81–90.Google Scholar
[3] Chow, Y. S., Robbins, H. and Siegmund, D. (1971) Great Expectations: The Theory of Optimal Stopping. Houghton Miffin Company, Boston.Google Scholar
[4] Gilbert, J. and Mosteller, F. (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.Google Scholar
[5] Mallows, C. L., Nair, V. N., Shepp, L. A. and Vardi, Y. (1983) Optimal sequential selection of secretaries.Google Scholar