Approximating functions by their Poisson transform
type: Item
instance of: scholarly article
title: Approximating functions by their Poisson transform
zbMATH Open document ID: 0654.65012
DOI: 10.1016/0020-0190(86)90111-0
author: Patricio V. Poblete
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65D15
zbMATH DE Number: 4068148
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: Poisson transform
zbMATH Keywords: hashing
zbMATH Keywords: exact filling model
zbMATH Keywords: Poisson filling model
MaRDI profile type: Publication
full work available at URL: 0020-0190(86)90111-0
OpenAlex ID: W2005879515
description: scientific article; zbMATH DE number 4068148