2.3 Aléa sur les arbres digitaux
57
Soit A = {a 1 , a 2 , . . . , a r } un alphabet fini. Une quantité très importante va jouer
un rôle dans la suite, il s’agit de la probabilité qu’un mot infini X ∈ A
N commence
par un préfixe w ∈ A
∗ , appelée probabilité fondamentale.
Définition 2.20 (Probabilités fondamentales, cylindres et sources) Soit P une
mesure de probabilité définie sur l’ensemble des mots infinis A
N . Soit w ∈ A
∗
un mot fini.
– L’ensemble des mots infinis C w = w · A
N admettant w comme préfixe est appelé
cylindre associé à w.
– La probabilité fondamentale associée au préfixe fini w ∈ A
∗ est définie par
p w := P(w · A
N ) = P(C w ).
La connaissance de P sur les cylindres {C w } w∈A
∗ suffit à décrire P ; une source S
est définie indifféremment par la mesure P ou par la collection des p w .
Remarque 2.21 Une famille {p w } w∈A
∗ de réels de [0, 1] qui satisfait p ε = 1 et les
relations de compatibilité
a∈A
p w·a = p w
(∀w ∈ A
∗ )
suffit à définir P sur A
N , c’est-à-dire une source, en posant P(C w ) = p w . En effet, le
théorème de Kolmogorov (voir Billingsley [28]) assure alors qu’il existe une unique
probabilité P sur A
N qui prolonge P sur les cylindres.
2.3.3 Sources sans mémoire
Définition 2.22 (Source sans mémoire) Une source sans mémoire sur l’alphabet
A est définie par une distribution de probabilité sur les symboles {p a } a∈A , avec
a∈A p a = 1. Pour tout mot fini w = w 1 w 2 . . . w n avec w i dans A, la probabilité
fondamentale p w est
p w =
n
i=1
p w i ,
ce qui définit également la mesure P.
Une source sans mémoire ne tient aucun compte des symboles précédemment émis :
il n’y a aucune dépendance entre deux symboles émis par la source.
Pour la langue française avec un alphabet de taille 27 (les lettres usuelles plus
le caractère « espace »), une première tentative (grossière) de modélisation consiste
à émettre chaque symbole avec une probabilité
1
27 . Un exemple typique d’un mot
57
Soit A = {a 1 , a 2 , . . . , a r } un alphabet fini. Une quantité très importante va jouer
un rôle dans la suite, il s’agit de la probabilité qu’un mot infini X ∈ A
N commence
par un préfixe w ∈ A
∗ , appelée probabilité fondamentale.
Définition 2.20 (Probabilités fondamentales, cylindres et sources) Soit P une
mesure de probabilité définie sur l’ensemble des mots infinis A
N . Soit w ∈ A
∗
un mot fini.
– L’ensemble des mots infinis C w = w · A
N admettant w comme préfixe est appelé
cylindre associé à w.
– La probabilité fondamentale associée au préfixe fini w ∈ A
∗ est définie par
p w := P(w · A
N ) = P(C w ).
La connaissance de P sur les cylindres {C w } w∈A
∗ suffit à décrire P ; une source S
est définie indifféremment par la mesure P ou par la collection des p w .
Remarque 2.21 Une famille {p w } w∈A
∗ de réels de [0, 1] qui satisfait p ε = 1 et les
relations de compatibilité
a∈A
p w·a = p w
(∀w ∈ A
∗ )
suffit à définir P sur A
N , c’est-à-dire une source, en posant P(C w ) = p w . En effet, le
théorème de Kolmogorov (voir Billingsley [28]) assure alors qu’il existe une unique
probabilité P sur A
N qui prolonge P sur les cylindres.
2.3.3 Sources sans mémoire
Définition 2.22 (Source sans mémoire) Une source sans mémoire sur l’alphabet
A est définie par une distribution de probabilité sur les symboles {p a } a∈A , avec
a∈A p a = 1. Pour tout mot fini w = w 1 w 2 . . . w n avec w i dans A, la probabilité
fondamentale p w est
p w =
n
i=1
p w i ,
ce qui définit également la mesure P.
Une source sans mémoire ne tient aucun compte des symboles précédemment émis :
il n’y a aucune dépendance entre deux symboles émis par la source.
Pour la langue française avec un alphabet de taille 27 (les lettres usuelles plus
le caractère « espace »), une première tentative (grossière) de modélisation consiste
à émettre chaque symbole avec une probabilité
1
27 . Un exemple typique d’un mot