La règle des 37 %

Les candidats se présentent un à un, dans un ordre aléatoire. Vous pouvez comparer chacun aux précédents, mais vous devez l’accepter ou le refuser sur-le-champ, sans pouvoir le rappeler. Choisissez combien de candidats écarter d’emblée ; la règle retient ensuite le premier qui les surpasse tous.

Probabilité de choisir le meilleur en écartant les k premiers	$P(k)=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Seuil optimal pour n grand	$k^*\approx\frac{n}{e}$
Probabilité correspondante	$P(k^*)\to\frac{1}{e}\approx0.3679$

Exemple résolu — La règle des 37 %

Seuil optimal k*	4
Probabilité de choisir le meilleur avec k*	39,84%
n/e, pour comparaison	4,05
Probabilité de choisir le meilleur au hasard	9,09%
Probabilité que le meilleur ait été écarté	36,36%
Probabilité d’atteindre le dernier candidat	40%

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — La règle des 37 %

Dans le problème du secrétaire, n candidats se présentent dans un ordre aléatoire. Chacun ne peut être comparé qu’aux précédents et doit être accepté ou refusé immédiatement, de façon définitive. La règle du seuil écarte les k premiers candidats, puis retient le premier qui les surpasse tous.

D’où vient la formule

Distinguez les cas selon la position du meilleur. Notez B la position du meilleur candidat et W l’événement « choisir le meilleur ». Toutes les positions de 1 à n sont équiprobables pour B.
$P(B=i)=\frac{1}{n},\qquad i=1,\dots,n$
Si le meilleur est parmi les k premiers, il est perdu. La règle ne permet aucun retour en arrière : ces positions ne contribuent donc pas à la probabilité de réussite.
$B\le k:\quad P(W\mid B)=0$
Pour choisir le meilleur à la position i > k, il faut n’avoir retenu personne entre k + 1 et i − 1. Cela se produit exactement lorsque le meilleur des i − 1 premiers candidats se trouve parmi les k premiers : alors seulement, aucun candidat intermédiaire ne dépasse la référence. Chacune des i − 1 positions a la même probabilité d’être celle de ce candidat.
$B=i>k:\quad P(W\mid B=i)=\frac{k}{i-1}$
Sommez sur les positions possibles.
$P(k)=\sum_{i=k+1}^{n}\frac{1}{n}\cdot\frac{k}{i-1}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}$
Faites tendre n vers l’infini. En posant x = k/n, la somme devient une intégrale et la probabilité tend vers −x ln x. La dérivée, −ln x − 1, s’annule en x = 1/e, où la probabilité vaut 1/e ≈ 36,79 %.
$P\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x,\qquad\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\iff x=\frac{1}{e}$

Suppose: Seuls les rangs sont observés, jamais les scores ; tous les ordres d’arrivée sont équiprobables ; un candidat refusé ne peut pas être rappelé et un candidat retenu accepte toujours ; tout choix autre que le meilleur compte comme un échec.

Problèmes entièrement résolus

Trois candidats, tous les ordres possibles 3 étapes
Trois candidats se présentent dans un ordre aléatoire. Représentez chaque ordre par la suite des rangs à l’arrivée (1 = meilleur). Vous écartez le premier candidat, puis retenez le premier qui surpasse tous les précédents. Dans combien des six ordres choisissez-vous le meilleur ? Vérifiez avec la formule.

Ouvrez ce problème dans l'outil
1. Les six ordres possibles :
  
  $123,\quad 132,\quad 213,\quad 231,\quad 312,\quad 321$
2. Le premier candidat sert de référence. Dans 213 et 231, le meilleur surpasse le 2 ; dans 312, le 1 arrive en deuxième position et est retenu. Dans 123 et 132, personne ne surpasse le 1, qui a été écarté : le dernier est donc retenu. Dans 321, le 2 surpasse le 3 et est retenu avant l’arrivée du 1 :
  
  $213\to1,\quad 231\to1,\quad 312\to1;\qquad 123\to3,\quad 132\to2,\quad 321\to2$
