130
10 Records, extrêmes, et recrutements
Le candidat n est recruté si son rang vaut n, c’est-à-dire si sa note bat le
précédent record. Le nombre de records, ou de personnes recrutées, jusqu’au
temps n est donné par
Z n =
n
i=1
1 {Ri=i} .
On définit également les instants de record par récurrence :
T 1 = 1 et, pour j 1, T j+1 = inf {n > T j : X n > X i pour i < n}.
Lemme 10.1 (Lois des rangs). Les variables aléatoires (R n ) n1 sont indépendantes et, pour tout n ∈ N
∗ , R n suit la loi uniforme sur {1, . . . , n},
E(Z n ) =
n
k=1
1
k
= log(n) + γ + O(1/n),
et
Var(Z n ) =
n
k=1
k − 1
k 2 = log(n) + γ −
π
2
6
+ O(1/n),
où γ désigne la constante d’Euler.
Démonstration. La fonction de répartition F de μ est continue donc pour tous
entiers i et j distincts, P(X i = X j ) = 1. En particulier, pour n 1, presque
sûrement, il existe une unique permutation (aléatoire) σ de {1, . . . , n} telle
que
X σ(1) < · · · < X σ(n) .
De plus la loi de cette permutation est la loi uniforme sur S n . Enfin, à un
vecteur (R 1 , . . . , R n ) on associe la permutation σ de manière bijective, d’où
P(R 1 = r 1 , . . . , R n = r n ) =
1
n!
pour tout (r 1 , . . . , r n ) vérifiant 1 r i i pour 1 i n. La v.a. Z n est donc
la somme de n v.a. de loi de Bernoulli indépendantes de paramètres 1, 1/2,. . . ,
1/n. Les expressions de son espérance et de sa variance s’en déduisent.
Notons que la suite (Z n ) n1 a la même loi que la suite (|B n |) n1 du
processus des restaurants chinois du chapitre 14, voir également le théorème
13.5 sur la suite (K n ) n1 du nombre d’allèles dans un échantillon obtenue lors
de l’étude de la généalogie du modèle de Wright-Fisher.
Théorème 10.2 (Comportement asymptotique du nombre de records).
Z n
log(n)
p.s.
−→
n→∞
1 et
Z n − log(n)
log(n)
loi
−→
n→∞
N (0, 1).