1.5 Problème du collectionneur de coupons
9
P(S n = k) − e
−np (np)
k
k!
=
n
n(1 − p)
· · ·
n − k + 1
n(1 − p)
(1 − p)
n
− e
−np
(np)
k
k!
.
Ceci montre que si p dépend de n avec lim n→∞ np = λ alors la loi de S n
tend vers Poi(λ). La distance en variation totale permet de quantifier cette
convergence en loi : l’inégalité de Le Cam du théorème 1.10 ci-dessous donne
∞
k=0
P(S n = k) − e
−np (np)
k
k!
2np
2 ,
utile si np
2 est petit. Si par exemple p = λ/n alors np = λ et np
2 = λ
2 /n.
Théorème 1.10 (Inégalité de Le Cam). Soient X 1 , . . . , X n des variables
aléatoires indépendantes de lois de Bernoulli Ber(p 1 ), . . . , Ber(p n ). Soit μ n la
loi de S n = X 1 + · · · + X n et soit ν n = Poi(p 1 + · · · + p n ) la loi de Poisson de
même moyenne que S n . Alors on a
d VT (μ n , ν n ) p
2
1 + · · · + p
2
n .
Démonstration. On établit par récurrence sur n que si α 1 , . . . , α n et β 1 , . . . , β n
sont des lois de probabilité sur N alors on a l’inégalité sous-additive
d VT (α 1 ∗ · · · ∗ α n , β 1 ∗ · · · ∗ β n ) d VT (α 1 , β 1 ) + · · · + d VT (α n , β n ).
On établit ensuite que d VT (Ber(p), Poi(p)) p
2 , et on exploite le semi-groupe
de convolution des lois de Poisson : Poi(a) ∗ Poi(b) = Poi(a + b).
L’inégalité
2
−
1
−
∞ suivante
p
2
1 + · · · + p
2
n (p 1 + · · · + p n ) max
1kn
p k
permet de retrouver la loi des petits nombres : si (X n,k ) 1kn est un tableau
triangulaire de variables aléatoires indépendantes de lois de Bernoulli avec
X n,k ∼ Ber(p n,k ) pour tous n k 1, et si
lim
n→∞
p n,1 + · · · + p n,n = λ et
lim
n→∞
max
1kn
p n,k = 0,
alors X n,1 + · · · + X n,n converge en loi vers Poi(λ) quand n → ∞.
1.5 Problème du collectionneur de coupons
Le problème du collectionneur de coupons est dans la même boîte à outils
que le jeu de pile ou face ou le jeu de dé, auquel il est intimement relié. Un
grand nombre de situations concrètes cachent un collectionneur de coupons
ou une de ses variantes. Nous nous limitons ici à sa version la plus simple.
9
P(S n = k) − e
−np (np)
k
k!
=
n
n(1 − p)
· · ·
n − k + 1
n(1 − p)
(1 − p)
n
− e
−np
(np)
k
k!
.
Ceci montre que si p dépend de n avec lim n→∞ np = λ alors la loi de S n
tend vers Poi(λ). La distance en variation totale permet de quantifier cette
convergence en loi : l’inégalité de Le Cam du théorème 1.10 ci-dessous donne
∞
k=0
P(S n = k) − e
−np (np)
k
k!
2np
2 ,
utile si np
2 est petit. Si par exemple p = λ/n alors np = λ et np
2 = λ
2 /n.
Théorème 1.10 (Inégalité de Le Cam). Soient X 1 , . . . , X n des variables
aléatoires indépendantes de lois de Bernoulli Ber(p 1 ), . . . , Ber(p n ). Soit μ n la
loi de S n = X 1 + · · · + X n et soit ν n = Poi(p 1 + · · · + p n ) la loi de Poisson de
même moyenne que S n . Alors on a
d VT (μ n , ν n ) p
2
1 + · · · + p
2
n .
Démonstration. On établit par récurrence sur n que si α 1 , . . . , α n et β 1 , . . . , β n
sont des lois de probabilité sur N alors on a l’inégalité sous-additive
d VT (α 1 ∗ · · · ∗ α n , β 1 ∗ · · · ∗ β n ) d VT (α 1 , β 1 ) + · · · + d VT (α n , β n ).
On établit ensuite que d VT (Ber(p), Poi(p)) p
2 , et on exploite le semi-groupe
de convolution des lois de Poisson : Poi(a) ∗ Poi(b) = Poi(a + b).
L’inégalité
2
−
1
−
∞ suivante
p
2
1 + · · · + p
2
n (p 1 + · · · + p n ) max
1kn
p k
permet de retrouver la loi des petits nombres : si (X n,k ) 1kn est un tableau
triangulaire de variables aléatoires indépendantes de lois de Bernoulli avec
X n,k ∼ Ber(p n,k ) pour tous n k 1, et si
lim
n→∞
p n,1 + · · · + p n,n = λ et
lim
n→∞
max
1kn
p n,k = 0,
alors X n,1 + · · · + X n,n converge en loi vers Poi(λ) quand n → ∞.
1.5 Problème du collectionneur de coupons
Le problème du collectionneur de coupons est dans la même boîte à outils
que le jeu de pile ou face ou le jeu de dé, auquel il est intimement relié. Un
grand nombre de situations concrètes cachent un collectionneur de coupons
ou une de ses variantes. Nous nous limitons ici à sa version la plus simple.