316
7 Arbres digitaux
Série de Dirichlet de la source Pour les sources les plus simples où il n’y a pas
de dépendance entre les lettres des mots, les probabilités fondamentales vérifient
une propriété multiplicative. En effet pour une source sans mémoire et deux mots
w, w ∈ A
∗ nous avons l’égalité p w·w = p w p w . Lorsque la source est « moins
simple » (par exemple avec une dépendance markovienne entre les lettres), une
version affaiblie de cette égalité reste vraie. C’est cette propriété multiplicative
qui motive le fait de définir une série génératrice de type Dirichlet associée à la
source plutôt qu’une série génératrice usuelle en combinatoire (et plutôt adaptée
à des propriétés additives). De manière analogue au cas des séries génératrices
(ordinaires, exponentielles) utilisées en combinatoire analytique, la série génératrice
(de Dirichlet) traduit de manière analytique les propriétés probabilistes de la source.
Les analyses font intervenir diverses séries de type « Dirichlet » de probabilités
fondamentales, dont les plus importantes sont (pour s ∈ C)
k (s) =
w∈A
k
p
s
w , ,(s) =
w∈A
∗
p
s
w =
k≥0
k (s).
(7.29)
La série (s) est toujours non définie en s = 1 (puisque k (1) =
w∈A
k p w = 1
pour tout k ≥ 0).
Exemple 7.32 Pour une source sans mémoire avec probabilités des symboles
{p α } α∈A , nous avons pour s ∈ C,
k (s) = λ(s)
k , ,(s) =
1
1 − λ(s)
, en posant λ(s) =
α∈A
p
s
α .
(7.30)
Exemple 7.33 Pour une source markovienne de matrice de transition
P =
p β|α
(α,β)∈A×A
et de distribution initiale (π α ) α∈A (vue comme un vecteur ligne), nous notons pour
s ∈ C,
P (s) =
p
s
β|α
(α,β)∈A×A
;
π(s) = (π
s
α ) α∈A .
Nous exprimons alors les séries de Dirichlet comme
k (s) = π(s)P (s)
k
1
. . .
1
; = π(s)(I − P (s))
−1
1
. . .
1
.
Deux grandeurs caractéristiques de la source jouent un rôle très important dans
la suite.
7 Arbres digitaux
Série de Dirichlet de la source Pour les sources les plus simples où il n’y a pas
de dépendance entre les lettres des mots, les probabilités fondamentales vérifient
une propriété multiplicative. En effet pour une source sans mémoire et deux mots
w, w ∈ A
∗ nous avons l’égalité p w·w = p w p w . Lorsque la source est « moins
simple » (par exemple avec une dépendance markovienne entre les lettres), une
version affaiblie de cette égalité reste vraie. C’est cette propriété multiplicative
qui motive le fait de définir une série génératrice de type Dirichlet associée à la
source plutôt qu’une série génératrice usuelle en combinatoire (et plutôt adaptée
à des propriétés additives). De manière analogue au cas des séries génératrices
(ordinaires, exponentielles) utilisées en combinatoire analytique, la série génératrice
(de Dirichlet) traduit de manière analytique les propriétés probabilistes de la source.
Les analyses font intervenir diverses séries de type « Dirichlet » de probabilités
fondamentales, dont les plus importantes sont (pour s ∈ C)
k (s) =
w∈A
k
p
s
w , ,(s) =
w∈A
∗
p
s
w =
k≥0
k (s).
(7.29)
La série (s) est toujours non définie en s = 1 (puisque k (1) =
w∈A
k p w = 1
pour tout k ≥ 0).
Exemple 7.32 Pour une source sans mémoire avec probabilités des symboles
{p α } α∈A , nous avons pour s ∈ C,
k (s) = λ(s)
k , ,(s) =
1
1 − λ(s)
, en posant λ(s) =
α∈A
p
s
α .
(7.30)
Exemple 7.33 Pour une source markovienne de matrice de transition
P =
p β|α
(α,β)∈A×A
et de distribution initiale (π α ) α∈A (vue comme un vecteur ligne), nous notons pour
s ∈ C,
P (s) =
p
s
β|α
(α,β)∈A×A
;
π(s) = (π
s
α ) α∈A .
Nous exprimons alors les séries de Dirichlet comme
k (s) = π(s)P (s)
k
1
. . .
1
; = π(s)(I − P (s))
−1
1
. . .
1
.
Deux grandeurs caractéristiques de la source jouent un rôle très important dans
la suite.