10.5 Pour aller plus loin
137
Démonstration. Pour tout n 1, on a P n = (Y n−1 )
−β . Le résultat précédent
assure que n
β/(β−1) P n converge presque sûrement vers une variable aléatoire
W vérifiant P(0 < W < ∞) = 1. On conclut alors avec le théorème 10.7.
10.5 Pour aller plus loin
On peut aussi étudier le nombre M n de candidats retenus après n auditions
et la moyenne A n des performances des candidats retenus après n auditions.
Ce chapitre est essentiellement basé sur un article de John Preater [Pre00]
pour le cas de la loi exponentielle, et sur un article de Abba Krieger, Moshe
Pollak, et Ester Samuel-Cahn [KPSC08] pour le cas général. Les preuves du
théorème des séries centrées (théorème 10.3) et du théorème de LindebergLévy (théorème 10.4) se trouvent par exemple dans l’incontournable livre de
William Feller [Fel68].
On peut compléter le théorème 10.2 avec des inégalités de déviation non
asymptotiques, à la différence du théorème de convergence en loi. Comme les
variables aléatoires (R n ) n1 sont à valeurs dans [0, 1], l’inégalité de (Wassily)
Hoeffding assure que, pour tout r > 0,
P
Z n −
n
k=1
1
k
r
exp
−
2r
2
n
.
Cette inégalité n’est en l’occurrence pas très précise car elle ne prend pas
bien en compte le fait que les variances des incréments de (Z n ) n1 tendent
vers 0. On peut obtenir un résultat plus fin pour la déviation inférieure grâce
à l’inégalité de (Andreas) Maurer pour les sommes de variables aléatoires
positives [Mau03], qui donne, pour tout r > 0,
P
Z n −
n
k=1
1
k
−r
exp
−
r
2
2 log(n)
.
Citons enfin le célèbre problème des secrétaires
1 dont on trouve une description savoureuse dans un article de Thomas Ferguson [Fer89]. Le contexte
est le même que dans notre chapitre mais on ne recrute qu’une personne parmi
n candidats. La question est de déterminer la stratégie fournissant avec la probabilité maximale le meilleur candidat. La première étape est de montrer que
la stratégie optimale est nécessairement de la forme suivante : on fixe r entre
1 et n, on recale les r − 1 premiers candidats puis on sélectionne le premier
candidat qui obtient une meilleure note que ses prédécesseurs. Avec une telle
1. Ce problème d’arrêt optimal est un grand classique de la théorie du contrôle
stochastique et de la théorie de la décision. Il est également connu sous le nom du
problème du mariage (entre autres).
137
Démonstration. Pour tout n 1, on a P n = (Y n−1 )
−β . Le résultat précédent
assure que n
β/(β−1) P n converge presque sûrement vers une variable aléatoire
W vérifiant P(0 < W < ∞) = 1. On conclut alors avec le théorème 10.7.
10.5 Pour aller plus loin
On peut aussi étudier le nombre M n de candidats retenus après n auditions
et la moyenne A n des performances des candidats retenus après n auditions.
Ce chapitre est essentiellement basé sur un article de John Preater [Pre00]
pour le cas de la loi exponentielle, et sur un article de Abba Krieger, Moshe
Pollak, et Ester Samuel-Cahn [KPSC08] pour le cas général. Les preuves du
théorème des séries centrées (théorème 10.3) et du théorème de LindebergLévy (théorème 10.4) se trouvent par exemple dans l’incontournable livre de
William Feller [Fel68].
On peut compléter le théorème 10.2 avec des inégalités de déviation non
asymptotiques, à la différence du théorème de convergence en loi. Comme les
variables aléatoires (R n ) n1 sont à valeurs dans [0, 1], l’inégalité de (Wassily)
Hoeffding assure que, pour tout r > 0,
P
Z n −
n
k=1
1
k
r
exp
−
2r
2
n
.
Cette inégalité n’est en l’occurrence pas très précise car elle ne prend pas
bien en compte le fait que les variances des incréments de (Z n ) n1 tendent
vers 0. On peut obtenir un résultat plus fin pour la déviation inférieure grâce
à l’inégalité de (Andreas) Maurer pour les sommes de variables aléatoires
positives [Mau03], qui donne, pour tout r > 0,
P
Z n −
n
k=1
1
k
−r
exp
−
r
2
2 log(n)
.
Citons enfin le célèbre problème des secrétaires
1 dont on trouve une description savoureuse dans un article de Thomas Ferguson [Fer89]. Le contexte
est le même que dans notre chapitre mais on ne recrute qu’une personne parmi
n candidats. La question est de déterminer la stratégie fournissant avec la probabilité maximale le meilleur candidat. La première étape est de montrer que
la stratégie optimale est nécessairement de la forme suivante : on fixe r entre
1 et n, on recale les r − 1 premiers candidats puis on sélectionne le premier
candidat qui obtient une meilleure note que ses prédécesseurs. Avec une telle
1. Ce problème d’arrêt optimal est un grand classique de la théorie du contrôle
stochastique et de la théorie de la décision. Il est également connu sous le nom du
problème du mariage (entre autres).