60
2 Aléa sur les arbres
Grâce à cette méthode, nous générons par exemple le texte suivant qui correspond
à une chaîne de Markov du premier ordre (toujours d’après le tome 1 des
Misérables) :
T SSU N CHOIÉT DÉTÈRRNTR DE, ANDES DER CERT ÊM. IT PAVANDENOR U
UNNTINESOUITEL’A STSITE HURQUSUPA CREUIENEUE.
Plutôt que de prendre des dépendances entre deux lettres, nous pouvons considérer
une « fenêtre » sur les derniers symboles émis afin d’émettre le prochain symbole (la
méthode de Shannon s’adapte facilement). Nous obtenons alors des approximations
d’ordre supérieur correspondant à des chaînes de Markov d’ordre supérieur. Par
exemple, nous obtenons
TREMESTAIT LATTEUR. IL SAINS IN ; DANTE MIENT TREST DRA ; VENDAITÉ
CHAINERTENTEL VOTÉ POURE SARQUE LE ENCTIGÉ SANCE.
(Chaîne de Markov deuxième ordre).
LE MADAMNATION DE CHAPILEMENT DANS, LUNE BAIT D’AIR DES D’ELLER SOANE,
PROBLEMENTE, DANS LA MAIS D’INSTRATEUR.
(Chaîne de Markov troisième ordre).
En faisant preuve de beaucoup d’imagination et en acceptant les néologismes au
sens trouble, nous pouvons commencer à trouver un semblant de syntaxe et peutêtre même du sens à cette phrase !
2.4 Aléa et choix de notations
Pour les notations des paramètres évalués pour un arbre marqué aléatoire, disons un
arbre à n nœuds τ n , deux conceptions sont possibles :
(a) considérer que l’aléa est dans l’arbre τ n , de sorte que tous les paramètres sont
des fonctions déterministes, définies sur un ensemble d’arbres, dont on prend la
valeur en un arbre τ n aléatoire. La hauteur d’un arbre binaire de recherche de
taille n sera ainsi notée h(τ n ). Ce point de vue parait simple conceptuellement ;
il a l’inconvénient de considérer que tout l’aléa est dans τ n , ce qui n’est pas le
cas par exemple pour la profondeur d’insertion d’une nouvelle clé (aléatoire)
dans τ n . Nous adopterons alors plutôt le point de vue suivant :
(b) considérer que les paramètres sont des variables aléatoires sur un certain espace
probabilisé. La hauteur d’un arbre binaire de recherche de taille n serait ainsi
notée plutôt h n .
Le point de vue algorithmique général du livre nous a conduit à opter la plupart
du temps pour des notations de type (a), à la fois plus lourdes et plus simples
(!). Nous préférerons parfois le point de vue (b) par exemple pour la profondeur
d’insertion d’une nouvelle clé dans τ n (qui sera notée D n+1 dans la section 6.1).
2 Aléa sur les arbres
Grâce à cette méthode, nous générons par exemple le texte suivant qui correspond
à une chaîne de Markov du premier ordre (toujours d’après le tome 1 des
Misérables) :
T SSU N CHOIÉT DÉTÈRRNTR DE, ANDES DER CERT ÊM. IT PAVANDENOR U
UNNTINESOUITEL’A STSITE HURQUSUPA CREUIENEUE.
Plutôt que de prendre des dépendances entre deux lettres, nous pouvons considérer
une « fenêtre » sur les derniers symboles émis afin d’émettre le prochain symbole (la
méthode de Shannon s’adapte facilement). Nous obtenons alors des approximations
d’ordre supérieur correspondant à des chaînes de Markov d’ordre supérieur. Par
exemple, nous obtenons
TREMESTAIT LATTEUR. IL SAINS IN ; DANTE MIENT TREST DRA ; VENDAITÉ
CHAINERTENTEL VOTÉ POURE SARQUE LE ENCTIGÉ SANCE.
(Chaîne de Markov deuxième ordre).
LE MADAMNATION DE CHAPILEMENT DANS, LUNE BAIT D’AIR DES D’ELLER SOANE,
PROBLEMENTE, DANS LA MAIS D’INSTRATEUR.
(Chaîne de Markov troisième ordre).
En faisant preuve de beaucoup d’imagination et en acceptant les néologismes au
sens trouble, nous pouvons commencer à trouver un semblant de syntaxe et peutêtre même du sens à cette phrase !
2.4 Aléa et choix de notations
Pour les notations des paramètres évalués pour un arbre marqué aléatoire, disons un
arbre à n nœuds τ n , deux conceptions sont possibles :
(a) considérer que l’aléa est dans l’arbre τ n , de sorte que tous les paramètres sont
des fonctions déterministes, définies sur un ensemble d’arbres, dont on prend la
valeur en un arbre τ n aléatoire. La hauteur d’un arbre binaire de recherche de
taille n sera ainsi notée h(τ n ). Ce point de vue parait simple conceptuellement ;
il a l’inconvénient de considérer que tout l’aléa est dans τ n , ce qui n’est pas le
cas par exemple pour la profondeur d’insertion d’une nouvelle clé (aléatoire)
dans τ n . Nous adopterons alors plutôt le point de vue suivant :
(b) considérer que les paramètres sont des variables aléatoires sur un certain espace
probabilisé. La hauteur d’un arbre binaire de recherche de taille n serait ainsi
notée plutôt h n .
Le point de vue algorithmique général du livre nous a conduit à opter la plupart
du temps pour des notations de type (a), à la fois plus lourdes et plus simples
(!). Nous préférerons parfois le point de vue (b) par exemple pour la profondeur
d’insertion d’une nouvelle clé dans τ n (qui sera notée D n+1 dans la section 6.1).