16
1 Pile, face, coupons
sup
x∈R
P
S n − E(S n )
Var(S n )
x
−
1
√
2π
x
−∞
e
−
t 2
2 dt
2
(τ
3
1 + · · · + τ
3
n )
2
(σ 2
1 + · · · + σ 2
n )
3 .
D’autre part, on peut voir la distance en variation totale d VT (·, ·) comme
une distance de Wasserstein (couplage). Pour le voir, on observe tout d’abord
que P(X = Y ) = E(d(X, Y )) pour la distance atomique d(x, y) = δ x =y , d’où,
en notant Π(μ, ν) l’ensemble des lois sur E × E de lois marginales μ et ν,
d VT (μ, ν) = min
π∈Π(μ,ν)
E×E
d(x, y) dπ(x, y).
Le problème du collectionneur de coupons est notamment abordé dans le
livre de William Feller [Fel68, Fel71], le livre de Rejeev Motwani et Prabhakar
Raghavan [MR95], et dans les articles de Lars Holst[Hol01] et de Aristides
Doumas et Vassilis Papanicolaou [DP13]. Donald Newman et Lawrence Shepp
on montré dans [NS60] que si on impose que chaque type soit observé m fois,
alors le temps de complétion de la collection vaut en moyenne
r log(r) + (m − 1)r log(log(r)) + O(r).
D’autres variantes se trouvent dans le livre de Claude Bouzitat, Gilles Pagès,
Frédérique Petit, et Fabrice Carrance [BPPC99]. Le théorème 1.16 révélant
une fluctuation asymptotique de loi de Gumbel a été obtenu par Paul Erdős
et Alfréd Rényi [ER61a]. Une analyse du cas non uniforme associé à une probabilité discrète (p 1 , . . . , p r ) est menée dans un article de Lars Holst [Hol01].
Lorsque r n’est pas connu, on dispose de l’estimateur
r n := card{X 1 , . . . , X n }.
Si e 1 , . . . , e r est la base canonique de R
r alors le vecteur aléatoire
C n := (C n,1 , . . . , C n,r ) := e X1 + · · · + e Xn
de N
r suit la loi multinomiale de taille n et de paramètre (p 1 , . . . , p r ), et on a
r n =
r
i=1
1 {Cn,i>0} = r −
r
i=1
1 {Cn,i=0} .
En particulier,
E( r n ) = r −
r
i=1
P(C n,i = 0) = r −
r
i=1
(1 − p i )
n .
Notons enfin que comme les r types sont ordonnés, la variable aléatoire
max(X 1 , . . . , X n ) est un estimateur du bord droit r du support {1, . . . , r}.
Le collectionneur de coupons est un cas particulier du problème du recouvrement abordé dans l’article [Ald91] de David Aldous, dans le livre de David
1 Pile, face, coupons
sup
x∈R
P
S n − E(S n )
Var(S n )
x
−
1
√
2π
x
−∞
e
−
t 2
2 dt
2
(τ
3
1 + · · · + τ
3
n )
2
(σ 2
1 + · · · + σ 2
n )
3 .
D’autre part, on peut voir la distance en variation totale d VT (·, ·) comme
une distance de Wasserstein (couplage). Pour le voir, on observe tout d’abord
que P(X = Y ) = E(d(X, Y )) pour la distance atomique d(x, y) = δ x =y , d’où,
en notant Π(μ, ν) l’ensemble des lois sur E × E de lois marginales μ et ν,
d VT (μ, ν) = min
π∈Π(μ,ν)
E×E
d(x, y) dπ(x, y).
Le problème du collectionneur de coupons est notamment abordé dans le
livre de William Feller [Fel68, Fel71], le livre de Rejeev Motwani et Prabhakar
Raghavan [MR95], et dans les articles de Lars Holst[Hol01] et de Aristides
Doumas et Vassilis Papanicolaou [DP13]. Donald Newman et Lawrence Shepp
on montré dans [NS60] que si on impose que chaque type soit observé m fois,
alors le temps de complétion de la collection vaut en moyenne
r log(r) + (m − 1)r log(log(r)) + O(r).
D’autres variantes se trouvent dans le livre de Claude Bouzitat, Gilles Pagès,
Frédérique Petit, et Fabrice Carrance [BPPC99]. Le théorème 1.16 révélant
une fluctuation asymptotique de loi de Gumbel a été obtenu par Paul Erdős
et Alfréd Rényi [ER61a]. Une analyse du cas non uniforme associé à une probabilité discrète (p 1 , . . . , p r ) est menée dans un article de Lars Holst [Hol01].
Lorsque r n’est pas connu, on dispose de l’estimateur
r n := card{X 1 , . . . , X n }.
Si e 1 , . . . , e r est la base canonique de R
r alors le vecteur aléatoire
C n := (C n,1 , . . . , C n,r ) := e X1 + · · · + e Xn
de N
r suit la loi multinomiale de taille n et de paramètre (p 1 , . . . , p r ), et on a
r n =
r
i=1
1 {Cn,i>0} = r −
r
i=1
1 {Cn,i=0} .
En particulier,
E( r n ) = r −
r
i=1
P(C n,i = 0) = r −
r
i=1
(1 − p i )
n .
Notons enfin que comme les r types sont ordonnés, la variable aléatoire
max(X 1 , . . . , X n ) est un estimateur du bord droit r du support {1, . . . , r}.
Le collectionneur de coupons est un cas particulier du problème du recouvrement abordé dans l’article [Ald91] de David Aldous, dans le livre de David