Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The growth of iterates of multivariate generating functions

Author: J. D. Biggins
Journal: Trans. Amer. Math. Soc. 360 (2008), 4305-4334
MSC (2000): Primary 39B12; Secondary 05A16, 60J80, 60F10
Published electronically: March 14, 2008
MathSciNet review: 2395174
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The vector-valued function $ m(\theta)$ of a $ p$-vector $ \theta$ has components $ m_1(\theta), m_2(\theta), \dots, m_p(\theta)$. For each $ i$, $ \exp(m_i(-\theta))$ is the (multivariate) Laplace transform of a discrete measure concentrated on $ [0,\infty)^p$ with only a finite number of atoms. The main objective is to give conditions for the functional iterates $ m^{(n)} $ of $ m$ to grow like $ \rho^n$ for a suitable $ \rho>1$. The initial stimulus was provided by results of Miller and O'Sullivan (1992) on enumeration issues in `context free languages', results which can be improved using the theory developed here. The theory also allows certain results in Jones (2004) on multitype branching to be proved under significantly weaker conditions.

References [Enhancements On Off] (What's this?)

  • 1. Tom M. Apostol, Mathematical analysis: A modern approach to advanced calculus, Addison-Wesley Publishing Company, Inc., Reading, Mass., 1957. MR 0087718 (19:398e)
  • 2. K. B. Athreya and P. E. Ney, Branching processes, Springer, New York, 1972. MR 0373040 (51:9242)
  • 3. K. B. Athreya and A. N. Vidyashankar, Large deviation rates for branching processes. II. The multitype case, Ann. Appl. Probab. 5 (1995), no. 2, 566-576. MR 1336883 (96k:60214)
  • 4. Martin T. Barlow and Edwin A. Perkins, Brownian motion on the Sierpiński gasket, Probab. Theory Related Fields 79 (1988), no. 4, 543-623. MR 966175 (89g:60241)
  • 5. J. D. Biggins and N. H. Bingham, Large deviations in the supercritical branching process, Adv. in Appl. Probab. 25 (1993), no. 4, 757-772. MR 1241927 (94i:60101)
  • 6. D. R. Grey, Nonnegative matrices, dynamic programming and a harvesting problem, J. Appl. Probab. 21 (1984), no. 4, 685-694. MR 766807 (86c:90126)
  • 7. T. E. Harris, Branching processes, Ann. Math. Statistics 19 (1948), 474-494. MR 0027465 (10:311b)
  • 8. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, 2nd edition, Addison-Wesley, Boston, 2001.
  • 9. Owen Dafydd Jones, Multivariate Böttcher equation for polynomials with nonnegative coefficients, Aequationes Math. 63 (2002), no. 3, 251-265. MR 1904719 (2003f:39064)
  • 10. -, Large deviations for supercritical multitype branching processes, J. Appl. Probab. 41 (2004), no. 3, 703-720. MR 2074818 (2005i:60169)
  • 11. Douglas P. Kennedy, On sets of countable non-negative matrices and Markov decision processes, Adv. Appl. Probab. 10 (1978), no. 3, 633-646. MR 0491767 (58:10966)
  • 12. Marek Kuczma, Bogdan Choczewski, and Roman Ger, Iterative functional equations, Encyclopedia of Mathematics and its Applications, vol. 32, Cambridge University Press, Cambridge, 1990. MR 1067720 (92f:39002)
  • 13. Takashi Kumagai, Estimates of transition densities for Brownian motion on nested fractals, Probab. Theory Related Fields 96 (1993), no. 2, 205-224. MR 1227032 (94e:60068)
  • 14. Peter Lancaster and Miron Tismenetsky, The theory of matrices, Computer Science and Applied Mathematics, Academic Press Inc., Orlando, FL, 1985. MR 792300 (87a:15001)
  • 15. Michael I. Miller and Joseph A. O'Sullivan, Entropies and combinatorics of random branching processes and context-free languages, IEEE Trans. Inform. Theory 38 (1992), no. 4, 1292-1310. MR 1168750 (93m:68103)
  • 16. R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683 (43:445)
  • 17. E. Seneta, Non-negative matrices, Halsted Press [A division of John Wiley & Sons], New York, 1973. MR 0389944 (52:10773)
  • 18. -, Nonnegative matrices and Markov chains, Springer Series in Statistics, Springer-Verlag, New York, 1981. MR 719544 (85i:60058)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 39B12, 05A16, 60J80, 60F10

Retrieve articles in all journals with MSC (2000): 39B12, 05A16, 60J80, 60F10

Additional Information

J. D. Biggins
Affiliation: Department of Probability and Statistics, The University of Sheffield, Sheffield, S3 7RH, United Kingdom

Keywords: Generating functions, iterates, maximum growth rate, non-negative matrices, functional iteration, multitype branching processes, enumeration
Received by editor(s): December 23, 2005
Received by editor(s) in revised form: August 17, 2006
Published electronically: March 14, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society