The growth of iterates of multivariate generating functions
HTML articles powered by AMS MathViewer
- by J. D. Biggins PDF
- Trans. Amer. Math. Soc. 360 (2008), 4305-4334 Request permission
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
- Tom M. Apostol, Mathematical analysis: a modern approach to advanced calculus, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1957. MR 0087718
- Krishna B. Athreya and Peter E. Ney, Branching processes, Die Grundlehren der mathematischen Wissenschaften, Band 196, Springer-Verlag, New York-Heidelberg, 1972. MR 0373040
- 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
- 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, DOI 10.1007/BF00318785
- 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, DOI 10.2307/1427790
- D. R. Grey, Nonnegative matrices, dynamic programming and a harvesting problem, J. Appl. Probab. 21 (1984), no. 4, 685–694. MR 766807, DOI 10.2307/3213687
- T. E. Harris, Branching processes, Ann. Math. Statistics 19 (1948), 474–494. MR 27465, DOI 10.1214/aoms/1177730146
- John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, 2nd edition, Addison-Wesley, Boston, 2001.
- Owen Dafydd Jones, Multivariate Böttcher equation for polynomials with nonnegative coefficients, Aequationes Math. 63 (2002), no. 3, 251–265. MR 1904719, DOI 10.1007/s00010-002-8023-7
- Owen Dafydd Jones, Large deviations for supercritical multitype branching processes, J. Appl. Probab. 41 (2004), no. 3, 703–720. MR 2074818, DOI 10.1017/s0021900200020490
- Douglas P. Kennedy, On sets of countable non-negative matrices and Markov decision processes, Adv. in Appl. Probab. 10 (1978), no. 3, 633–646. MR 491767, DOI 10.2307/1426638
- 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, DOI 10.1017/CBO9781139086639
- Takashi Kumagai, Estimates of transition densities for Brownian motion on nested fractals, Probab. Theory Related Fields 96 (1993), no. 2, 205–224. MR 1227032, DOI 10.1007/BF01192133
- Peter Lancaster and Miron Tismenetsky, The theory of matrices, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1985. MR 792300
- 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, DOI 10.1109/18.144710
- R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
- E. Seneta, Non-negative matrices, Halsted Press [John Wiley & Sons], New York, 1973. An introduction to theory and applications. MR 0389944
- E. Seneta, Nonnegative matrices and Markov chains, 2nd ed., Springer Series in Statistics, Springer-Verlag, New York, 1981. MR 719544, DOI 10.1007/0-387-32792-4
Additional Information
- J. D. Biggins
- Affiliation: Department of Probability and Statistics, The University of Sheffield, Sheffield, S3 7RH, United Kingdom
- Email: J.Biggins@sheffield.ac.uk
- Received by editor(s): December 23, 2005
- Received by editor(s) in revised form: August 17, 2006
- Published electronically: March 14, 2008
- © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 360 (2008), 4305-4334
- MSC (2000): Primary 39B12; Secondary 05A16, 60J80, 60F10
- DOI: https://doi.org/10.1090/S0002-9947-08-04408-5
- MathSciNet review: 2395174