1.5 Problème du collectionneur de coupons
13
probabilité unique valable pour tout r. D’autre part, la borne établie permet
d’obtenir un intervalle de prédiction non asymptotique : pour α = 0.05, r fixé,
et t bien choisi, on a P(|T − r log(r)|/r > t) = O(1/t
2 ) = α. L’intervalle de
prédiction est de largeur 2rt, et se dégrade quand t croît (α diminue).
Le théorème suivant affirme que les fluctuations asymptotiques dans la
convergence précédente suivent une loi de Gumbel.
Théorème 1.16 (Fluctuations asymptotiques). On a
T − r log(r)
r
= log(r)
T
r log(r)
− 1
loi
−→
r→∞
Gumbel
où la loi de Gumbel a pour fonction de répartition t ∈ R → e
−e
−t .
La figure 1.2 illustre ce résultat.
Queue du collectionneur de coupons r=20
MonteCarlo N=2000
Gumbel
0
0.2
0.4
0.6
0.8
1
P(T>n)
50
100
150
200
n
Fig. 1.2. Approximations de la queue de distribution de la variable aléatoire T par
celle de r log(r) + rG où G suit la loi de Gumbel en vertu du théorème 1.16, ainsi
que par une méthode de Monte-Carlo avec N tirages en utilisant la représentation
de T en somme de variables aléatoires géométriques indépendantes.
Démonstration. Il suffit d’établir que pour tout t ∈ R on a