10
1 Pile, face, coupons
Il faut jouer un nombre de fois (aléatoire) géométrique à pile ou face pour
voir apparaître les deux côtés de la pièce. Si on remplace la pièce de monnaie
par un dé à r 2 faces, combien de fois faut-il lancer le dé pour voir apparaître les r faces différentes ? On modélise cela, pour un entier fixé r 2, en
considérant la variable aléatoire
T := min{n 1 : {X 1 , . . . , X n } = {1, . . . , r}}
= min{n 1 : card{X 1 , . . . , X n } = r}
où (X n ) n1 est une suite de variables aléatoires i.i.d. de loi uniforme sur
{1, . . . , r}. La variable aléatoire T est le premier instant où les r faces du
dé sont apparues. Ce temps dépend bien entendu de r mais, par souci de
simplicité, nous omettrons cette dépendance dans la notation. Le nom collectionneur de coupons provient des coupons à collectionner présents dans
certains paquets de céréales.
Théorème 1.11 (Combinatoire). On a T r, et pour tout n r,
P(T = n) =
r!
r n
n − 1
r − 1
où la notation en accolades désigne le nombre de Stirling de seconde espèce,
qui est le nom donné en combinatoire au nombre de manières de partitionner
un ensemble à n − 1 éléments en r − 1 sous-ensembles non vides.
Démonstration. On a X T ∈ {X 1 , . . . , X T −1 } car le coupon qui termine la collection n’a forcément jamais été vu auparavant. Si on fixe n r, l’événement
{T = n} correspond à choisir le type du dernier coupon puis à répartir les
n−1 coupons restants sur les r−1 types restants. Le résultat désiré en découle
car la loi des types est uniforme.
Bien qu’explicite, le théorème 1.11 n’est malgré tout pas très parlant. Le
résultat intuitif suivant va beaucoup nous aider à étudier la variable T .
Lemme 1.12 (Décomposition). On a T = G 1 + · · · + G r où G 1 , . . . , G r sont
des variables aléatoires indépendantes avec
G i ∼ Geo(π i ), π i :=
r − i + 1
r
, 1 i r.
En particulier, on a P(T < ∞) = 1, et de plus
E(T ) = r(log(r) + γ) + o r→∞ (r) et Var(T ) =
π
2
6
r
2 + o r→∞ (r
2 ),
où γ = lim n→∞ (
n
i=1 1/i − log(n)) ≈ 0.577 est la constante d’Euler.