A universal bound for the maximal expected reward is obtained for stopping a sequence of independent random variables where the reward is a nonincreasing function of the rank of the variable selected. This bound is shown to be sharp in three classical cases: (i) when maximizing the probability of choosing one of the $k$ best; (ii) when minimizing the expected rank; and (iii) for an exponential function of the rank.
Publié le : 1992-05-14
Classification:
Optimal stopping,
rank,
sharp inequalities,
best choice problem,
secretary problem,
prophet inequality,
Schur convexity,
60G40
@article{1177005713,
author = {Hill, T. P. and Kennedy, D. P.},
title = {Sharp Inequalities for Optimal Stopping with Rewards Based on Ranks},
journal = {Ann. Appl. Probab.},
volume = {2},
number = {4},
year = {1992},
pages = { 503-517},
language = {en},
url = {http://dml.mathdoc.fr/item/1177005713}
}
Hill, T. P.; Kennedy, D. P. Sharp Inequalities for Optimal Stopping with Rewards Based on Ranks. Ann. Appl. Probab., Tome 2 (1992) no. 4, pp. 503-517. http://gdmltest.u-ga.fr/item/1177005713/