Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, September 7, 2015 - 12:51:12 PM
Last modification on : Wednesday, May 10, 2017 - 5:41:09 PM
Long-term archiving on: : Tuesday, December 8, 2015 - 1:03:34 PM


Publisher files allowed on an open archive




Eva-Maria Schopp. Polynomial tails of additive-type recursions. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. pp.223-234, ⟨10.46298/dmtcs.3566⟩. ⟨hal-01194690⟩



Record views


Files downloads