Analytical dePoissonization and its applications

In combinatorics and analysis of algorithms a Poisson version of a problem (henceforth called Poisson model or poissonization) is often easier to solve than the original one, which we name here the Bernoulli model. Poissonization is a technique that replaces the original input (e.g., think of balls thrown into urns) by a Poisson process (e.g., think of balls arriving according to a Poisson process into urns). More precisely, analytical Poisson transform maps a sequence (e.g., characterizing the Bernoulli model) into a generating function of a complex variable. However, after poissonization one must depoissonize in order to translate the results of the Poisson model into the original (i.e., Bernoulli) model. We present in this paper several analytical depoissonization results that fall into the following general scheme: If the Poisson transform has an appropriate growth in the complex plane, then an asymptotic expansion of the sequence can be expressed in terms of the Poisson transform and its derivatives evaluated on the real line. Not surprisingly, actual formulations of depoissonization results depend on the nature of the growth of the Poisson transform, and thus we have polynomial and exponential depoissonization theorems. Normalization (e.g., as in the central limit theorem) introduces another twist that led us to formulate the so-called diagonal depoissonization theorems. Finally, we illustrate our results on numerous examples from combinatorics and the analysis of algorithms and data structures (e.g., combinatorial assemblies, digital trees, multiaccess protocols, probabilistic counting, selecting a leader, data compression, etc.). (C) 1998-Elsevier Science B.V. All rights reserved.