License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.35
URN: urn:nbn:de:0030-drops-89284
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8928/
Vallée, Brigitte
The Depoissonisation Quintet: Rice-Poisson-Mellin-Newton-Laplace
Abstract
This paper is devoted to the Depoissonisation process which is central in various analyses of the AofA domain. We first recall in Section 1 the two possible paths that may be used in this process, namely the Depoissonisation path and the Rice path. The two paths are rarely described for themselves in the literature, and general methodological results are often difficult to isolate amongst particular results that are more directed towards various applications. The main results for the Depoissonisation path are scattered in at least five papers, with a chronological order which does not correspond to the logical order of the method. The Rice path is also almost always presented with a strong focus towards possible applications. It is often very easy to apply, but it needs a tameness condition, which appears a priori to be quite restrictive, and is not deeply studied in the literature. This explains why the Rice path is very often undervalued.
Second, the two paths are not precisely compared, and the situation creates various "feelings": some people see the tools that are used in the two paths as quite different, and strongly prefer one of the two paths; some others think the two paths are almost the same, with just a change of vocabulary. It is thus useful to compare the two paths and the tools they use. This will be done in Sections 2 and 3. We also "follow" this comparison on a precise problem, related to the analysis of tries, introduced in Section 1.7.
The paper also exhibits in Section 4 a new framework, of practical use, where the tameness condition of Rice path is proven to hold. This approach, perhaps of independent interest, deals with the shifting of sequences and then the inverse Laplace transform, which does not seem of classical use in this context. It performs very simple computations. This adds a new method to the Depoissonisation context and explains the title of the paper. We then conclude that the Rice path is both of easy and practical use: even though (much?) less general than the Depoissonisation path, it is easier to apply.
BibTeX - Entry
@InProceedings{valle:LIPIcs:2018:8928,
author = {Brigitte Vall{\'e}e},
title = {{The Depoissonisation Quintet: Rice-Poisson-Mellin-Newton-Laplace}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {35:1--35:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-078-1},
ISSN = {1868-8969},
year = {2018},
volume = {110},
editor = {James Allen Fill and Mark Daniel Ward},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8928},
URN = {urn:nbn:de:0030-drops-89284},
doi = {10.4230/LIPIcs.AofA.2018.35},
annote = {Keywords: Analysis of Algorithms, Poisson model, Mellin transform, Rice integral, Laplace transform, Newton interpolation, Depoissonisation, sources, trie struc}
}
|
Keywords: |
|
Analysis of Algorithms, Poisson model, Mellin transform, Rice integral, Laplace transform, Newton interpolation, Depoissonisation, sources, trie struc |
|
Collection: |
|
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
18.06.2018 |
