Exact results for a secretary problem

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 ba...

Full description

Saved in:
Bibliographic Details
Published in:Journal of applied probability 1996-09, Vol.33 (3), p.630-639, Article 630
Main Authors: Quine, M. P., Law, J. S.
Format: Article
Language:English
Subjects:
Backward induction
Conditional probabilities
Exact sciences and technology
Functions
Integers
Markov analysis
Markov chains
Markov processes
Mathematics
Optimal strategies
Optimization
Probability
Probability and statistics
Probability theory and stochastic processes
Research Papers
Sciences and techniques of general use
Stochastic processes
Studies
Theory
Transition probabilities
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 → ∞.
ISSN:0021-9002
1475-6072
DOI:10.2307/3215345