Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-23T07:39:38.912Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal selection based on relative ranks of a sequence by ties

Published online by Cambridge University Press:  01 July 2016

Gregory Campbell
Gregory Campbell*
Affiliation:
Purdue University
*
∗Present address: Division of Computer Research and Technology, National Institutes of Health, Bethesda, MD 20205, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

The optimal selection of a maximum of a sequence with the possibility of ties is considered. The object is to examine each observation in the sequence of known length n and, based only on the relative rank among predecessors, either to stop and select it as a maximum or to continue without recall. Rules which maximize the probability of correctly selecting a maximum from a sequence with ties are investigated. These include rules which randomly break ties, rules which discard tied observations, and minimax rules based on the atoms of a discrete distribution function. If the sequence is random from F, a random distribution function from a Dirichlet process prior with non-atomic parameter, optimal rules are developed. The limiting behavior of these rules is studied and compared with other rules. The selection of the parameter of the Dirichlet process regulates the ties.

Keywords

BEST CHOICE PROBLEMDIRICHLET PROCESS PRIOROPTIMAL STOPPINGRELATIVE RANKSSECRETARY PROBLEM
Type
Research Article
Information
Advances in Applied Probability , Volume 16 , Issue 1 , March 1984 , pp. 131 - 146
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

Research supported in part by National Science Foundation Grant MCS78–02895.

References

Antoniak, C. E. (1974) Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems. Ann. Statist. 2, 1152–1174.Google Scholar
Berk, R. H. and Savage, I. R. (1979) Dirichlet processes produce discrete measures: an elementary proof. Contributions to Statistics-Jaroslav Hájek Memorial Volume, ed. Jureckova, J., Reidel, Dordrecht, 25–32.Google Scholar
Campbell, G. (1983) The maximum of a sequence with prior information. Commun. Statist. Sequential Analysis 1, 177–191.Google Scholar
Campbell, G. and Hollander, M. (1978) Rank order estimation with the Dirichlet prior. Ann. Statist. 6, 142–153.Google Scholar
Campbell, G. and Samuels, S. M. (1981) Choosing the best of the current crop. Adv. Appl. Prob. 13, 510–532.Google Scholar
Ewens, W. J. (1972) The sampling theory of selectively neutral alleles. Theoret. Popn Biol. 3, 87–112.Google Scholar
Ferguson, T. S. (1973) A Bayesian analysis of some nonparametric problems. Ann. Statist. 1, 209–230.Google Scholar
Gianini-??Ttit, 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
Govindarajulu, Z. (1975) The secretary problem: optimal selection with interview cost. Proc. Symp. Statistics and Related Topics, Carleton University.Google Scholar
Irle, A. (1980) On the best choice problem with random population size. Z. Operat. Res. 24, 177–190.Google Scholar
Korwar, R. M. and Hollander, M. (1973) Contributions to the theory of Dirichlet processes. Ann. Prob. 1, 705–711.Google Scholar
Lorenzen, T. J. (1979) Generalizing the secretary problem. Adv. Appl. Prob. 11, 384–396.Google Scholar
Petruccelli, J. D. (1981) Best choice problems involving uncertainty of selection and recall of observations. J. Appl. Prob. 18, 415–425.Google Scholar
Presman, E. L. and Sonin, I. M. (1972) The best choice problem for a random number of objects. Theory Prob. Appl. XVIII, 657–668.Google Scholar
Rasmussen, W. T. (1975) A generalized choice problem. J. Optimization Theory Appl. 15, 311–325.Google Scholar
Rasmussen, W. T. and Robbins, H. (1975) The candidate problem with unknown population size. J. Appl. Prob. 12, 692–701.Google Scholar
Samuels, S. M. (1981) Minimax stopping rules when the underlying distribution is uniform. J. Amer. Statist. Assoc. 76, 188–197.Google Scholar
Sethuraman, J. and Tiwari, R. C. (1982) Convergence of Dirichlet measures and the interpretation of their parameter. 3rd Purdue Symp. Decision Theory and Related Topics. Google Scholar
Smith, M. H. (1975) A secretary problem with uncertain employment. J. Appl. Prob. 12, 620–624.Google Scholar
Smith, M. H. and Deely, J. J. (1975) A secretary problem with finite memory. J. Amer. Statist. Assoc. 70, 357–361.Google Scholar
Stewart, T. J. (1978) Optimal selection from a random sequence with learning of the underlying distribution. J. Amer. Statist. Assoc. 73, 775–780.Google Scholar
Yang, M. C. K. (1974) Recognizing the maximum of a random sequence based on relative rank with backward solicitation. J. Appl. Prob. 11, 504–512.Google Scholar