4.5 Une loi des grands nombres ralentie
77
log α(n) ≥ −δ
n
k=1
1
k
= −δ
1 +
n
k=2
1
k
Comme pr´ ec´ edemment, on remplace ces sommes par des int´ egrales en utilisant
les majorations ´ el´ ementaires
1
k
≤
k
k−1
dt
t
=⇒
n
k=2
1
k
≤
n
k=2
k
k−1
dt
t
=
n
1
dt
t
= log n
On arrive enfin `
a la borne inf´ erieure recherch´ ee
α(n) ≥ e
−δ log (e n)) =
1
(e n) δ
4.5 Une loi des grands nombres ralentie
Les propri´ et´ es de convergence d´ ecrites dans la section pr´ ec´ edente peuvent
ˆ etre interpr´ et´ ees comme une loi des grands nombres ralentie par un processus
de renforcement. Rappelons que dans le cas classique, les variables al´ eatoires
sont g´ en´ eralement ind´ ependantes, et identiquement distribu´ ees selon la loi μ.
Cette situation correspond ` a une absence totale de renforcement = 0.
Lorsque le degr´ e de renforcement est strictement positif, le processus
peut aussi s’interpr´ eter comme un g´ en´ erateur de variables de mˆ eme loi μ.
N´ eanmoins, au cours du renforcement, de nombreuses variables sont souvent
r´ ep´ et´ ees. Pour mieux comprendre ces remarques, examinons de plus pr` es les
lois conditionnelles des ´ etats du processus connaissant ses valeurs pass´ ees
Loi(X n | X 0 , . . . , X n−1 ) =
1
n
n−1
k=0
1 X k + (1 − ) μ
`
A chaque ´ etape, et avec une probabilit´ e (1−), chaque ´ etat al´ eatoire X n est une
variable de loi μ, ind´ ependante des pr´ ec´ edentes. Dans le cas contraire, X n est
une simple copie conforme de l’une des variables pr´ ec´ edemment construites !
La loi des grands nombres usuelle nous informe que la mesure empirique d’une
suite de variables ind´ ependantes, et identiquement distribu´ ees selon une loi μ
est approximativement ´ egale `
a la distribution μ. Dans le cas d’explorations
renforc´ ees, les variables ne sont plus ind´ ependantes, et d’apr` es la discussion
pr´ ec´ edente de nombreuses variables al´ eatoires sont r´ ep´ et´ ees. N´ eanmoins on
peut s’attendre `
a avoir suffisamment de variables ind´ ependantes pour voir
s’exprimer une loi des grands nombres renforc´ es.
Une version faible de la loi des grands nombres correspond `
a la convergence
en probabilit´ e des mesures d’occupations S n (f ), ´ evalu´ ees sur des fonctions
tests born´ ees f , vers les quantit´ es moyennes μ(f ) :
77
log α(n) ≥ −δ
n
k=1
1
k
= −δ
1 +
n
k=2
1
k
Comme pr´ ec´ edemment, on remplace ces sommes par des int´ egrales en utilisant
les majorations ´ el´ ementaires
1
k
≤
k
k−1
dt
t
=⇒
n
k=2
1
k
≤
n
k=2
k
k−1
dt
t
=
n
1
dt
t
= log n
On arrive enfin `
a la borne inf´ erieure recherch´ ee
α(n) ≥ e
−δ log (e n)) =
1
(e n) δ
4.5 Une loi des grands nombres ralentie
Les propri´ et´ es de convergence d´ ecrites dans la section pr´ ec´ edente peuvent
ˆ etre interpr´ et´ ees comme une loi des grands nombres ralentie par un processus
de renforcement. Rappelons que dans le cas classique, les variables al´ eatoires
sont g´ en´ eralement ind´ ependantes, et identiquement distribu´ ees selon la loi μ.
Cette situation correspond ` a une absence totale de renforcement = 0.
Lorsque le degr´ e de renforcement est strictement positif, le processus
peut aussi s’interpr´ eter comme un g´ en´ erateur de variables de mˆ eme loi μ.
N´ eanmoins, au cours du renforcement, de nombreuses variables sont souvent
r´ ep´ et´ ees. Pour mieux comprendre ces remarques, examinons de plus pr` es les
lois conditionnelles des ´ etats du processus connaissant ses valeurs pass´ ees
Loi(X n | X 0 , . . . , X n−1 ) =
1
n
n−1
k=0
1 X k + (1 − ) μ
`
A chaque ´ etape, et avec une probabilit´ e (1−), chaque ´ etat al´ eatoire X n est une
variable de loi μ, ind´ ependante des pr´ ec´ edentes. Dans le cas contraire, X n est
une simple copie conforme de l’une des variables pr´ ec´ edemment construites !
La loi des grands nombres usuelle nous informe que la mesure empirique d’une
suite de variables ind´ ependantes, et identiquement distribu´ ees selon une loi μ
est approximativement ´ egale `
a la distribution μ. Dans le cas d’explorations
renforc´ ees, les variables ne sont plus ind´ ependantes, et d’apr` es la discussion
pr´ ec´ edente de nombreuses variables al´ eatoires sont r´ ep´ et´ ees. N´ eanmoins on
peut s’attendre `
a avoir suffisamment de variables ind´ ependantes pour voir
s’exprimer une loi des grands nombres renforc´ es.
Une version faible de la loi des grands nombres correspond `
a la convergence
en probabilit´ e des mesures d’occupations S n (f ), ´ evalu´ ees sur des fonctions
tests born´ ees f , vers les quantit´ es moyennes μ(f ) :