3. La formule pour n = 3 et k = 1 :
  
  $P(1)=\frac{1}{3}\left(\frac{1}{1}+\frac{1}{2}\right)=\frac{1}{3}\cdot\frac{3}{2}=\frac{1}{2}$
Réponse

3 ordres sur 6, soit une probabilité de 1/2, contre 1/3 si vous retenez le premier candidat.

$P(1)=\frac{3}{6}=\frac{1}{2}>\frac{1}{3}=P(0)$
Quatre candidats, tous les seuils 2 étapes
Avec 4 candidats, calculez la probabilité de choisir le meilleur pour chaque seuil k = 0, 1, 2, 3, puis déterminez le seuil optimal.

Ouvrez ce problème dans l'outil
Afficher la solution
1. Pour k = 0, le premier candidat est retenu ; il est le meilleur avec une probabilité de 1/4. Pour k ≥ 1, utilisez la formule :
  
  $P(1)=\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{3}\right)=\frac{11}{24},\quad P(2)=\frac{2}{4}\left(\frac{1}{2}+\frac{1}{3}\right)=\frac{5}{12},\quad P(3)=\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{4}$
2. Comparez les quatre résultats :
  
  $P(0)=\frac{6}{24},\quad P(1)=\frac{11}{24},\quad P(2)=\frac{10}{24},\quad P(3)=\frac{6}{24}$
Réponse

Écartez le premier candidat, puis retenez le premier qui le surpasse : 11/24 ≈ 45,83 %.

$k^*=1,\qquad P(1)=\frac{11}{24}\approx0.4583$
Les onze de Kepler 3 étapes
En 1611, Johannes Kepler entreprend de choisir une seconde épouse. En près de deux ans, il envisage onze candidates. Avec la règle du seuil et n = 11, quel seuil est optimal, quelle probabilité donne-t-il et quelle est la première candidate que la règle peut retenir ?

Ouvrez ce problème dans l'outil
Afficher la solution
1. Évaluez la formule autour de n/e = 11/e ≈ 4,05 :
  
  $P(4)=\frac{4}{11}\left(\frac{1}{4}+\frac{1}{5}+\dots+\frac{1}{10}\right)=\frac{4}{11}\times1.0956=0.3984$
2. La probabilité est maximale pour k = 4 ; elle est plus faible pour k = 3 comme pour k = 5 :
  
  $P(3)=\frac{3}{11}\left(\frac{1}{3}+\dots+\frac{1}{10}\right)=0.3897,\qquad P(5)=\frac{5}{11}\left(\frac{1}{5}+\dots+\frac{1}{10}\right)=0.3844$
3. Après avoir écarté les 4 premières candidates, la règle peut retenir la cinquième au plus tôt. Kepler a bien épousé la cinquième, mais sans suivre cette règle. D’après le récit que Ferguson tire de sa lettre, après avoir rencontré la cinquième, il se serait laissé convaincre de demander la quatrième en mariage. Celle-ci aurait refusé, et il serait revenu vers la cinquième. La règle interdit tout retour en arrière.
Réponse

Écartez les 4 premières candidates : la probabilité est de 39,84 %. La cinquième est la première que la règle puisse retenir.

$k^*=4,\qquad P(4)\approx0.3984$
Un grand nombre de candidats : d’où vient 1/e 3 étapes
Pour n grand, notez x = k/n la proportion de candidats écartés. Déterminez la valeur optimale de x et la probabilité correspondante. Comparez ensuite au cas n = 100.

Ouvrez ce problème dans l'outil
Afficher la solution
1. La somme est une somme de Riemann pour la fonction 1/t sur [x, 1] :
  
  $\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1}=x\sum_{j=k}^{n-1}\frac{1}{n}\cdot\frac{1}{j/n}\approx x\int_{x}^{1}\frac{dt}{t}=-x\ln x$
2. Cherchez où la dérivée s’annule :
  
  $\frac{d}{dx}\left(-x\ln x\right)=-\ln x-1=0\ \Rightarrow\ x=\frac{1}{e},\qquad -\frac{1}{e}\ln\frac{1}{e}=\frac{1}{e}\approx0.3679$
