7.1 Analyses exactes
305
Bien évidemment il est possible de revenir au modèle (usuel) de Bernoulli
(B n , S), à nombre n fixé de clés. Les deux équations de la proposition suivante
traduisent (formellement) la poissonisation et dépoissonisation algébrique.
Proposition 7.24 Pour un paramètre v de trie, les relations suivantes permettent
de passer du modèle de Bernoulli (B n , S) à celui de Poisson (P Z , S) :
E Z [v] = e
−Z
∞
n=0
Z n
n!
E n [v],
E n [v] = n![Z
n
]e
Z E Z [v].
(7.21)
Preuve Ces égalités viennent directement de la définition de l’espérance dans le
modèle de Poisson à partir de celle dans le modèle de Bernoulli. La première égalité
n’est d’ailleurs autre que l’équation (7.20).
La relation (7.21), bien qu’explicite, conduit souvent à des expressions compliquées où le comportement asymptotique est difficile à évaluer directement. Ce
sera l’objet d’une analyse asymptotique de déduire les ordres de grandeur à partir
de ces expressions.
Analyse exacte
Les paramètres additifs sont les plus faciles à analyser puisque l’approche généralise
celle que nous avons vue dans la section précédente.
Lemme 7.25 (Paramètres additifs — modèle de Poisson) Considérons le modèle (P Z , S) et un trie aléatoire dans ce modèle. Soient ω ⊂ A
N et un paramètre
additif v s’écrivant
v(ω) = γ (|ω|) +
α∈A
v(ω \ α),
avec γ : N → N une fonction de péage ne dépendant que du cardinal de ω (et
vérifiant γ (0) = γ (1) = 0 puisqu’il s’agit d’un paramètre de trie). Alors nous
avons
E Z [v] =
w∈A
∗
γ (Zp w )
(7.22)
où nous introduisons la série de Poisson γ (z) associée à γ par
γ (z) = e
−z
k≥2
z k
k!
γ (k).
(7.23)