324
7 Arbres digitaux
Les termes oscillants n’existent que si la source « ressemble » à
une source sans mémoire dont les rapports des log p α , pour α ∈ A, sont
rationnels. Cela induit en effet pour (s) une suite de pôles régulièrement
espacés sur une droite verticale (cas périodique sur la figure 7.8). Pour la
taille des tries, ces fluctuations éventuelles et minimes interviennent dans le
terme dominant. Ce n’est pas le cas pour la longueur de cheminement.
Les termes d’erreur peuvent être précisés par exemple avec les sources sans
mémoire ou les chaînes markoviennes. Dans le cas spécifique des sources sans
mémoire, les termes d’erreurs dépendent de propriétés fines des rapports des
log p α , pour α ∈ A, logarithmes des probabilités des symboles (comme par
exemple l’exposant d’irrationalité lorsque ces rapports sont irrationnels). On
dit qu’un réel positif ν est un exposant d’irrationalité de α si, pour tout ε > 0,
il n’y a qu’un nombre fini de rationnels p/q tel que
α −
p
q
<
1
q ν+ε .
L’exposant d’irrationalité d’un nombre α est le plus petit élément de
l’ensemble des exposants d’irrationalité de α (si l’ensemble est vide, il est
infini). Par exemple pour un nombre algébrique irrationnel, il vaut 2. De
manière informelle, l’exposant d’irrationalité mesure ainsi la qualité des
approximations rationnelles de α. Nous renvoyons à Flajolet et al. [105] et
Roux et Vallée [226] pour plus de détails.
Sources particulières Dans le cas de sources particulières (sans mémoire ou
markovienne), l’expression de (s) est explicite et nous pouvons alors calculer
plusieurs termes du développement asymptotique (pourvu que les pôles puissent
être localisés précisément).
Dans le cas d’une source « périodique » pour laquelle les pôles de (s) sont
régulièrement espacés sur la droite verticale (s) = 1, l’ensemble des pôles
contribue à des fluctuations d’amplitude très petite.
Exemple 7.40 Dans le modèle infini i.i.d. binaire symétrique,
(s) =
1
1 − 2 1−s .
Nous retrouvons les fluctuations obtenues par la méthode élémentaire avec cette
fois-ci le calcul de résidus. La somme des résidus donne alors une expression sous
forme de série de Fourier du terme fluctuant. En effet (s) admet des pôles simples
aux points y k =
1−2ikπ
log 2 . Ces pôles se retrouvent dans le relèvement analytique
(s) (qui dépend du paramètre de trie analysé). Par exemple, pour la longueur de
7 Arbres digitaux
Les termes oscillants n’existent que si la source « ressemble » à
une source sans mémoire dont les rapports des log p α , pour α ∈ A, sont
rationnels. Cela induit en effet pour (s) une suite de pôles régulièrement
espacés sur une droite verticale (cas périodique sur la figure 7.8). Pour la
taille des tries, ces fluctuations éventuelles et minimes interviennent dans le
terme dominant. Ce n’est pas le cas pour la longueur de cheminement.
Les termes d’erreur peuvent être précisés par exemple avec les sources sans
mémoire ou les chaînes markoviennes. Dans le cas spécifique des sources sans
mémoire, les termes d’erreurs dépendent de propriétés fines des rapports des
log p α , pour α ∈ A, logarithmes des probabilités des symboles (comme par
exemple l’exposant d’irrationalité lorsque ces rapports sont irrationnels). On
dit qu’un réel positif ν est un exposant d’irrationalité de α si, pour tout ε > 0,
il n’y a qu’un nombre fini de rationnels p/q tel que
α −
p
q
<
1
q ν+ε .
L’exposant d’irrationalité d’un nombre α est le plus petit élément de
l’ensemble des exposants d’irrationalité de α (si l’ensemble est vide, il est
infini). Par exemple pour un nombre algébrique irrationnel, il vaut 2. De
manière informelle, l’exposant d’irrationalité mesure ainsi la qualité des
approximations rationnelles de α. Nous renvoyons à Flajolet et al. [105] et
Roux et Vallée [226] pour plus de détails.
Sources particulières Dans le cas de sources particulières (sans mémoire ou
markovienne), l’expression de (s) est explicite et nous pouvons alors calculer
plusieurs termes du développement asymptotique (pourvu que les pôles puissent
être localisés précisément).
Dans le cas d’une source « périodique » pour laquelle les pôles de (s) sont
régulièrement espacés sur la droite verticale (s) = 1, l’ensemble des pôles
contribue à des fluctuations d’amplitude très petite.
Exemple 7.40 Dans le modèle infini i.i.d. binaire symétrique,
(s) =
1
1 − 2 1−s .
Nous retrouvons les fluctuations obtenues par la méthode élémentaire avec cette
fois-ci le calcul de résidus. La somme des résidus donne alors une expression sous
forme de série de Fourier du terme fluctuant. En effet (s) admet des pôles simples
aux points y k =
1−2ikπ
log 2 . Ces pôles se retrouvent dans le relèvement analytique
(s) (qui dépend du paramètre de trie analysé). Par exemple, pour la longueur de