7.1 Analyses exactes
301
Pour chaque longueur k de préfixe, les probabilités {p w } w∈A
k définissent une
partition de l’intervalle ]0, 1[ en un ensemble d’intervalles d’intérieurs disjoints
appelés intervalles fondamentaux. 4
Définition 7.19 (Intervalle fondamental) Soit P une mesure de probabilité sur
A
N donnée par la collection {p w } w∈A
∗ . L’intervalle fondamental associé au préfixe
fini w ∈ A
∗ est I w = [a w , b w ] avec
a w =
v≺w
|v|=|w|
p v ,
b w =
v
|v|=|w|
p v = a w + p w ,
(7.18)
où la notation ‘≺’ désigne l’ordre lexicographique sur les mots. Notons que
l’intervalle I w admet bien comme mesure (ou longueur) p w .
Exemple 7.20 Pour préciser les choses, examinons le cas correspondant au modèle
infini i.i.d. binaire uniforme (ce qui équivaut à considérer une source sans mémoire
avec un alphabet binaire et symétrique, les symboles ayant la même probabilité
1/2). Pour un mot w = w 1 w 2 . . . w n , l’intervalle fondamental I w = [a w , b w ] est de
longueur p w = 1/2 n avec
a w =
n
i=1
w i
2 i , b w = a w + p w .
Lorsque la taille des préfixes grandit, nous obtenons des raffinements successifs
de l’intervalle [0, 1]. En effet, nous avons dans ce modèle pour tout mot w fixé
α∈A
p w·α = p w , et I w =
α∈A
I w·α ,
où l’union est une union d’intervalles d’intérieurs disjoints. Inversement, toujours
étant donnée cette collection de probabilités fondamentales
{p w } w∈A
∗ ,
nous définissons une application M : [0, 1] → A
N qui associe à un réel x de
l’intervalle unité I = [0, 1], un mot infini M(x) ∈ A
N .
Définition 7.21 (application M) L’application M est définie presque partout par
M : [0, 1] → A
N
x → M(x) = (m 1 (x), m 2 (x), m 3 (x), . . .).
4 La paramétrisation est basée sur un principe analogue à celui utilisé pour le codage arithmétique
en compression [227].
301
Pour chaque longueur k de préfixe, les probabilités {p w } w∈A
k définissent une
partition de l’intervalle ]0, 1[ en un ensemble d’intervalles d’intérieurs disjoints
appelés intervalles fondamentaux. 4
Définition 7.19 (Intervalle fondamental) Soit P une mesure de probabilité sur
A
N donnée par la collection {p w } w∈A
∗ . L’intervalle fondamental associé au préfixe
fini w ∈ A
∗ est I w = [a w , b w ] avec
a w =
v≺w
|v|=|w|
p v ,
b w =
v
|v|=|w|
p v = a w + p w ,
(7.18)
où la notation ‘≺’ désigne l’ordre lexicographique sur les mots. Notons que
l’intervalle I w admet bien comme mesure (ou longueur) p w .
Exemple 7.20 Pour préciser les choses, examinons le cas correspondant au modèle
infini i.i.d. binaire uniforme (ce qui équivaut à considérer une source sans mémoire
avec un alphabet binaire et symétrique, les symboles ayant la même probabilité
1/2). Pour un mot w = w 1 w 2 . . . w n , l’intervalle fondamental I w = [a w , b w ] est de
longueur p w = 1/2 n avec
a w =
n
i=1
w i
2 i , b w = a w + p w .
Lorsque la taille des préfixes grandit, nous obtenons des raffinements successifs
de l’intervalle [0, 1]. En effet, nous avons dans ce modèle pour tout mot w fixé
α∈A
p w·α = p w , et I w =
α∈A
I w·α ,
où l’union est une union d’intervalles d’intérieurs disjoints. Inversement, toujours
étant donnée cette collection de probabilités fondamentales
{p w } w∈A
∗ ,
nous définissons une application M : [0, 1] → A
N qui associe à un réel x de
l’intervalle unité I = [0, 1], un mot infini M(x) ∈ A
N .
Définition 7.21 (application M) L’application M est définie presque partout par
M : [0, 1] → A
N
x → M(x) = (m 1 (x), m 2 (x), m 3 (x), . . .).
4 La paramétrisation est basée sur un principe analogue à celui utilisé pour le codage arithmétique
en compression [227].