3. Pour n = 100, on a n/e ≈ 36,79, et le seuil optimal exact est 37 :
  
  $P(36)=0.37101,\qquad P(37)=0.37104,\qquad P(38)=0.37080$
Réponse

Écartez une proportion 1/e ≈ 36,79 % des candidats ; la probabilité tend vers 1/e. Pour n = 100, le seuil optimal est 37 et donne une probabilité de 37,1 %.

$x^*=\frac{1}{e},\qquad P\to\frac{1}{e}\approx0.3679;\qquad n=100:\ k^*=37,\ P(37)\approx0.3710$
Quand il ne reste que le dernier candidat 3 étapes
Sur 100 candidats, vous écartez les 37 premiers. Calculez la probabilité que le meilleur ait été écarté, celle d’atteindre le dernier candidat et celle d’atteindre ce dernier et de trouver en lui le meilleur.

Ouvrez ce problème dans l'outil
Afficher la solution
1. Le meilleur a la même probabilité d’occuper chaque position. La probabilité qu’il soit parmi les 37 premiers vaut donc :
  
  $\frac{k}{n}=\frac{37}{100}=0.37$
2. La recherche atteint le candidat 100 exactement lorsqu’aucun candidat de 38 à 99 n’est retenu, c’est-à-dire lorsque le meilleur des 99 premiers se trouve parmi les 37 premiers :
  
  $\frac{k}{n-1}=\frac{37}{99}\approx0.3737$
3. La différence correspond au cas où la recherche atteint le dernier candidat et où celui-ci est le meilleur :
  
  $\frac{37}{99}-\frac{37}{100}=\frac{37}{9900}\approx0.0037$
Réponse

37 %, 37,37 % et 0,37 % : plus d’une sélection sur trois se termine avec le dernier candidat, mais presque jamais parce qu’il est le meilleur.

$0.37,\qquad 0.3737,\qquad 0.0037$
Minimiser l’espérance du rang avec trois candidats 3 étapes
Avec 3 candidats, l’objectif est désormais de minimiser l’espérance du rang (1 = meilleur), plutôt que de choisir le meilleur. Déterminez la règle optimale par récurrence à rebours et calculez l’espérance du rang qu’elle donne.

Ouvrez ce problème dans l'outil
Afficher la solution
1. Un candidat qui arrive en position i et dont le rang parmi ceux déjà vus est j a pour espérance du rang final j(n + 1)/(i + 1). Le troisième candidat doit être retenu ; son espérance du rang vaut (n + 1)/2 :
  
  $\frac{j(n+1)}{i+1}=\frac{4j}{i+1},\qquad c_2=\frac{3+1}{2}=2$
2. Au deuxième candidat, retenez-le si son espérance du rang est au plus 2 ; sinon, poursuivez :
  
  $i=2:\ \ j=1:\ \tfrac{4}{3}<2,\quad j=2:\ \tfrac{8}{3}>2;\qquad c_1=\frac{1}{2}\left(\frac{4}{3}+2\right)=\frac{5}{3}$
3. Au premier candidat, le retenir donne 2, ce qui dépasse 5/3 : poursuivez donc :
  
  $i=1:\ \ \frac{4}{2}=2>\frac{5}{3}\ \Rightarrow\ c_0=c_1=\frac{5}{3}$
Réponse

Écartez le premier candidat, retenez le deuxième s’il le surpasse, sinon prenez le troisième : l’espérance du rang vaut 5/3 ≈ 1,67. Avec 3 candidats, c’est exactement la règle du seuil pour k = 1.

$c_0=\frac{5}{3}\approx1.6667$
Deux candidats, scores observés 2 étapes
Deux candidats ont des scores tirés indépendamment selon la loi uniforme entre 0 et 1. Vous observez chaque score à l’arrivée. Déterminez la règle qui choisit le plus souvent le score le plus élevé et calculez sa probabilité de réussite. Comparez avec le cas où seuls les rangs sont connus.

