When Should You Stop and what do You Get? Some Secretary Problems

Ester Samuel-Cahn

A version of a secretary problem is considered: Let Xj, j = 1,...,n be i.i.d. random variables. Like in the classical secretary problem the optimal stopper only observes Yj = 1, if Xj is a (relative) record, and Yj = 0, otherwise. The actual Xj-values are not revealed. The goal is to maximize the expected X-value at which one stops. We describe the structure of the optimal stopping rule, its asymptotic properties and the asymptotic expected reward. Three different families of distributions of X are considered, belonging to the three different domains of attraction of the maximum. It is shown that both the time of stopping, as well as the expected reward are strongly distribution dependent. The last section discusses an ‘inverse' of ‘Robbins' Problem'.

October, 2005
Published in: 
Published as "Optimal Stopping for I.I.D. Random Variables", Sequential Analysis 26 (2007), 395-401