Le problème du secrétaire
Une directrice des ressources humaines souhaite enbaucher un nouveau secrétaire. Un nombre $n$ de candidats se présente à l'entretien d'embauches, dans un ordre complètement aléatoire. Après chaque audition, la directrice est capable de comparer un candidat avec les candidats précédents, mais elle doit décider de suite si elle l'embauche ou non. Si elle l'embauche, elle n'auditionne pas les candidats suivants. Si elle ne l'embauche pas, elle ne pourra pas le rappeler plus tard et passe au candidat suivant. Bien entendu, si elle atteint le dernier candidat, elle doit l'embaucher. Quelle est la meilleure stratégie pour optimiser la chance de recruter le meilleur candidat? Quelle est alors, avec cette stratégie, la probabilité de recruter le meilleur?
Ce problème peut sembler assez compliqué, et on pourrait penser que, même avec la meilleure stratégie, la probabilité de recruter le meilleur candidat devient très petite avec $n$. Il n'en est rien, et on peut démontrer les résultats suivants :
- pour de grandes valeurs de $n,$ la stratégie optimale est d'auditionner 37% des candidats (ou plus précisément une proportion $1/e$ de candidats) en les rejetant tous, puis de recruter ensuite le premier candidat qui est meilleur que tous les précédents.
- avec cette stratégie, la probabilité de recruter le meilleur candidat tend vers $1/e$, et est toujours supérieure ou égale à $1/e\simeq 0,\!37.$
Ainsi, si l'on si prend bien, il y a toujours au moins 37% de chances de recruter le meilleur candidat!