Problème de Robbins

Le problème de Robbins, aussi appelé quatrième problème de la secrétaire, est un problème mathématique de théorie des probabilités et plus particulièrement de théorie de l'arrêt optimal. Il doit son nom au mathématicien Herbert Robbins qui l'a énoncé la première fois en 1990. Le problème de Robbins reste jusqu'à ce jour encore ouvert.

Énoncé

Informellement, le problème est le suivant : un recruteur travaillant dans une entreprise cherche à embaucher un secrétaire. Pour cela il va faire passer un entretien d'embauche à un certain nombre de candidats (ce nombre est fini et connu du recruteur). À la fin de chaque entretien, le recruteur attribue une note (un nombre réel) entre 0 et 1 en fonction des performances du candidat. Plus la note est proche de 0, plus le candidat est qualifié. On suppose que pour chaque candidat toutes les notes possibles sont équiprobables (les candidats ont autant de chance d'être bons que mauvais). On suppose aussi que les notes des candidats n'influent pas sur les performances des autres. A la fin de chaque entretien le recruteur doit prendre une décision irrévocable : soit il accepte le candidat et l'embauche sur le champ sans faire passer l'entretien aux prochains ; soit il refuse le candidat et alors il ne pourra plus revenir sur sa décision. Le problème consiste alors à déterminer une stratégie optimale permettant de minimiser le rang du candidat retenu (le rang étant le classement par rapport aux autres, par exemple le candidat de rang 1 est le meilleur de tous, celui de rang 2 est le deuxième meilleur, etc).

Plus formellement, soit $X_1,\dots ,X_n$ des variables i.i.d de loi uniforme dans $[0,1]$. Pour tout $0\le k\le n$, on pose ${ℱ}_k:=\sigma (X_1,\dots ,X_k)$ la tribu engendrée par les $k$ premières variables aléatoires $X_1,\dots ,X_k$. On définit le rang absolu :

$R_k:=\sum _{i=1}^n{\mathrm{𝟏}}_{X_i\le X_k}$.

On cherche alors un temps d'arrêt optimal ${\tau }^{*}$ qui minimiserait la quantité $V_n:=\underset{\tau }{\inf }𝔼[R_{\tau }]$ où l'infimum est pris sur l'ensemble des temps d'arrêt adaptés à la filtration $({ℱ}_k)$.

Résultats

Les premières valeurs de $V_n$ sont connues pour $n=1,2,3,4$ :

$V_1=1$, $V_2=1,25$, $V_3=1,39155\dots$ et $V_4=1,4932\dots$

La complexité des calculs grandit très vite et calculer $V_4$ n'est pas trivial.

Un argument de «prophète» permet de montrer que la suite $(V_n)$ est croissante. De plus elle est bornée. En effet, dans le troisième problème de la secrétaire, qui est identique au problème de Robbins à la différence que le recruteur n'a accès qu'aux rangs relatifs et non aux notes des candidats, la suite associée $(V{\text{'}}_n)$ est bornée. Or il est clair que $V_n\le V{\text{'}}_n$ pour tout $n\ge 1$. Ainsi la suite $(V_n)$ converge vers une limite notée $V$.

Actuellement la valeur de $V$ est inconnue et le meilleur encadrement connu est $1.909\le V\le 2,32614$. La borne inférieure a été trouvée en utilisant une méthode de troncation tandis que la borne supérieure a été trouvée en utilisant une stratégie à seuil sans mémoire modifiée.

Stratégie à seuil sans mémoire

Une stratégie à seuil sans mémoire consiste à sélectionner le candidat numéro $k$ si et seulement si sa note est inférieure à un certain seuil, sans se soucier des performances des candidats précédents (d'où l'appellation «sans mémoire»). Plus formellement, fixons une fonction de seuil $s:\{1,\dots ,n\}\to [0,1]$ telle que $s(n)=1$. La stratégie à seuil sans mémoire associée à la fonction $s$ correspond alors au temps d'arrêt

$\tau :=\inf \{k:X_k\le s(k)\}$.

Par exemple en prenant

$s(k):=\frac{2}{n-k+2}\mathrm{\forall }k=1,2,\dots ,n$

on obtient que l'espérance de la note du candidat retenu vérifie, pour tout $n\ge 1$ :

$𝔼(R_{\tau })\le 7/3$.

Cela implique donc en particulier que $V\le 7/3$.

Articles connexes

• Problème du secrétaire