Philippe Jacquet: Poissonization and Depoissonization of Generating Functions

Poissonization is an elegant way to map recursive combinatorial sequences into generating functions (Poisson transform). See tries, divide and conquer, Patricia tries, etc. Moreover there is a Tauberian theorem (Depoissonization theorem) that maps the asymptotics of the Poisson transform and the asymptotics of the original sequence. We show that under very light conditions the asymptotic mapping can be extended to any arbitrary orders. We will show more complicated and generalized Depoissonization theorems applied on doubled indexed sequence (two-variate Poisson transform) applied to dynamical sources, digital search trees and compression redundancy calculation. We will end with some Poissonization theorems that have been applied to entropy calculation of binomial random variables.

Back to the Index


Please send comments and corrections to Thomas Klausner.