Geodesic
Polynomial tails of additive-type recursions
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (2008).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2008_special_254_a12,
     author = {Schopp, Eva-Maria},
     title = {Polynomial tails of additive-type recursions},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science},
     year = {2008},
     doi = {10.46298/dmtcs.3566},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3566/}
}
TY  - JOUR
AU  - Schopp, Eva-Maria
TI  - Polynomial tails of additive-type recursions
JO  - Discrete mathematics & theoretical computer science
PY  - 2008
VL  - DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3566/
DO  - 10.46298/dmtcs.3566
LA  - en
ID  - DMTCS_2008_special_254_a12
ER  - 
%0 Journal Article
%A Schopp, Eva-Maria
%T Polynomial tails of additive-type recursions
%J Discrete mathematics & theoretical computer science
%D 2008
%V DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3566/
%R 10.46298/dmtcs.3566
%G en
%F DMTCS_2008_special_254_a12
Schopp, Eva-Maria. Polynomial tails of additive-type recursions. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (2008). doi : 10.46298/dmtcs.3566. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3566/

Cité par Sources :