Probabilités et statistiquesNotion · Glossaire
Problème du secrétaire
Le problème du secrétaire est un problème de décision optimale en probabilités. On doit choisir le meilleur candidat parmi n candidats présentés un à un, en décidant immédiatement et irrévocablement après chaque présentation. La stratégie optimale consiste à rejeter les r-1 premiers candidats sans embaucher (où r est environ n/e), puis à embaucher le premier candidat meilleur que tous les précédents, ou le dernier candidat si aucun nouveau record ne s’est présenté auparavant. Cette stratégie maximise la probabilité de choisir le meilleur candidat, qui tend vers 1/e.
Sommaire
Ce que vous allez apprendre
- Savoir pourquoi la stratégie commence par une phase d’observation.
- Appliquer la règle à une série de dix candidats.
- Distinguer la limite 1/e du seuil exact pour une taille finie.
- Reconnaître les hypothèses qui rendent le modèle applicable.
En clair
Dix candidats se présentent l’un après l’autre. Après chaque entretien, il faut répondre sans pouvoir rappeler une personne refusée. Choisir trop tôt risque de laisser passer mieux ; attendre trop longtemps risque de perdre une excellente candidature.
La stratégie du problème du secrétaire réserve d’abord quelques entretiens à l’observation. Le meilleur niveau aperçu devient un seuil. Dès qu’un candidat ultérieur dépasse ce seuil, il est choisi. Pour une longue série, la phase d’observation représente environ 37 % des candidats.
Définition
Le problème du secrétaire est un modèle d’arrêt optimal : il faut sélectionner le meilleur élément d’une suite révélée progressivement. Le nombre total de candidats, noté n, est connu. Leur ordre d’arrivée est supposé aléatoire, leurs qualités sont toutes distinctes et, à chaque étape, seul leur classement relatif parmi les candidats déjà vus est nécessaire. Un refus est définitif et une acceptation termine la sélection.
Pour un rang de bascule entier noté r, avec 2 ≤ r ≤ n, la règle rejette les r − 1 premiers candidats, puis accepte le premier qui soit meilleur que tous ses prédécesseurs. Si aucun candidat des rangs r à n − 1 ne franchit ce seuil, le dernier candidat est accepté par défaut. La probabilité de choisir le meilleur parmi les n candidats est :
Le choix entier optimal dépend de n. Lorsque n devient grand, r est proche de n/e : on observe donc environ 1/e, soit 37 %, de la série. La probabilité maximale tend elle aussi vers 1/e, soit environ 36,8 %. Ces pourcentages sont des limites, pas des égalités exactes pour toute taille finie.
Un exemple, pas à pas
Une entreprise doit choisir parmi 10 candidats. Leurs qualités, sur une échelle fictive où 10 est le meilleur rang, arrivent dans l’ordre suivant : 6, 2, 8, 7, 5, 10, 9, 4, 3, 1. Le diagramme de cette série rend visibles la phase d’observation, le seuil obtenu et l’arrêt.
1. Le nombre total vaut n = 10. La valeur n/e est environ 3,68 ; la règle optimale pour cette taille rejette les 3 premiers candidats et commence donc à décider au quatrième.
2. Parmi les qualités 6, 2 et 8 observées, le record vaut 8. Les candidats 4 et 5 obtiennent 7 puis 5 : aucun ne dépasse le seuil. Le candidat 6 obtient 10, dépasse 8 et est immédiatement choisi.
3. Le contrôle est direct : aucune des qualités restantes, 9, 4, 3 et 1, ne dépasse 10. Le candidat choisi est donc bien le meilleur des dix.
La probabilité de réussir avant de connaître l’ordre vaut ici , soit environ 39,87 %. Une autre permutation des mêmes qualités pourrait faire échouer exactement la même règle.
En pratique
Dans une sélection séquentielle, cette règle donne un repère lorsque les options arrivent au hasard et qu’une réponse immédiate est exigée. On préfère cette stratégie à un choix dès le premier candidat lorsque l’objectif précis est de maximiser la chance d’obtenir le meilleur de toute la série.
Le geste pratique consiste à fixer avant le départ la longueur de la phase d’observation, à mémoriser son meilleur niveau, puis à s’arrêter au premier nouveau record. Si aucun nouveau record ne se présente auparavant, le dernier candidat est choisi par défaut. Fixer la règle à l’avance évite de déplacer le seuil selon les candidats déjà rencontrés.
Si les options peuvent être rappelées, comparées toutes ensemble ou évaluées par des notes incertaines, le modèle ne décrit plus fidèlement la décision. Une comparaison globale ou une méthode tenant compte du coût et de l’incertitude devient alors préférable.
À ne pas confondre
Avec un classement complet. Un classement attend d’avoir vu tous les candidats avant de choisir ; le problème du secrétaire impose une décision irrévocable à chaque arrivée. Si les dix dossiers restent disponibles jusqu’à la fin, il suffit de les comparer tous.
Avec la maximisation de la qualité moyenne. La règle classique maximise la probabilité de sélectionner le meilleur rang, et non la note moyenne du candidat retenu. Deux stratégies peuvent donc être départagées différemment selon l’objectif choisi.
Limites et pièges
37 % n’est pas un seuil exact universel. C’est une approximation asymptotique. Pour 10 candidats, rejeter les 3 premiers donne environ 39,87 % de réussite ; il faut comparer les choix entiers voisins pour une petite série.
L’ordre doit être aléatoire. Si les meilleurs candidats arrivent systématiquement tôt ou tard, les probabilités du modèle changent. Il faut alors modéliser cet ordre plutôt que reprendre mécaniquement la règle des 37 %.
Les ex æquo demandent une convention. La règle « meilleur que tous les précédents » suppose des rangs distincts. Avec des notes égales, il faut préciser si l’égalité franchit le seuil et comment plusieurs meilleurs candidats sont départagés.
Le nombre total et l’irrévocabilité sont structurants. Si n est inconnu, si un refus peut être annulé ou si plusieurs choix sont permis, la formule classique ne s’applique plus telle quelle. Le problème doit être reformulé avec ces nouvelles règles.
Pour aller plus loin
Le nombre e éclaire la constante qui fixe asymptotiquement la durée d’observation et la probabilité maximale de succès.
La probabilité conditionnelle aide à suivre la chance que le meilleur candidat apparaisse après la phase d’observation.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres