15.4 Théorème de Rubin
211
telles que S α (0) > 0 et S β (0) > 0. On construit une suite récurrente aléatoire
(X n ) n1 à valeurs dans {α, β} comme suit : pour tout n ∈ N, conditionnellement à X 1 , . . . , X n , en notant Y n =
n
k=1 1 {X k =α} le nombre de α et
Z n = n − Y n le nombre de β,
(X n+1 , Y n+1 , Z n+1 ) =
(α, Y n + 1, Z n ) si U n+1
Sα(Yn)
Sα(Yn)+S β (Zn) ,
(β, Y n , Z n + 1) si U n+1 >
Sα(Yn)
Sα(Yn)+S β (Zn) ,
où (U n ) n1 est une suite de variables aléatoires i.i.d. de loi uniforme sur [0, 1].
La suite (X n ) n1 ainsi construite code les tirages successifs d’une urne de
Pólya généralisée. Le modèle du théorème 15.8 dans le cas où (A 0 , B 0 ) est déterministe s’obtient avec (S α (0), S β (0)) = (A 0 , B 0 ), et S α (n) = S β (n) = r(n)
pour tout n > 0. Si r est linéaire alors on retrouve l’absence de renforcement (tirages avec remise). Si r est affine alors on retrouve le renforcement
linéaire (urne de Pólya standard). Enfin, si r est une fonction puissance, alors
on retrouve le renforcement géométrique.
Pour étudier le cas général, on introduit la probabilité p α (respectivement
p β ) que la suite (X n ) n1 ne comporte qu’un nombre fini de β (respectivement
de α) c’est-à-dire que des α (respectivement que des β) à partir d’un certain
rang sur n. Ces probabilités sont données par les formules suivantes :
p α = P(∪ n ∩ kn {X k = α}) et p β = P(∪ n ∩ kn {X k = β}).
On a p α +p β 1. Les nombres suivants dans [0, ∞] vont jouer un rôle crucial :
ϕ α =
∞
n=0
1
S α (n)
et ϕ β =
∞
n=0
1
S β (n)
.
Théorème 15.9 (de Rubin). Les valeurs de p α , p β sont liées à ϕ α , ϕ β :
ϕ β < ∞
ϕ β = ∞
ϕ α < ∞ p α > 0, p β > 0, p α + p β = 1 p α = 1 (donc p β = 0)
ϕ α = ∞
p β = 1 (donc p α = 0)
p α = 0, p β = 0
Ainsi, la trivialité des probabilités p α et p β ne dépend que du comportement asymptotique des fonctions de renforcement S α et S β , et les cas critiques
sont liés à la condition de Riemann. En absence de renforcement (S α et S β
sont linéaires) ainsi que dans le cas d’un renforcement linéaire (S α et S β sont
affines) on a ϕ α = ϕ β = ∞ car la série harmonique diverge. Dès que le renforcement est sur-linéaire, alors ϕ α < ∞ et ϕ β < ∞, en particulier pour le cas
du renforcement quadratique, et bien sûr le cas du renforcement géométrique.
Démonstration. Soient (E
α
n ) n0 et (E
β
n ) n0 deux suites indépendantes de variables aléatoires indépendantes de loi exponentielle avec, pour tout n 0,
E(E
α
n ) =
1
S α (n)
et E(E
β
n ) =
1
S β (n)
211
telles que S α (0) > 0 et S β (0) > 0. On construit une suite récurrente aléatoire
(X n ) n1 à valeurs dans {α, β} comme suit : pour tout n ∈ N, conditionnellement à X 1 , . . . , X n , en notant Y n =
n
k=1 1 {X k =α} le nombre de α et
Z n = n − Y n le nombre de β,
(X n+1 , Y n+1 , Z n+1 ) =
(α, Y n + 1, Z n ) si U n+1
Sα(Yn)
Sα(Yn)+S β (Zn) ,
(β, Y n , Z n + 1) si U n+1 >
Sα(Yn)
Sα(Yn)+S β (Zn) ,
où (U n ) n1 est une suite de variables aléatoires i.i.d. de loi uniforme sur [0, 1].
La suite (X n ) n1 ainsi construite code les tirages successifs d’une urne de
Pólya généralisée. Le modèle du théorème 15.8 dans le cas où (A 0 , B 0 ) est déterministe s’obtient avec (S α (0), S β (0)) = (A 0 , B 0 ), et S α (n) = S β (n) = r(n)
pour tout n > 0. Si r est linéaire alors on retrouve l’absence de renforcement (tirages avec remise). Si r est affine alors on retrouve le renforcement
linéaire (urne de Pólya standard). Enfin, si r est une fonction puissance, alors
on retrouve le renforcement géométrique.
Pour étudier le cas général, on introduit la probabilité p α (respectivement
p β ) que la suite (X n ) n1 ne comporte qu’un nombre fini de β (respectivement
de α) c’est-à-dire que des α (respectivement que des β) à partir d’un certain
rang sur n. Ces probabilités sont données par les formules suivantes :
p α = P(∪ n ∩ kn {X k = α}) et p β = P(∪ n ∩ kn {X k = β}).
On a p α +p β 1. Les nombres suivants dans [0, ∞] vont jouer un rôle crucial :
ϕ α =
∞
n=0
1
S α (n)
et ϕ β =
∞
n=0
1
S β (n)
.
Théorème 15.9 (de Rubin). Les valeurs de p α , p β sont liées à ϕ α , ϕ β :
ϕ β < ∞
ϕ β = ∞
ϕ α < ∞ p α > 0, p β > 0, p α + p β = 1 p α = 1 (donc p β = 0)
ϕ α = ∞
p β = 1 (donc p α = 0)
p α = 0, p β = 0
Ainsi, la trivialité des probabilités p α et p β ne dépend que du comportement asymptotique des fonctions de renforcement S α et S β , et les cas critiques
sont liés à la condition de Riemann. En absence de renforcement (S α et S β
sont linéaires) ainsi que dans le cas d’un renforcement linéaire (S α et S β sont
affines) on a ϕ α = ϕ β = ∞ car la série harmonique diverge. Dès que le renforcement est sur-linéaire, alors ϕ α < ∞ et ϕ β < ∞, en particulier pour le cas
du renforcement quadratique, et bien sûr le cas du renforcement géométrique.
Démonstration. Soient (E
α
n ) n0 et (E
β
n ) n0 deux suites indépendantes de variables aléatoires indépendantes de loi exponentielle avec, pour tout n 0,
E(E
α
n ) =
1
S α (n)
et E(E
β
n ) =
1
S β (n)