Choisissons un entier r. On rejette systématiquement les r premiers candidats, puis on recrute le premier candidat suivant qui est meilleur que tous les candidats observés jusque-là.
Pour que cette stratégie choisisse le meilleur candidat, celui-ci doit apparaître après la position r et le meilleur candidat parmi ceux qui le précèdent doit être situé dans les r premières positions.
Pour N grand, si x=r/N, la probabilité de succès est approximativement
P(x) ≈ x ln(1/x)
On maximise cette fonction :
P'(x) = ln(1/x) − 1 = 0 ⇒ x = 1/e ≈ 0,368
La stratégie optimale consiste donc à observer environ les
37 % premiers candidats, puis à choisir le premier qui bat tous ceux déjà vus.
La probabilité maximale de sélectionner le meilleur tend elle aussi vers
1/e ≈ 36,8 %
💡 Idée à retenir : il faut équilibrer deux risques opposés — décider trop tôt sans information, ou attendre tellement longtemps que le meilleur candidat soit déjà passé.