Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T05:22:03.540Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic results for the best-choice problem with a random number of objects

Published online by Cambridge University Press:  14 July 2016

Masami Yasuda
Masami Yasuda*
Affiliation:
Chiba University
*
∗Postal address: College of General Education, Chiba University, Yayoi-cho, Chiba, 260, Japan.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper considers the best-choice problem with a random number of objects having a known distribution. The optimality equation of the problem reduces to an integral equation by a scaling limit. The equation is explicitly solved under conditions on the distribution, which relate to the condition for an OLA policy to be optimal in Markov decision processes. This technique is then applied to three different versions of the problem and an exact value for the asymptotic optimal strategy is found.

Keywords

OPTIMAL STOPPING PROBLEMBEST CHOICERANDOM NUMBER OF OBJECTSSCALING LIMIT
Type
Research Papers
Information
Journal of Applied Probability , Volume 21 , Issue 3 , September 1984 , pp. 521 - 536
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.)

References

Abdel-Hamid, A. R., Bather, J. A. and Trustrum, G. B. (1982) The secretary problem with unknown number of candidates. J. Appl. Prob. 19, 619–630.Google Scholar
Bartoszynski, R. and Govindarajulu, Z. (1978) The secretary problem with interview cost. Sankhya B 40, 11–28.Google Scholar
Bremaud, P. (1981) Point Processes and Queues, Martingale Dynamics. Springer-Verlag, New York.CrossRefGoogle Scholar
Chow, Y. S., Robbins, H. and Siegmund, D. (1971) Great Expectations: The Theory of Optimal Stopping. Houghton Mifflin, Boston, Ma.Google Scholar
Degroot, M. H. (1970) Optimal Statistical Decisions. McGraw-Hill, New York.Google Scholar
Derman, C., Lieberman, G. J. and Ross, S. M. (unpublished) On the candidate problem with a random number of candidates.Google Scholar
Dynkin, E. B. and Yuskevich, A. A. (1969) Theorems and Problems in Markov Processes. Plenum Press, New York.Google Scholar
Feller, W. (1966) An Introduction to Probability Theory and Its Applications, Vol. II. Wiley, New York.Google Scholar
Gianini, J. (1979) Optimal selection based on relative ranks with a random number of individuals. Adv. Appl. Prob. 11, 720–736.Google Scholar
Gilbert, J. P. and Mosteller, F. (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.Google Scholar
Gusein-Zade, S. W. (1966) The problem of choice and the optimal stopping rule for a sequence of independent trials. Theory Prob. Appl. 11, 472–476.CrossRefGoogle Scholar
Irle, A. (1980) On the best choice problem with random population size. Z. Operat. Res. 24, 177–190.Google Scholar
Lorenzen, T. J. (1981) Optimal stopping with sampling cost: The secretary problem. Ann. Prob. 9, 167–172.Google Scholar
Mucci, A. G. (1973) Differential equations and optimal choice problems. Ann. Statist. 1, 104–113.CrossRefGoogle Scholar
Nikolaev, M. L. (1977) On a generalization of the best choice problem. Theory Prob. Appl. 22, 187–190.CrossRefGoogle Scholar
Presman, E. L. and Sonin, I. M. (1972) The best choice problem for a random number of objects. Theory Prob. Appl. 17, 657–668.CrossRefGoogle Scholar
Rasmussen, W. T. and Robbins, H. (1975) The candidate problem with unknown population size. J. Appl. Prob. 12, 692–701.Google Scholar
Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden Day, San Francisco.Google Scholar
Sakaguchi, M. (1978) Dowry problem and OLA policies. Res. Stat. Appl. Res. JUSE 25, 124–128.Google Scholar
Sakaguchi, M. (1979) A generalized secretary problem with uncertain employment. Math. Japonica 23, 647–653.Google Scholar
Smith, M. H. (1975) A secretary problem with uncertain employment. J. Appl. Prob. 12, 620–624.CrossRefGoogle Scholar
Stewart, T. J. (1981) The secretary problem with an unknown number of options. Operat. Res. 29, 130–145.CrossRefGoogle Scholar
Tamaki, M. (1979a) OLA policy and the best choice problem with random number of objects. Math. Japonica 24, 451–457.Google Scholar
Tamaki, M. (1979b) Recognizing both the maximum and the second maximum of a sequence. J. Appl. Prob. 16, 803–812.Google Scholar