9.6 Exercices
397
9.3. Pour n’importe quelle urne, si N = α + β, montrer que le nombre total d’histoires de
longueur n partant de
α
β
est
N
N + S
N + 2S
. . .
N + (n − 1)S
= n!S
n
N
S + n − 1
n
.
9.4.
(a) Pour l’urne originelle R = SI 2 , montrer que la fonction génératrice des histoires est
H
x, y, z
u 0
v 0
=
x u 0 y v 0
1 − Szx S
u 0
S
1 − Szy S
v 0
S
.
Indication : faire des manipulations sur les séries entières multivariées à partir de
1
(1−X) N =
n≥0
N+n−1
n
X n .
(b) Montrer que le système différentiel associé par le théorème « basic isomorphism » s’écrit
X = X S+1 , Y = Y S+1 , et le résoudre. Montrer que le problème de Cauchy a pour solution
X(t) = x(1 − Stx S ) −1/S , Y (t) = y(1 − Sty S ) −1/S et retrouver le résultat de (a).
9.5. Soit Y n le vecteur composition de l’urne d’un arbre-B dans sa forme optimiste de
paramètre m − 1. La matrice de remplacement de l’urne est R m donnée par (9.16).
(a) Montrer que le nombre de feuilles N n est
N n =
Y
(1)
n
m
+
Y
(2)
n
m + 1
+ · · · +
Y
(m)
n
2m − 1
.
(b) En déduire que
N n
n
−→
n→∞
L :=
1
2mH m+1 (m)
p.s. avec la notation H m (z) =
1≤k≤m−1
1
z + k
.
(c) Trouver la limite quand n tend vers l’infini de l’arité moyenne d’une feuille. En déduire que
pour m grand, cette arité est équivalente à 2m ln 2.
9.6. On considère un arbre-B prudent de paramètre m, et l’urne correspondante de matrice de
remplacement r m donnée par (9.15).
(a) Calculer le polynôme caractéristique de r m .
(b) Montrer que λ 1 = 1 est valeur propre.
(c) Calculer u 1 vecteur propre à gauche associé à la valeur propre 1, de sorte que v 1 = t (1, . . . , 1)
soit vecteur propre à droite pour la valeur propre λ 1 = 1, et que u 1 v 1 = 1.
(d) En déduire la limite presque sûre de
Yn
n .
9.7. On considère un arbre-B dans sa forme optimiste de paramètre m − 1, et l’urne
correspondante de matrice de remplacement R m donnée par (9.16).
On appelle λ 2 et λ 2 les valeurs propres conjuguées dont la partie réelle est la plus grande (en
restant < 1).
Pour k = 1, 2, . . . , m, on appelle X k (t) le processus de branchement à m types obtenu par
plongement de l’urne en temps continu (voir section 9.4.1), partant à l’instant 0 d’une particule de
type k.
(a) Appliquer à X k (t) la propriété de branchement au premier instant de saut τ pour écrire les
équations de dislocation vérifiées par les X k (t), pour k = 1, 2, . . . , m.
397
9.3. Pour n’importe quelle urne, si N = α + β, montrer que le nombre total d’histoires de
longueur n partant de
α
β
est
N
N + S
N + 2S
. . .
N + (n − 1)S
= n!S
n
N
S + n − 1
n
.
9.4.
(a) Pour l’urne originelle R = SI 2 , montrer que la fonction génératrice des histoires est
H
x, y, z
u 0
v 0
=
x u 0 y v 0
1 − Szx S
u 0
S
1 − Szy S
v 0
S
.
Indication : faire des manipulations sur les séries entières multivariées à partir de
1
(1−X) N =
n≥0
N+n−1
n
X n .
(b) Montrer que le système différentiel associé par le théorème « basic isomorphism » s’écrit
X = X S+1 , Y = Y S+1 , et le résoudre. Montrer que le problème de Cauchy a pour solution
X(t) = x(1 − Stx S ) −1/S , Y (t) = y(1 − Sty S ) −1/S et retrouver le résultat de (a).
9.5. Soit Y n le vecteur composition de l’urne d’un arbre-B dans sa forme optimiste de
paramètre m − 1. La matrice de remplacement de l’urne est R m donnée par (9.16).
(a) Montrer que le nombre de feuilles N n est
N n =
Y
(1)
n
m
+
Y
(2)
n
m + 1
+ · · · +
Y
(m)
n
2m − 1
.
(b) En déduire que
N n
n
−→
n→∞
L :=
1
2mH m+1 (m)
p.s. avec la notation H m (z) =
1≤k≤m−1
1
z + k
.
(c) Trouver la limite quand n tend vers l’infini de l’arité moyenne d’une feuille. En déduire que
pour m grand, cette arité est équivalente à 2m ln 2.
9.6. On considère un arbre-B prudent de paramètre m, et l’urne correspondante de matrice de
remplacement r m donnée par (9.15).
(a) Calculer le polynôme caractéristique de r m .
(b) Montrer que λ 1 = 1 est valeur propre.
(c) Calculer u 1 vecteur propre à gauche associé à la valeur propre 1, de sorte que v 1 = t (1, . . . , 1)
soit vecteur propre à droite pour la valeur propre λ 1 = 1, et que u 1 v 1 = 1.
(d) En déduire la limite presque sûre de
Yn
n .
9.7. On considère un arbre-B dans sa forme optimiste de paramètre m − 1, et l’urne
correspondante de matrice de remplacement R m donnée par (9.16).
On appelle λ 2 et λ 2 les valeurs propres conjuguées dont la partie réelle est la plus grande (en
restant < 1).
Pour k = 1, 2, . . . , m, on appelle X k (t) le processus de branchement à m types obtenu par
plongement de l’urne en temps continu (voir section 9.4.1), partant à l’instant 0 d’une particule de
type k.
(a) Appliquer à X k (t) la propriété de branchement au premier instant de saut τ pour écrire les
équations de dislocation vérifiées par les X k (t), pour k = 1, 2, . . . , m.