Analytical depoissonization and its applications

DOI10.1016/S0304-3975(97)00167-9zbMath0902.68087OpenAlexW2085901659MaRDI QIDQ1129001

Wojciech Szpankowski, Philippe Jacquet

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00167-9

zbMATH Keywords

limiting distributions saddle point method digital trees Cauchy integral formula poissonization depoissonization analysis of algorithms and data structures analytical combinatorics Mellin transform of complex variable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Moments of distributions related to digital expansions, On the mixtures of length-biased Weibull distributions for loss severity modeling, Distances in random digital search trees, A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence, The Depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace, Average distances on self-similar sets and higher order average distances of self-similar measures, Moments of discrete measures with dense jumps induced by \(\beta\)-expansions, Node profiles of symmetric digital search trees: Concentration properties, A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries, On the variety of shapes in digital trees, Asymptotic normality for the size of graph tries built from M-ary tree labelings, Local limit theorems for finite and infinite urn models, Poisson limit theorems for the Robinson-Schensted correspondence and for the multi-line Hammersley process, Expectations on fractal sets, Asymptotic expectation of protected node profile in random digital search trees, Asymptotic expansions relating to the distribution of the length of longest increasing subsequences, Towards a Realistic Analysis of Some Popular Sorting Algorithms, Profiles of PATRICIA tries, Joint string complexity for Markov sources: small data matters, An analytic approach to the asymptotic variance of trie statistics and related structures, Average-Case Analysis of Cousins in m-ary Tries, Order statistics of the generalised multinomial measure, On tries, contention trees and their analysis, Optimal online selection of a monotone subsequence: a central limit theorem, Gaps in samples of geometric random variables, Analysis of swaps in radix selection, On gaps and unoccupied urns in sequences of geometrically distributed random variables, The expected profile of digital search trees, On the Stack-Size of General Tries, D?E?K=(1000)8, Size and path length of Patricia tries: Dynamical sources context, Distinctness of compositions of an integer: A probabilistic analysis, The oscillatory distribution of distances in random tries, Asymptotic laws for compositions derived from transformed subordinators, Gap-free compositions and gap-free samples of geometric random variables, From coin tossing to rock-paper-scissors and beyond: a log-exp gap theorem for selecting a leader, Dependence between path-length and size in random digital trees, ON CLIMBING TRIES, Asymptotics of Plancherel measures for symmetric groups, Profile of Tries, Words with a generalized restricted growth property, Asymmetric Rényi Problem, On the shape of the fringe of various types of random trees, Imbalance in random digital trees, On sequential selection and a first passage problem for the Poisson process, On the variance of the number of occupied boxes, Singularity analysis and asymptotics of Bernoulli sums, Limit distribution of distances in biased random tries, On an asymptotic series of Ramanujan, A binomial splitting process in connection with corner parking problems, The Wiener Index of Random Digital Trees

Cites Work