56
2 Aléa sur les arbres
Modèle fini équiprobable Un modèle assez intuitif consiste à considérer un
ensemble de clés finies, toutes de même longueur, indépendantes et de même loi.
Définition 2.16 (Modèle fini équiprobable) Considérons un alphabet A fini de
taille r. Si d est la longueur des clés (ou mots), l’ensemble des clés possibles est A
d
constitué de r d clés distinctes. Le modèle fini équiprobable, si n est le nombre de
clés, est le modèle uniforme sur les sous-ensembles de A
d de cardinal n. Chaque
ensemble est de probabilité 1/
r d
n
.
Dans ce modèle toutes les clés sont équiprobables, de probabilité 1/r d , avec r la
taille de l’alphabet et d la longueur des mots considérés. Les ensembles de clés de
même cardinal sont donc également équiprobables.
Un cas particulier important, et le seul analysé dans ce cadre en section 7.1.1,
correspond au cas binaire A = {0, 1}.
Modèle infini i.i.d. Dans ce modèle les clés sont toujours indépendantes au sens
probabiliste. Mais contrairement au cas précédent, les mots sont infinis.
Définition 2.17 (Modèle infini i.i.d.) Soit n ≥ 1 fixé. Le modèle infini i.i.d. est
le modèle probabiliste qui considère un ensemble ω de n mots indépendants entre
eux et où chaque mot infini de l’ensemble ω est constitué de lettres qui sont des
variables aléatoires i.i.d. à valeur dans l’alphabet A.
Remarque 2.18 Dans le cas où la loi de distribution sur les symboles est uniforme,
il est raisonnable de penser que le modèle infini i.i.d. est la limite (en un sens
à préciser) du modèle fini équiprobable précédent lorsque que le cardinal n de
l’ensemble des mots est fixé et que la taille d des mots tend vers l’infini.
Remarque 2.19 Ce modèle est différent du modèle fini équiprobable, puisqu’il est
possible d’avoir deux clés égales mais avec une probabilité nulle.
Dans la section 7.1.2, nous nous attacherons au cas le plus simple où l’alphabet
est binaire et la distribution sur les symboles 0 et 1 est uniforme.
Dans la section suivante, nous introduisons le concept de source pour modéliser
un mot aléatoire de manière générale.
2.3.2 Sources de symboles : aléa sur les clés
La production de symboles est un phénomène discret dans le temps. À chaque coup
d’horloge, un nouveau symbole est émis par la source. Le choix du symbole à
émettre peut prendre en compte un grand nombre de paramètres. Nous décrivons
ici plusieurs sources dont le mécanisme est probabiliste : deux sources très utilisées
– les sources sans mémoire et les sources à dépendance markovienne – et un modèle
complètement général de source probabilisée.
2 Aléa sur les arbres
Modèle fini équiprobable Un modèle assez intuitif consiste à considérer un
ensemble de clés finies, toutes de même longueur, indépendantes et de même loi.
Définition 2.16 (Modèle fini équiprobable) Considérons un alphabet A fini de
taille r. Si d est la longueur des clés (ou mots), l’ensemble des clés possibles est A
d
constitué de r d clés distinctes. Le modèle fini équiprobable, si n est le nombre de
clés, est le modèle uniforme sur les sous-ensembles de A
d de cardinal n. Chaque
ensemble est de probabilité 1/
r d
n
.
Dans ce modèle toutes les clés sont équiprobables, de probabilité 1/r d , avec r la
taille de l’alphabet et d la longueur des mots considérés. Les ensembles de clés de
même cardinal sont donc également équiprobables.
Un cas particulier important, et le seul analysé dans ce cadre en section 7.1.1,
correspond au cas binaire A = {0, 1}.
Modèle infini i.i.d. Dans ce modèle les clés sont toujours indépendantes au sens
probabiliste. Mais contrairement au cas précédent, les mots sont infinis.
Définition 2.17 (Modèle infini i.i.d.) Soit n ≥ 1 fixé. Le modèle infini i.i.d. est
le modèle probabiliste qui considère un ensemble ω de n mots indépendants entre
eux et où chaque mot infini de l’ensemble ω est constitué de lettres qui sont des
variables aléatoires i.i.d. à valeur dans l’alphabet A.
Remarque 2.18 Dans le cas où la loi de distribution sur les symboles est uniforme,
il est raisonnable de penser que le modèle infini i.i.d. est la limite (en un sens
à préciser) du modèle fini équiprobable précédent lorsque que le cardinal n de
l’ensemble des mots est fixé et que la taille d des mots tend vers l’infini.
Remarque 2.19 Ce modèle est différent du modèle fini équiprobable, puisqu’il est
possible d’avoir deux clés égales mais avec une probabilité nulle.
Dans la section 7.1.2, nous nous attacherons au cas le plus simple où l’alphabet
est binaire et la distribution sur les symboles 0 et 1 est uniforme.
Dans la section suivante, nous introduisons le concept de source pour modéliser
un mot aléatoire de manière générale.
2.3.2 Sources de symboles : aléa sur les clés
La production de symboles est un phénomène discret dans le temps. À chaque coup
d’horloge, un nouveau symbole est émis par la source. Le choix du symbole à
émettre peut prendre en compte un grand nombre de paramètres. Nous décrivons
ici plusieurs sources dont le mécanisme est probabiliste : deux sources très utilisées
– les sources sans mémoire et les sources à dépendance markovienne – et un modèle
complètement général de source probabilisée.