7.1 Analyses exactes
303
Preuve La mesure image de λ par M, notée pour l’instant M(λ), est définie pour
n’importe quel sous-ensemble B de A
N par
M(λ)(B) = λ(M
−1 (B)).
Soit w ∈ A
∗ , et C w = w · A
N le cylindre associé. Nous avons
M(λ)(C w ) = λ(M
−1 (C w ))
= λ({x | M(x) ∈ C w })
= λ(I w )
= p w .
Comme la famille des C w engendre tous les sous-ensembles mesurables de A
N , et
que la mesure P est caractérisée par sa valeur sur les cylindres, nous concluons que
M(λ) = P.
Cette proposition permet de paramétrer par l’intervalle [0, 1] les mots infinis.
Tirer un mot infini de A N pour une source probabilisée S (définie par ses probabilités
fondamentales (p w )) revient à tirer uniformément un réel x de [0, 1] et à considérer le
mot infini M(x). De plus cette paramétrisation « préserve » l’ordre entre les réels de
l’intervalle [0, 1] et l’ordre lexicographique (‘≺’) sur les mots, i.e., x < y ⇔ M(x) ≺
M(y).
Modèles de Poisson et de Bernoulli pour le cardinal
Dans ce qui constitue sûrement un abus de langage (mais qui est entré dans les
usages) nous nommons modèle de Bernoulli le modèle usuel et naturel où le nombre
de clés est fixé.
Dans la suite nous auront recours dans les analyses à un modèle différent, dit
modèle de Poisson, qui introduit un aléa supplémentaire sur le nombre de clés
dans le trie. L’intérêt de ce modèle est qu’il permet de simplifier les calculs, mais
en général nous préférons donner les résultats dans le modèle, plus « parlant »,
de Bernoulli. Nous décrivons formellement ces deux modèles et les liens qui les
unissent ci-après.
Modèle de Bernoulli Dans ce modèle nous considérons un ensemble de n
mots infinis X = {X 1 , . . . , X n } produits par une source S. Cet ensemble est
supposé obtenu en tirant indépendamment et uniformément des réels x 1 , . . . , x n
de l’intervalle [0, 1]. Nous associons à chaque réel x i ∈ [0, 1] un mot infini
X i = M(x i ) ∈ A
N pour i ∈ {1, . . . , n} grâce au codage M. Nous obtenons
ainsi le modèle de Bernoulli noté (B n , S) relatif au cardinal n de l’ensemble
X = {X 1 , . . . , X n } et la source S.
303
Preuve La mesure image de λ par M, notée pour l’instant M(λ), est définie pour
n’importe quel sous-ensemble B de A
N par
M(λ)(B) = λ(M
−1 (B)).
Soit w ∈ A
∗ , et C w = w · A
N le cylindre associé. Nous avons
M(λ)(C w ) = λ(M
−1 (C w ))
= λ({x | M(x) ∈ C w })
= λ(I w )
= p w .
Comme la famille des C w engendre tous les sous-ensembles mesurables de A
N , et
que la mesure P est caractérisée par sa valeur sur les cylindres, nous concluons que
M(λ) = P.
Cette proposition permet de paramétrer par l’intervalle [0, 1] les mots infinis.
Tirer un mot infini de A N pour une source probabilisée S (définie par ses probabilités
fondamentales (p w )) revient à tirer uniformément un réel x de [0, 1] et à considérer le
mot infini M(x). De plus cette paramétrisation « préserve » l’ordre entre les réels de
l’intervalle [0, 1] et l’ordre lexicographique (‘≺’) sur les mots, i.e., x < y ⇔ M(x) ≺
M(y).
Modèles de Poisson et de Bernoulli pour le cardinal
Dans ce qui constitue sûrement un abus de langage (mais qui est entré dans les
usages) nous nommons modèle de Bernoulli le modèle usuel et naturel où le nombre
de clés est fixé.
Dans la suite nous auront recours dans les analyses à un modèle différent, dit
modèle de Poisson, qui introduit un aléa supplémentaire sur le nombre de clés
dans le trie. L’intérêt de ce modèle est qu’il permet de simplifier les calculs, mais
en général nous préférons donner les résultats dans le modèle, plus « parlant »,
de Bernoulli. Nous décrivons formellement ces deux modèles et les liens qui les
unissent ci-après.
Modèle de Bernoulli Dans ce modèle nous considérons un ensemble de n
mots infinis X = {X 1 , . . . , X n } produits par une source S. Cet ensemble est
supposé obtenu en tirant indépendamment et uniformément des réels x 1 , . . . , x n
de l’intervalle [0, 1]. Nous associons à chaque réel x i ∈ [0, 1] un mot infini
X i = M(x i ) ∈ A
N pour i ∈ {1, . . . , n} grâce au codage M. Nous obtenons
ainsi le modèle de Bernoulli noté (B n , S) relatif au cardinal n de l’ensemble
X = {X 1 , . . . , X n } et la source S.