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

Abstract

top
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 → ∞ 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.

How to cite

top

Grabner, 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. [1] T.M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1984. Zbl0335.10001MR434929
  2. [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. [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. [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. [5] P. Flajolet and A. Odlyzko, Singularity Analysis of Generating Functions, SIAM J. Disc. Math.3 (1990), 216-240. Zbl0712.05004MR1039294
  6. [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. [7] D.E. Knuth, The Art of Computer Science Vol. 3, Addison Wesley, Reading, MA, 1973. Zbl0302.68010
  8. [8] H.M. Mahmoud, Evolution of Random Search Trees, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1992. Zbl0762.68033MR1140708
  9. [9] J.-L. Mauclaire and L. Murata, On q-Additive Functions, II, Proc. Japan Acad.59 (1983), 441-444. Zbl0541.10040MR732606
  10. [10] H. Prodinger, How to, Advance on a Staircase by Coin Flippings,, Proceedings "Fibonacci Numbers and Applications 5" (1992) (to appear). Zbl0807.68056
  11. [11] E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press, 1927. Zbl45.0433.02JFM53.0180.04

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.