9.5 Applications algorithmiques
391
à deux coordonnées comptant les feuilles de type 1 et 2 à l’instant n. C’est une urne
de Pólya dont la matrice de remplacement est
R =
−2 3
4 −3
C’est l’exemple type de l’article de Flajolet et al. [102] sur les « urnes analytiques »
dont il est question dans la section 9.2. L’urne est équilibrée, de balance égale à 1.
Les valeurs propres de R sont 1 et −6 et d’après le Théorème 9.6,
EY n
n −→ u 1
presque sûrement. Dans cet exemple, la composition initiale est Y 0 = (2, 0) et le
calcul de u 1 peut se faire comme suit. Ce vecteur est d’une part vecteur propre à
gauche pour la matrice R et la valeur propre 1, ce qui donne une première équation
entre les coordonnées x et y de u 1 : −3x + 4y = 0 ; d’autre part, u 1 v 1 = 1,
autrement dit, puisque v 1 = t (1, 1), la somme des coordonnées de u 1 est égale à 1 :
x + y = 1. Finalement, lorsque n → +∞,
EY n
n
−→
4
7
,
3
7
.
Dans la terminologie plus haut (voir la définition 9.7), il s’agit d’une petite
urne et donc le théorème 9.8 ne s’applique pas. Nous pouvons montrer que le
terme du second ordre dans le développement asymptotique converge en distribution
vers une loi gaussienne par plongement en temps continu, cf. Janson [147] ou par
combinatoire analytique, cf. Flajolet et al. [103]. La proposition suivante résume
cela.
Proposition 9.13 Soit Y n le vecteur à deux coordonnées comptant les feuilles de
type 1 et 2 dans un arbre 2–3 à n clés. C’est une urne de Pólya dont la matrice de
remplacement est
R =
−2 3
4 −3
.
Alors, lorsque n → +∞,
EY n
n
−→
4
7
,
3
7
.
De plus,
Y n − EY n
√
n
D
−→
n→∞
N(0, ,
2 ),
391
à deux coordonnées comptant les feuilles de type 1 et 2 à l’instant n. C’est une urne
de Pólya dont la matrice de remplacement est
R =
−2 3
4 −3
C’est l’exemple type de l’article de Flajolet et al. [102] sur les « urnes analytiques »
dont il est question dans la section 9.2. L’urne est équilibrée, de balance égale à 1.
Les valeurs propres de R sont 1 et −6 et d’après le Théorème 9.6,
EY n
n −→ u 1
presque sûrement. Dans cet exemple, la composition initiale est Y 0 = (2, 0) et le
calcul de u 1 peut se faire comme suit. Ce vecteur est d’une part vecteur propre à
gauche pour la matrice R et la valeur propre 1, ce qui donne une première équation
entre les coordonnées x et y de u 1 : −3x + 4y = 0 ; d’autre part, u 1 v 1 = 1,
autrement dit, puisque v 1 = t (1, 1), la somme des coordonnées de u 1 est égale à 1 :
x + y = 1. Finalement, lorsque n → +∞,
EY n
n
−→
4
7
,
3
7
.
Dans la terminologie plus haut (voir la définition 9.7), il s’agit d’une petite
urne et donc le théorème 9.8 ne s’applique pas. Nous pouvons montrer que le
terme du second ordre dans le développement asymptotique converge en distribution
vers une loi gaussienne par plongement en temps continu, cf. Janson [147] ou par
combinatoire analytique, cf. Flajolet et al. [103]. La proposition suivante résume
cela.
Proposition 9.13 Soit Y n le vecteur à deux coordonnées comptant les feuilles de
type 1 et 2 dans un arbre 2–3 à n clés. C’est une urne de Pólya dont la matrice de
remplacement est
R =
−2 3
4 −3
.
Alors, lorsque n → +∞,
EY n
n
−→
4
7
,
3
7
.
De plus,
Y n − EY n
√
n
D
−→
n→∞
N(0, ,
2 ),