Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-02T22:37:12.598Z Has data issue: false hasContentIssue false
  • English
  • Français

Exact results for a secretary problem

Part of: Stochastic processes Markov processes

Published online by Cambridge University Press:  14 July 2016

M. P. Quine  and
J. S. Law
M. P. Quine*
Affiliation:
University of Sydney
J. S. Law*
Affiliation:
University of Sydney
*
∗Postal address for both authors: School of Mathematics and Statistics, University of Sydney, NSW 2006, Australia.
∗Postal address for both authors: School of Mathematics and Statistics, University of Sydney, NSW 2006, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the following secretary problem: items ranked from 1 to n are randomly selected without replacement, one at a time, and to ‘win' is to stop at an item whose overall rank is less than or equal to s, given only the relative ranks of the items drawn so far. Our method of analysis is based on the existence of an imbedded Markov chain and uses the technique of backwards induction. In principal the approach can be used to give exact results for any value of s; we do the working for s = 3. We give exact results for the optimal strategy, the probability of success and the distribution of T, and the total number of draws when the optimal strategy is implemented. We also give some asymptotic results for these quantities as n → ∞.

Keywords

BACKWARDS INDUCTIONMARKOV CHAINOPTIMAL STOPPING

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory
Secondary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Type
Research Papers
Information
Journal of Applied Probability , Volume 33 , Issue 3 , September 1996 , pp. 630 - 639
Copyright
Copyright © Applied Probability Trust 1996 

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

Dynkin, E. B. (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl. 4, 627–629.Google Scholar
Dynkin, E. B. and Yushkevich, A. (1969) Markov Processes: Theorems and Problems. 1st edn. Plenum, New York.CrossRefGoogle Scholar
Ferguson, T. S. (1989) Who solved the secretary problem? Statist. Sci. 4, 282–296.Google Scholar
Frank, A. Q. and Samuels, S. M. (1980) On an optimal stopping problem of Gusein-Zade. Stoch. Proc. Appl. 10, 299–311.CrossRefGoogle Scholar
Freeman, P. R. (1983) The secretary problem and its extensions. Int. Statist. Rev. 51, 189–206.Google Scholar
Gilbert, J. and Mosteller, F. (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61, 35–73.CrossRefGoogle Scholar
Gusein-Zade, S. M. (1966) The problem of choice and the optimal stopping rule for a sequence of independent trials. Theory Prob. Appl. 11, 472–476.CrossRefGoogle Scholar
Lindley, D. V. (1961) Dynamic programming and decision theory. Appl. Stat. 10, 39–51.Google Scholar
Mucci, A. G. (1973) Differential equations and optimal choice problems. Ann. Statist. 1, 104–113.CrossRefGoogle Scholar