9.5 Applications algorithmiques
395
Par conséquent assurons-nous que la condition arithmétique (9.1) est satisfaite : en
effet, les colonnes de R m sont successivement multiples de m, m + 1, . . . , 2m − 1.
Considérons comme d’habitude le vecteur composition de l’urne Y n . Fixons
un entier m ≥ 2. Pour déterminer s’il s’agit d’une petite ou d’une grande urne
et connaître ainsi le comportement asymptotique de Y n quand n tend vers +∞,
cherchons les valeurs propres de R m . Le polynôme caractéristique de R m est
χ m (X) =
2m−1
k=m
(X + k) −
(2m)!
m!
.
Ce polynôme ressemble à celui des arbres m-aires de recherche (voir
l’expression (9.12)). Les valeurs propres ont les mêmes propriétés : λ = 1 est
une racine, toutes les racines sont simples, les racines non réelles sont conjuguées
deux à deux. De plus, 1 est la valeur propre de plus grande partie réelle, toutes les
autres valeurs propres ont une partie réelle strictement inférieure à 1.
Appelons σ la plus grande partie réelle de valeur propre différente de 1 :
σ := max{{(λ), λ valeur propre, λ = 1}
et si m ≥ 3, appelons λ 2 , λ 2 les deux valeurs propres conjuguées de partie réelle σ .
Il apparaît 10 que les valeurs propres différentes de 1 ont toutes une partie réelle
≤ 1/2 si et seulement si m ≤ 59, autrement dit :
σ ≤
1
2
⇐⇒ m ≤ 59 ⇐⇒ l’urne est petite ;
σ >
1
2
⇐⇒ m ≥ 60 ⇐⇒ l’urne est grande.
Comme, en pratique, les arbres-B sont utilisés pour de grandes valeurs de m
(supérieures à 100), cet exemple fournit une illustration algorithmique d’une grande
urne de Pólya.
Quelques résultats pour les arbres-B
Pour tous les arbres-B, grands et petits, nous avons
Y n
n
−→
n→∞
u 1 presque sûrement
et en moyenne, ce qui donne la composition asymptotique de l’urne, c’est-à-dire le
nombre de gaps de chaque type.
10 Les calculs effectués avec l’aide d’un système de calcul formel indiquent une monotonie de σ
en m ; le démontrer !