# Asymptotic analysis of a class of functional equations and applications

P. J. Grabner; H. Prodinger; R. F. Tichy

Journal de théorie des nombres de Bordeaux (1993)

- Volume: 5, Issue: 2, page 365-381
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

topGrabner, P. J., Prodinger, H., and Tichy, R. F.. "Asymptotic analysis of a class of functional equations and applications." Journal de théorie des nombres de Bordeaux 5.2 (1993): 365-381. <http://eudml.org/doc/93588>.

@article{Grabner1993,

abstract = {Flajolet and Richmond have invented a method to solve a large class of divide-and-conquer recursions. The essential part of it is the asymptotic analysis of a certain generating function for $z \rightarrow \infty $ by means of the Mellin transform. In this paper this type of analysis is performed for a reasonably large class of generating functions fulfilling a functional equation with polynomial coefficients. As an application, the average life time of a party of $N$ people is computed, where each person advances one step or dies with equal probabilities, and an additional “killer” can kill at any level up to $d$ survivors, according to his probability distribution.},

author = {Grabner, P. J., Prodinger, H., Tichy, R. F.},

journal = {Journal de théorie des nombres de Bordeaux},

keywords = {recursion problems; analysis of algorithms; stochastic processes; average life problems; functional equation; asymptotic behaviour; generating functions; Mellin transform},

language = {eng},

number = {2},

pages = {365-381},

publisher = {Université Bordeaux I},

title = {Asymptotic analysis of a class of functional equations and applications},

url = {http://eudml.org/doc/93588},

volume = {5},

year = {1993},

}

TY - JOUR

AU - Grabner, P. J.

AU - Prodinger, H.

AU - Tichy, R. F.

TI - Asymptotic analysis of a class of functional equations and applications

JO - Journal de théorie des nombres de Bordeaux

PY - 1993

PB - Université Bordeaux I

VL - 5

IS - 2

SP - 365

EP - 381

AB - Flajolet and Richmond have invented a method to solve a large class of divide-and-conquer recursions. The essential part of it is the asymptotic analysis of a certain generating function for $z \rightarrow \infty $ by means of the Mellin transform. In this paper this type of analysis is performed for a reasonably large class of generating functions fulfilling a functional equation with polynomial coefficients. As an application, the average life time of a party of $N$ people is computed, where each person advances one step or dies with equal probabilities, and an additional “killer” can kill at any level up to $d$ survivors, according to his probability distribution.

LA - eng

KW - recursion problems; analysis of algorithms; stochastic processes; average life problems; functional equation; asymptotic behaviour; generating functions; Mellin transform

UR - http://eudml.org/doc/93588

ER -

## References

top- [1] T.M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1984. Zbl0335.10001MR434929
- [2] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger and R.F. Tichy, Mellin Transforms and Asymptotics: Digital Sums, Theoret. Comput. Sci. (to appear). Zbl0788.44004MR1256203
- [3] P. Flajolet and L.B. Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures and Algorithms3 (1992), 305-320. Zbl0758.60015MR1164843
- [4] P. Flajolet, M. Régnier and R. Sedgewick, Some Uses of the Mellin Integral Transform in the Analysis of Algorithms, Combinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), Springer, New York, 1985. Zbl0582.68015MR815343
- [5] P. Flajolet and A. Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math.3 (1990), 216-240. Zbl0712.05004MR1039294
- [6] P. Flajolet and J. Vitter, Average-Case Analysis of Algorithms and Data Structures, Handbook of Theoretical Computer Science Vol. A "Algorithms and Complexity"North-Holland, 1990, 431-524. Zbl0900.68251MR1127175
- [7] D.E. Knuth, The Art of Computer Science Vol. 3, Addison Wesley, Reading, MA, 1973. Zbl0302.68010
- [8] H.M. Mahmoud, Evolution of Random Search Trees, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1992. Zbl0762.68033MR1140708
- [9] J.-L. Mauclaire and L. Murata, On q-Additive Functions, II, Proc. Japan Acad.59 (1983), 441-444. Zbl0541.10040MR732606
- [10] H. Prodinger, How to, Advance on a Staircase by Coin Flippings,, Proceedings "Fibonacci Numbers and Applications 5" (1992) (to appear). Zbl0807.68056
- [11] E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press, 1927. Zbl45.0433.02JFM53.0180.04

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.