Mellin Transforms and Asymptotics: Harmonic Sums

Philippe Flajolet 1 Xavier Gourdon 1 Philippe Dumas 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : This survey presents a unified and essentially self-contained approach to the asymptotic analysis of a large class of sums that arise in combinatorial mathematics, discrete probabilistic models, and the average case analysis of algorithms. It relies on the Mellin transform, a close relative of the integral transforms of Laplace and Fourier. The method applies to harmonic sums that are superpositions of rather arbitrary ``harmonics'' of a common base function. Its principle is a precise correspondence between individual terms in the asymptotic expansion of an original function and singularities of the transformed function. The main applications discussed are in the area of digital data structures, probabilistic algorithms, and communication theory.
Type de document :
Rapport
[Research Report] RR-2369, INRIA. 1994
Liste complète des métadonnées

https://hal.inria.fr/inria-00074307
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:01:31
Dernière modification le : samedi 17 septembre 2016 - 01:35:21
Document(s) archivé(s) le : mardi 12 avril 2011 - 16:29:33

Fichiers

Identifiants

  • HAL Id : inria-00074307, version 1

Collections

Citation

Philippe Flajolet, Xavier Gourdon, Philippe Dumas. Mellin Transforms and Asymptotics: Harmonic Sums. [Research Report] RR-2369, INRIA. 1994. 〈inria-00074307〉

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

83