390
9 Urnes de Pólya et applications
où la convergence exprimée par le petit o est presque sûre et dans tous les
L p , p ≥ 1, où W est une variable aléatoire à valeurs complexes, et
u 2 =
1
H m (λ 2 )
1
k
λ 2 +k
k
1≤k≤m−1
.
Dans le développement asymptotique (9.14) de X n , W est une variable aléatoire
complexe, limite de martingale, dont nous pouvons calculer récursivement les
moments. La loi de cette variable aléatoire est encore mystérieuse et fait l’objet
de recherches en cours [40, 42, 155], notamment par méthode de contraction (voir
section 6.1.3) et par la méthode de plongement en temps continu exposée dans la
section 9.4.
9.5.2 Arbres 2–3
Les arbres 2–3 ont été définis et décrits algorithmiquement à la section 1.2.6. Le
modèle aléatoire est, comme pour les abr, celui des permutations uniformes. Il y a
deux types de feuilles : les feuilles de type 1 ont un parent qui contient une seule clé
; les feuilles de type 2 ont un parent qui contient 2 clés. La règle d’insertion dans
l’arbre produit la transformation suivante sur les feuilles, illustrée dans la figure 9.2
ci-dessous.
L’étude mathématique de ces arbres est difficile ; par exemple nous ne savons pas
encore prouver que la hauteur a un comportement asymptotique presque sûr d’ordre
log n avec une constante égale à 1. Il est néanmoins facile de compter les feuilles de
différents types : considérons l’urne de Pólya où les boules sont les feuilles (i.e. les
intervalles vacants) et les couleurs sont les types de feuilles. Appelons Y n le vecteur
Fig. 9.2 Règle d’insertion dans un arbre 2–3
9 Urnes de Pólya et applications
où la convergence exprimée par le petit o est presque sûre et dans tous les
L p , p ≥ 1, où W est une variable aléatoire à valeurs complexes, et
u 2 =
1
H m (λ 2 )
1
k
λ 2 +k
k
1≤k≤m−1
.
Dans le développement asymptotique (9.14) de X n , W est une variable aléatoire
complexe, limite de martingale, dont nous pouvons calculer récursivement les
moments. La loi de cette variable aléatoire est encore mystérieuse et fait l’objet
de recherches en cours [40, 42, 155], notamment par méthode de contraction (voir
section 6.1.3) et par la méthode de plongement en temps continu exposée dans la
section 9.4.
9.5.2 Arbres 2–3
Les arbres 2–3 ont été définis et décrits algorithmiquement à la section 1.2.6. Le
modèle aléatoire est, comme pour les abr, celui des permutations uniformes. Il y a
deux types de feuilles : les feuilles de type 1 ont un parent qui contient une seule clé
; les feuilles de type 2 ont un parent qui contient 2 clés. La règle d’insertion dans
l’arbre produit la transformation suivante sur les feuilles, illustrée dans la figure 9.2
ci-dessous.
L’étude mathématique de ces arbres est difficile ; par exemple nous ne savons pas
encore prouver que la hauteur a un comportement asymptotique presque sûr d’ordre
log n avec une constante égale à 1. Il est néanmoins facile de compter les feuilles de
différents types : considérons l’urne de Pólya où les boules sont les feuilles (i.e. les
intervalles vacants) et les couleurs sont les types de feuilles. Appelons Y n le vecteur
Fig. 9.2 Règle d’insertion dans un arbre 2–3