On an Optimal Stopping Problem of Gusein-Zade
Abstract
We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r = 25, we give the limiting (as n approaches infinity) optimal risk (probability of not selecting) one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r = 10, and for r = 15, 20 and 25.) We show that, for large n and r, the optimal risk is approximately (l-t*) to the rth power where t* is approx. .2834 is obtained as the root of a function which is the solution to a certain differential equation; and the optimal stopping rule tau sub r,n lets approximately t*n arrivals go by then stops 'almost immediately' in the sense that tau sub r,n/n approaches t* in probability as n approaches infinity, r approaches infinity.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 05, 1979
- Accession Number
- ADA065456
Entities
People
- Arthur Q. Frank
- Stephen M. Samuels
Organizations
- Stanford University