Problème du secrétaire

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Problème de la secrétaire)
Aller à : navigation, rechercher

Le problème du secrétaire, de la secrétaire ou des secrétaires est un problème mathématique de théorie de l’arrêt optimal (en) en théorie de la décision, en théorie des probabilités et en statistique. Le problème est aussi connu sous le nom de problème de la princesse[1], et de problème du recrutement immédiat[2].

Énoncé[modifier | modifier le code]

Le contexte est le suivant : quelqu'un veut recruter un ou une secrétaire et voit défiler un nombre fini et connu de candidats. Pour chacun, il doit décider s'il l'engage ou pas. Si oui, il termine le processus de recrutement sans voir les autres candidats. Sinon, il n'a pas la possibilité de rappeler la candidate plus tard[3]. Dans le contexte de ce problème, le recruteur n'a pas accès à une valeur intrinsèque des candidats (comme « ce candidat vaut 7/10 » ), il ne peut que les comparer (par exemple «ce candidat est meilleur que le premier, mais moins bon que le deuxième »)[3].

Le but est de définir une stratégie qui maximise la probabilité d'engager le meilleur candidat.

Le problème peut être vu comme un problème algorithmique, dans le contexte des algorithmes onlines.

Stratégie[modifier | modifier le code]

La bonne stratégie[4] est de laisser passer 37 % des candidates (ou, plus précisément, une proportion 1/e), puis d'attendre d'avoir une candidate meilleure que toutes celles de ce premier échantillon[3]. On parle parfois de la règle des 37 %[1].

Analyse[modifier | modifier le code]

Extensions[modifier | modifier le code]

Sous certaines hypothèses, on peut étendre l'analyse au recrutement de plusieurs personnes[2].

Notes et références[modifier | modifier le code]

  1. a et b Michel Benaim et Nicole El Karaoui, Promenades aléatoires : Chaînes de Markov et simulations ; martingales et stratégies, Les éditions de l’École polytechnique, chap. 6.4 (« Arrêt optimal »), p. 210-211.
  2. a et b Claire Mathieu, « Support du cours « Algorithmes pour flux de données » au collège de France, le 16 janvier 2018 », sur Collège de France.
  3. a, b et c Etienne Ghys, « Décision », sur Images des maths,
  4. Pour un nombre de candidates tendant vers l'infini.