Minimax-optimal stop rules and distributions in secretary problems (Q756847): Difference between revisions

For a fixed integer \(n\geq 2\) let N be a random variable assuming values in \(\{\) 1,2,...,n\(\}\) and D the set of all distributions of such N. The authors solve the minimax-optimal secretary problem - win if best - where the infimum is taken over D and the supremum over all stopping times. They derive the value explicitly (Theorem A), give the minimax-optimal stop rule (Theorem B) and the distribution yielding the value (Theorem C). The authors' results show several interesting features: Firstly, the minimax-optimal distribution in this model (Presman-Sonin model) is unique. Then the optimal value tends to zero like 1/log(n) as n grows. (Samuels' concise argument suffices to show that c/log(n) is a lower bound for some \(c<1.)\) Both features contrast the 1/e-law for the model where options arrive independently according to the same continuous arrival time distribution, where this value is 1/e, which is achieved, among others, by \(P(N=\infty)=1.\) Thirdly, the value is an expression in which each term has its own probabilistic interpretation, but the whole expression is definitely difficult to interpret. And finally, the minimax distribution of N (which puts, except for n, no probability mass on the unique stopping island for the deterministic \(N=n\) case) is seemingly a new distribution on \(\{\) 1,2,...,n\(\}\).