Ouvrez ce problème dans l'outil
Afficher la solution
1. Si vous écartez le premier candidat, dont le score est x, vous devez retenir le second. Vous réussissez si son score est supérieur à x, avec une probabilité de 1 − x. Si vous retenez le premier, vous réussissez si le score du second est inférieur à x, avec une probabilité de x.
  
  $S(x)=x,\qquad C(x)=1-x;\qquad S(x)\ge C(x)\iff x\ge\tfrac{1}{2}$
2. Retenez donc le premier lorsque x ≥ 1/2. Calculez la moyenne sur x :
  
  $\int_{0}^{1/2}(1-x)\,dx+\int_{1/2}^{1}x\,dx=\frac{3}{8}+\frac{3}{8}=\frac{3}{4}$
Réponse

Retenez le premier candidat si son score est au moins 1/2 : la probabilité de réussite est de 3/4. Avec les seuls rangs et 2 candidats, elle vaut 1/2 quelle que soit votre règle.

$P=\frac{3}{4}>\frac{1}{2}$

Exercices supplémentaires, réponses seules

Avec 5 candidats, déterminez le seuil optimal et la probabilité correspondante.

Afficher la réponse

Écartez les 2 premiers : 13/30 ≈ 43,33 %.

$k^*=2,\qquad P(2)=\frac{2}{5}\left(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)=\frac{13}{30}\approx0.4333$
Avec 2 candidats et les seuls rangs, montrez que toute règle choisit le meilleur dans la moitié des cas.

Afficher la réponse

Retenir le premier donne une probabilité de réussite de 1/2 ; l’écarter oblige à retenir le second, avec la même probabilité de 1/2.

$P(0)=\frac{1}{2},\qquad P(1)=\frac{1}{2}\cdot\frac{1}{1}=\frac{1}{2}$
Avec 10 candidats et le seuil optimal, calculez la probabilité que le meilleur ait été écarté et celle d’atteindre le dernier candidat.

Afficher la réponse

k = 3 : 30 % et 3/9 ≈ 33,33 %.

$k^*=3:\quad\frac{3}{10}=0.3,\qquad\frac{3}{9}\approx0.3333$
Lorsque n tend vers l’infini, calculez la probabilité de choisir le meilleur si l’on écarte un cinquième des candidats, puis si l’on en écarte trois cinquièmes.

Afficher la réponse

−0,2 ln 0,2 ≈ 32,19 % et −0,6 ln 0,6 ≈ 30,65 %.

$-0.2\ln0.2\approx0.3219,\qquad-0.6\ln0.6\approx0.3065$
Avec 4 candidats, déterminez l’espérance du rang minimale, toutes règles confondues.

Afficher la réponse

15/8 = 1,875.

$c_0=\frac{15}{8}=1.875$

Écarter un quart ou la moitié : une même probabilité

La courbe est presque plate au sommet, ce qui rend la règle facile à appliquer. Cliquez sur Un quart écarté : 35,04 %. Puis sur La moitié écartée : 34,91 %. Pour 100 candidats, le seuil optimal est 37 et donne 37,1 % ; écarter entre un quart et la moitié des candidats vous coûte donc au plus 2,2 points. Quand n augmente, la courbe tend vers −x ln x, où x est la proportion de candidats écartés. Elle prend exactement la même valeur en un quart et en un demi, puisque ¼ ln 4 = ½ ln 2 ≈ 34,66 %. Vous pouvez donc vous contenter d’une estimation de n : même si vous le surestimez ou le sous-estimez d’un tiers, écarter 37 % de votre estimation conserve une probabilité d’au moins 34,5 % pour n grand.

Viser le meilleur conduit au dernier dans plus d’un tiers des cas

