Polynomial tails of additive-type recursions

Abstract : Polynomial bounds and tail estimates are derived for additive random recursive sequences, which typically arise as functionals of recursive structures, of random trees, or in recursive algorithms. In particular they arise as parameters of divide and conquer type algorithms. We mainly focuss on polynomial tails that arise due to heavy tail bounds of the toll term and the starting distributions. Besides estimating the tail probability directly we use a modified version of a theorem from regular variation theory. This theorem states that upper bounds on the asymptotic tail probability can be derived from upper bounds of the Laplace―Stieltjes transforms near zero.
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.223-234, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01194690
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:51:12
Dernière modification le : mercredi 10 mai 2017 - 17:41:09
Document(s) archivé(s) le : mardi 8 décembre 2015 - 13:03:34

Fichier

dmAI0113.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01194690, version 1

Collections

Citation

Eva-Maria Schopp. Polynomial tails of additive-type recursions. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.223-234, 2008, DMTCS Proceedings. 〈hal-01194690〉

Partager

Métriques

Consultations de la notice

138

Téléchargements de fichiers

47