Approximating functions by their Poisson transform (Q1108734)

When analyzing the performance of hashing algorithms, it is usually assumed that the hash function distributes the n keys randomly over the m table positions. In this exact filling model, all the m n possible arrangements are equally likely. In some cases, the analysis under this model becomes too difficult, and a Poisson filling model is used instead. Under this model, the number of keys falling in a given table slot is assumed to follow a Poisson distribution with parameter \(\alpha\), independently of the number of keys falling elsewhere. The total number of keys, then, follows a Poisson distribution with parameter \(m\alpha\). The results obtained under the Poisson model are usually interpreted as an approximation of those one would obtain working under the exact model, with \(n=m\alpha\). \textit{G. H. Gonnet} and \textit{J. I. Munro} [J. Algorithms 5, 451-470 (1984; Zbl 0606.68058)] showed that the relationship between these two models is a deeper one: a Poisson result can be interpreted as a transform of the exact one, and this transform can be inverted to recover the exact result. They also point out that the intuitive notion of using a Poisson result to approximate the corresponding exact result can be formalized, by means of an asymptotic expansion. In this article, we provide a stronger version of their approximation theorem, together with a detailed proof. In particular, we find an explicit form for all the terms of the asymptotic expansion. We also prove that they satisfy a recurrence relation, which may be more useful for the actual computation of these terms.