6.4 Formes d’arbres binaires de recherche biaisées
259
Alors
(i) La suite de variables aléatoires (E n (z)) n≥0 définies par
E n (z) :=
(2z) s n
γ n (2z − 1)
est une F n -martingale d’espérance 1, pour la probabilité P 1
2
, qui est la loi P de
l’arbre bourgeonnant ordinaire. Autrement dit
E 1
2
(2z) s n+1
γ n+1 (2z − 1)
τ n
=
(2z) s n
γ n (2z − 1)
.
(ii) La loi P z de l’arbre biaisé de paramètre z s’écrit pour tout n ∈ N
P z = E n (z) P 1
2
= E n (z) P
sur F n .
Preuve
(i) En explicitant la loi de s n sous P 1
2
: s n+1 − s n vaut 1 avec probabilité
1
n+1 et 0
sinon.
(ii) Pour tout z > 0, pour tout n ∈ N, définissons
Q z := E n (z) P 1
2
sur F n ,
autrement dit
∀n ∈ N, ∀A ∈ F n ,
Q z (A) :=
A
E n (z) d P 1
2
,
(6.22)
et montrons que Q z = P z . Comme s n+1 −s n est F n+1 -mesurable, par définition
de Q z donnée dans (6.22),
Q z (s n+1 − s n = 0) = E 1
2
E n+1 (z)1 {s n+1 −s n =0}
= E 1
2
(2z) s n+1
γ n+1 (2z − 1)
1 {s n+1 −s n =0}
=
1
γ n+1 (2z − 1)
E 1
2
(2z)
s n 1 {s n+1 −s n =0}
=
1
γ n+1 (2z − 1)
E 1
2
E 1
2
(2z)
s n 1 {s n+1 −s n =0}
F n
=
1
γ n+1 (2z − 1)
E 1
2
(2z)
s n
n
n + 1
,