La règle mise tout sur le meilleur candidat. S’il fait partie de ceux que vous avez écartés, ce qui arrive dans 37 % des cas avec 100 candidats, personne ne peut ensuite dépasser la référence. La recherche va jusqu’au bout et retient le dernier arrivé. Cliquez sur 100 : 37 écartés : l’espérance du rang du candidat retenu est de 20,01. En 1964, Chow, Moriguti, Robbins et Samuels ont cherché une règle qui minimise plutôt cette espérance. Leur règle peut retenir un candidat qui figure simplement parmi les meilleurs déjà vus, avec une exigence qui s’assouplit à mesure que les candidats restants se font moins nombreux. Pour n = 100, l’espérance du rang est de 3,60. Elle reste inférieure à 4 pour toutes les valeurs de n proposées sur cette page et tend vers 3,8695. Celle de la règle des 37 % continue de croître avec n et atteint 185,54 pour 1 000 candidats.

Avec les scores, la probabilité passe à 58 %

La règle des 37 % utilise uniquement les rangs : elle sait qui surpasse qui. Supposons maintenant que vous observiez le score de chaque candidat et que vous connaissiez la loi de répartition des scores, par exemple la loi uniforme entre 0 et 1. Gilbert et Mosteller ont résolu cette variante en 1966. La phase d’observation sans choix disparaît. Dès le premier candidat, vous retenez celui qui surpasse tous les précédents et dont le score dépasse un seuil. Ce seuil diminue à mesure que la fin approche : 0,5 lorsqu’il reste un candidat à venir, 0,6899 lorsqu’il en reste deux, 0,9240 lorsqu’il en reste dix. La probabilité de choisir le meilleur est de 60,6 % pour 11 candidats et de 58,29 % pour 100. Elle tend vers 58,02 %, contre 36,79 % avec les seuls rangs. Savoir reconnaître un bon score apporte environ 21 points.

Parcours

Choisir d’après ce que vous avez vu

Références (4)

The problem as now studied (n known, random order, relative ranks only, no recall, only the best counts), the cutoff rule and its chance, and the history the page uses: Kepler, after losing his first wife in 1611, spent nearly two years over at least eleven candidates, described in a letter to Baron Strahlendorf of 23 October 1613; friends persuaded him to propose to the fourth after he met the fifth, the fourth turned him down, and he chose the fifth. Ferguson notes that for n = 11 the rule's chance is largest when the fifth is the first candidate it may take, and that Kepler's recall breaks the problem's assumptions: T. S. Ferguson, Who solved the secretary problem? Statistical Science 4(3), 282–289 (1989). doi:10.1214/ss/1177012493
The classical secretary problem solved by backward induction, the limits the page quotes in insight blocks 2 and 3: the least expected rank tends to 3.8695 (Chow, Moriguti, Robbins and Samuels), and with the values revealed and their distribution known the chance of the best tends to 0.58016 (Gilbert and Mosteller), 'to be compared to the limiting value e⁻¹ when the intrinsic values are not revealed': T. S. Ferguson, Optimal Stopping and Applications, Chapter 2, Finite Horizon Problems, §§2.1–2.3. Mathematics Department, UCLA (online text).
The rank-minimising rule of insight block 2 and solved problem 6: accept a candidate whose relative rank is within a threshold that rises as the candidates run out, with expected rank tending to 3.8695: Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels, Optimal selection based on relative rank (the "secretary problem"). Israel Journal of Mathematics 2(2), 81–90 (1964). doi:10.1007/BF02759948
The full-information problem of insight block 3 and solved problem 7: values seen, independent with a known distribution; the optimal rule takes a best-so-far above a threshold that depends on how many remain, and the chance of the best tends to 0.5802: J. P. Gilbert and F. Mosteller, Recognizing the maximum of a sequence. Journal of the American Statistical Association 61(313), 35–73 (1966). doi:10.1080/01621459.1966.10502008

Par l’équipe 7 Raven Room · Vérifié sur des sources publiées. Corrections bienvenues.

La règle des 37 %

D’où vient la formule

Exercices supplémentaires, réponses seules

Écarter un quart ou la moitié : une même probabilité 🖖

Viser le meilleur conduit au dernier dans plus d’un tiers des cas 🖖

Avec les scores, la probabilité passe à 58 % 🖖

Écarter un quart ou la moitié : une même probabilité

Viser le meilleur conduit au dernier dans plus d’un tiers des cas

Avec les scores, la probabilité passe à 58 %