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$? 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 made 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 achieve an asymptotic optimality gap of about one per cent. For an analytic lower bound, we reveal structural properties of the optimal strategy and utilise self-similarity. For the upper bound, we pursue an idea of thinned memory to construct embedded stopping problems for low-dimensional ‘sliding window’ processes, whose terminal states are evaluated numerically using the memoryless strategies |