For the secretary (or best-choice) problem with an unknown number $N$ of objects, minimax-optimal stop rules and (worst-case) distributions are derived, under the assumption that $N$ is a random variable with unknown distribution, but known upper bound $n$. Asymptotically, the probability of selecting the best object in this situation is of order of $(\log n)^{-1}$. For example, even if the only information available is that there are somewhere between 1 and 100 objects, there is still a strategy which will select the best item about one time in five.
@article{1176990548,
author = {Hill, Theodore P. and Krengel, Ulrich},
title = {Minimax-Optimal Stop Rules and Distributions in Secretary Problems},
journal = {Ann. Probab.},
volume = {19},
number = {4},
year = {1991},
pages = { 342-353},
language = {en},
url = {http://dml.mathdoc.fr/item/1176990548}
}
Hill, Theodore P.; Krengel, Ulrich. Minimax-Optimal Stop Rules and Distributions in Secretary Problems. Ann. Probab., Tome 19 (1991) no. 4, pp. 342-353. http://gdmltest.u-ga.fr/item/1176990548/