240
6 Arbres binaires de recherche
Fig. 6.6 Estimation de la densité de la variable Y n = (lce(τ n )−E[lce(τ n )])/(n+1) pour n = 500
à l’aide d’un échantillon de 200 000 abr aléatoires tirés selon la loi Ord
6.1.4 Simulation de la loi limite
Pour simuler la densité de la loi limite de Y n = (lce(τ n ) − E[lce(τ n )])/(n + 1)
quand n tend vers l’infini, plusieurs méthodes sont possibles. La plus évidente est
de dessiner un histogramme de Y n pour n suffisamment grand et pour un échantillon
de grande taille d’abr tirés selon la loi Ord. C’est ce qui est représenté dans la
figure 6.6 ci-dessous.
Une autre méthode 6 consiste à utiliser les résultats de la section 6.1.3 précédente
et notamment l’équation en loi (6.16) satisfaite par Y qui est la limite presque sûre
et en loi de Y n quand n tend vers l’infini. Rappelons cette équation :
Y
L
= UY
(1)
+ (1 − U)Y
(2)
+ C(U ),
(6.19)
où C est la fonction C(x) = 2x log x + 2(1 − x) log(1 − x) + 1, U est de loi
uniforme sur l’intervalle [0, 1], Y, Y (1) , Y (2) sont indépendantes, de même loi et
indépendantes de U .
Nous avons vu que la loi limite Y est le point fixe de la transformation
F −→ S(F ) = L(U X
(1)
+ (1 − U)X
(2)
+ C(U )),
où X (1) et X (2) sont indépendantes et de même loi F , et où U est de loi uniforme
sur [0, 1], indépendante de X (1) et X (2) . Par conséquent, si nous initialisons avec
une variable aléatoire W 0 de loi uniforme sur [0, 1] et notons W n+1 = S(W n ) pour
6 La mise en œuvre de cette méthode, exposée ici, est due à Nicolas Pouyanne, que nous remercions
pour son aide.