7.2 Analyses asymptotiques
317
Définition 7.34 (Entropie et coïncidence) L’entropie h(S) de la source S est
définie comme la limite, lorsqu’elle existe, d’une quantité où interviennent les
probabilités fondamentales
h(S) = lim
k→∞
−1
k
w∈A
k
p w log p w = lim
k→∞
−1
k
d
ds
k (s)
s=1 .
(7.31)
Le coefficient de coïncidence c(S) est la longueur moyenne du préfixe commun de
deux mots produits indépendamment par la source
c(S) =
w∈A
∗
p
2
w =
Remarque 7.35 Dans le cas des sources simples précédentes, sans mémoire ou à
dépendance markovienne : l’entropie est −λ (1). Pour une source sans mémoire
λ(s) est définie en (7.30). Pour une source à dépendance markovienne, lorsque
la matrice de transition P (s) associée à la chaîne de Markov est apériodique et
irréductible (voir [20]), alors λ(s) est la valeur propre dominante (de plus grand
module) de la matrice P (s).
Lorsque (s) est analytique dans un domaine contenant s = 1, les propriétés de
régularité de la source s’expriment grâce à celles de dans ce domaine.
Nous pouvons systématiser l’étude des séries rencontrées usuellement dans
les analyses d’arbres digitaux dans le modèle des clés infinies produites par une
source, en utilisant les propriétés analytiques de la série de Dirichlet associée
à la source. L’approche décrite dans cette section repose sur une formule de
dépoissonisation algébrique différente de l’équation (7.21). Cette nouvelle approche
se révèle particulièrement adaptée aux paramètres additifs. Soit un paramètre additif
γ : N → N tel que γ (0) = γ (1) = 0. Introduisons la série de Poisson associée à la
suite (γ (n)) n≥0 :
γ (z) = e
−z
∞
n=2
γ (n)
z n
n!
.
Rappelons que γ (z) est aussi l’espérance de la variable aléatoire γ (N) pour N
variable de Poisson de paramètre z.
Pour appliquer la formule de Rice, nous allons recourir à une formule de
dépoissonisation un peu différente, qui se base sur la transformée binomiale (aussi
nommée transformée d’Euler et rappelée dans l’annexe B.3.4) de la suite (γ (n)) n≥0 .
La transformée (ϕ(n)) est définie pour n ≥ 0 à partir de la séquence (γ (k)) par
ϕ(n) =
n
k=0
n
k
(−1)
k γ (k).
(7.32)
317
Définition 7.34 (Entropie et coïncidence) L’entropie h(S) de la source S est
définie comme la limite, lorsqu’elle existe, d’une quantité où interviennent les
probabilités fondamentales
h(S) = lim
k→∞
−1
k
w∈A
k
p w log p w = lim
k→∞
−1
k
d
ds
k (s)
s=1 .
(7.31)
Le coefficient de coïncidence c(S) est la longueur moyenne du préfixe commun de
deux mots produits indépendamment par la source
c(S) =
w∈A
∗
p
2
w =
Remarque 7.35 Dans le cas des sources simples précédentes, sans mémoire ou à
dépendance markovienne : l’entropie est −λ (1). Pour une source sans mémoire
λ(s) est définie en (7.30). Pour une source à dépendance markovienne, lorsque
la matrice de transition P (s) associée à la chaîne de Markov est apériodique et
irréductible (voir [20]), alors λ(s) est la valeur propre dominante (de plus grand
module) de la matrice P (s).
Lorsque (s) est analytique dans un domaine contenant s = 1, les propriétés de
régularité de la source s’expriment grâce à celles de dans ce domaine.
Nous pouvons systématiser l’étude des séries rencontrées usuellement dans
les analyses d’arbres digitaux dans le modèle des clés infinies produites par une
source, en utilisant les propriétés analytiques de la série de Dirichlet associée
à la source. L’approche décrite dans cette section repose sur une formule de
dépoissonisation algébrique différente de l’équation (7.21). Cette nouvelle approche
se révèle particulièrement adaptée aux paramètres additifs. Soit un paramètre additif
γ : N → N tel que γ (0) = γ (1) = 0. Introduisons la série de Poisson associée à la
suite (γ (n)) n≥0 :
γ (z) = e
−z
∞
n=2
γ (n)
z n
n!
.
Rappelons que γ (z) est aussi l’espérance de la variable aléatoire γ (N) pour N
variable de Poisson de paramètre z.
Pour appliquer la formule de Rice, nous allons recourir à une formule de
dépoissonisation un peu différente, qui se base sur la transformée binomiale (aussi
nommée transformée d’Euler et rappelée dans l’annexe B.3.4) de la suite (γ (n)) n≥0 .
La transformée (ϕ(n)) est définie pour n ≥ 0 à partir de la séquence (γ (k)) par
ϕ(n) =
n
k=0
n
k
(−1)
k γ (k).
(7.32)