1.5 Problème du collectionneur de coupons
11
Démonstration. On pose G 1 ≡ 1 et pour tout 1 < i r,
G i = min{n 1 : X Gi−1+n ∈ {X 1 , . . . , X Gi−1 }}.
On a card({X 1 , . . . , X Gi }) = i pour tout 1 i n. Les variables aléatoires
G 1 , G 1 + G 2 , . . . , G 1 + · · · + G r sont les temps d’apparition des r premiers
succès dans un jeu de pile ou face spécial dans lequel la probabilité de gagner
change après chaque succès : cette probabilité vaut successivement
π 1 = 1, π 2 =
r − 1
r
, π 3 =
r − 2
r
, . . . , π r =
1
r
.
La décroissance de cette suite traduit le fait qu’il est de plus en plus difficile
d’obtenir un coupon d’un nouveau type au fil de la collection.
Calculons à présent les moments de T . La linéarité de l’espérance donne
E(T ) =
r
i=1
E(G i ) =
r
i=1
1
π i
=
r
i=1
r
r − i + 1
= r
r
i=1
1
i
= r(log(r) + γ + o(1)).
D’autre part, l’indépendance des v.a. G 1 , . . . , G r (exercice !) donne
Var(T ) =
r
i=1
Var(G i ) =
r
i=1
1 − π i
π 2
i
= r
r−1
i=1
r − i
i 2 =
π
2
6
r
2
− r(log(r) + γ) + o(r
2 ).
Théorème 1.13 (Queue de distribution). Pour tout n 1,
P(T > n) =
r
k=1
(−1)
k−1
r
k
1 −
k
r
n
.
Démonstration. On a
{T > n} = E n,1 ∪ · · · ∪ E n,r où E n,i := {X 1 = i, . . . , X n = i}.
Si i 1 , . . . , i k ∈ {1, . . . , r} sont deux à deux distincts, alors, en notant
R = {1, . . . , r} \ {i 1 , . . . , i k },
on a
P(E n,i1 ∩ · · · ∩ E n,i k ) = P(X 1 ∈ R) · · · P(X n ∈ R)