Robbins' Minimum Rank Problem
A talk in the Oberseminar Probability Theory and Mathematical Statistics series by
Alexander Gnedin from Queen Mary University London
| Abstract: | The following version of the ‘secretary problem’ was proposed by Herbert Robbins (Amherst, Summer 1990). Let $X_1,\ldots,X_n$ be independent random scores drawn from the uniform distribution on
$[0,1]$ (or any other continuous distribution). The scores are observed sequentially until exactly one of them is selected, with the loss incurred for choosing score $X_k, ~k\in [n],$ set equal to its total rank among all $n$ scores:
$$
R_{k}:=\#\{i\in [n]: X_i\leq X_k\}.
$$
Suppose that the admissible selection strategies are non-anticipating stopping rules $\tau$ adapted to the sequence $X_1,\ldots,X_n$. What is the minimum expected rank
$$
v_n:=\min_\tau {\mathbb E}R_{\tau},
$$
and what is a stopping rule $\tau_n^*$ achieving $v_n$? The ultimate objective is to find the more informative limit $v=\lim_{n\to\infty} v_n$. Unlike many other related optimisation tasks, which vary in the type of information flow and objective, the problem is inherently infinite-dimensional, because an optimal decision at any stage before stopping depends on all scores observed so far. Explicit solutions are only known for $n\leq 4$. For large $n$, the major progress to date has been achieved in early work that focused on memoryless strategies with constant thresholds. In this talk, we employ a planar Poisson limit form of the problem to explore memoryless rules and their extensions which account also for the initial rank. For memoryless rules we confirm the value proposed previously by numerical extrapolation from relatively small sample sizes. To outperform the memoryless rules explicitly we pursue an idea of thinned memory by constructing embedded stopping problems for low-dimensional ‘sliding window’ processes, whose terminal states are evaluated using the memoryless strategies. We further discuss recent results on Poisson limits in related problems, such as the memoryless best-choice and score-extremal problems for the discrete uniform i.i.d. sampling. |