×

zbMATH — the first resource for mathematics

Functional limit theorems for multitype branching processes and generalized Pólya urns. (English) Zbl 1075.60109
Summary: A functional limit theorem is proved for multitype continuous time Markov branching processes. As consequences, we obtain limit theorems for the branching process stopped by some stopping rule, for example when the total number of particles reaches a given level. Using the Athreya-Karlin embedding, these results yield asymptotic results for generalized Pólya urns. We investigate such results in detail and obtain explicit formulas for the asymptotic variances and covariances. The general formulas involve integrals of matrix function; we show how they can be evaluated and simplified in important special cases. We also consider the numbers of drawn balls of different types and functional limit theorems for the urns. We illustrate our results by some examples, including several applications to random trees where our theorems and variance formulas give simple proofs of some known results; we also give some new results.

MSC:
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60F17 Functional limit theorems; invariance principles
Keywords:
urn models
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldous, D.; Flannery, B.; Palacios, J.L., Two applications of urn processes, Probab. eng. inform. sci., 2, 293-307, (1988) · Zbl 1134.68592
[2] Asmussen, S., Almost sure behavior of linear functionals of supercritical branching processes, Trans. amer. math. soc., 231, 1, 233-248, (1977) · Zbl 0376.60083
[3] Athreya, K.B., Some results on multitype continuous time Markov branching processes, Ann. math. statist., 39, 347-357, (1968) · Zbl 0169.49202
[4] Athreya, K.B., Limit theorems for multitype continuous time Markov branching processes. I. the case of an eigenvector linear functional, Z. wahrsch. verw. gebiete, 12, 320-332, (1969) · Zbl 0181.21101
[5] Athreya, K.B., Limit theorems for multitype continuous time Markov branching processes. II. the case of an arbitrary linear functional, Z. wahrsch. verw. gebiete, 13, 204-214, (1969) · Zbl 0181.21102
[6] Athreya, K.B.; Karlin, S., Limit theorems for the split times of branching processes, J. math. mech., 17, 257-277, (1967) · Zbl 0171.15801
[7] Athreya, K.B.; Karlin, S., Embedding of urn schemes into continuous time Markov branching processes and related limit theorems, Ann. math. statist., 39, 1801-1817, (1968) · Zbl 0185.46103
[8] Athreya, K.B.; Ney, P.E., Branching processes, (1972), Springer Berlin · Zbl 0259.60002
[9] Bagchi, A.; Pal, A.K., Asymptotic normality in the generalized Pólya – eggenberger urn model, with an application to computer data structures, SIAM J. algebraic discrete methods, 6, 3, 394-405, (1985) · Zbl 0568.60010
[10] Bai, Z.D.; Hu, F., Asymptotic theorems for urn models with nonhomogeneous generating matrices, Stochastic process. appl., 80, 1, 87-101, (1999) · Zbl 0954.62014
[11] Bai, Z.D.; Hu, F.; Zhang, L.-X., Gaussian approximation theorems for urn models and their applications, Ann. appl. probab., 12, 4, 1149-1173, (2002) · Zbl 1014.60025
[12] Bernstein, S., Nouvelles applications des grandeurs aléatoires presqu’indépendantes, Izv. akad. nauk SSSR ser. mat., 4, 137-150, (1940), (in Russian) · JFM 66.0614.01
[13] Bernstein, S., Sur un problème du schéma des urnes à composition variable, C. R. (doklady) acad. sci. URSS (N.S.), 28, 5-7, (1940) · JFM 66.0615.01
[14] Billingsley, P., Convergence of probability measures, (1968), Wiley New York · Zbl 0172.21201
[15] Chauvin, B., Pouyanne, N., 2004. m-ary search trees when m⩾ 27: a strong asymptotics for the space requirements. Random Struct. Algorithms, to appear. Available from http://www.math.uvsq.fr/ chauvin/publis.html. · Zbl 1037.60027
[16] Chern, H.-H.; Hwang, H.-K., Phase changes in random m-ary search trees and generalized quicksort, Random struct. algorithms, 19, 3-4, 316-358, (2001) · Zbl 0990.68052
[17] Eggenberger, F.; Pólya, G., Über die statistik verketteter vorgänge, Zeitschrift angew. math. mech., 3, 279-289, (1923) · JFM 49.0382.01
[18] Fill, J., Kapur, N., 2003. Transfer theorems and asymptotic distributional results for m-ary search trees. Preprint. Available from http://www.mts.jhu.edu/ fill/. · Zbl 1101.68018
[19] Flajolet, P., Gabarró, J., Pekari, H., 2003. Analytic urns. Preprint.
[20] Freedman, D.A., Bernard Friedman’s urn, Ann. math. statist., 36, 956-970, (1965) · Zbl 0138.12003
[21] Friedman, B., A simple urn model, Comm. pure appl. math., 2, 59-70, (1949) · Zbl 0033.07101
[22] Gouet, R., Martingale functional central limit theorems for a generalized Pólya urn, Ann. probab., 21, 3, 1624-1639, (1993) · Zbl 0788.60044
[23] Gut, A., Stopped random walks, (1988), Springer New York · Zbl 0634.60061
[24] Gut, A.; Janson, S., The limiting behaviour of certain stopped sums and some applications, Scand. J. statist., 10, 281-292, (1983) · Zbl 0529.60019
[25] Hwang, H.-K., Second phase changes in random m-ary search trees and generalized quicksortconvergence rates, Ann. probab., 31, 2, 609-629, (2003) · Zbl 1021.60020
[26] Jacod, J.; Shiryaev, A.N., Limit theorems for stochastic processes, (1987), Springer Berlin · Zbl 0635.60021
[27] Janson, S., Limit theorems for certain branching random walks on compact groups and homogeneous spaces, Ann. probab., 11, 909-930, (1983) · Zbl 0544.60022
[28] Janson, S., A functional limit theorem for random graphs with applications to subgraph count statistics, Random struct. algorithms, 1, 15-37, (1990) · Zbl 0708.05052
[29] Janson, S., Orthogonal decompositions and functional limit theorems for random graph statistics, Mem. amer. math. soc., Vol. 111(534), (1994), American Mathematical Society Providence, RI · Zbl 0810.05001
[30] Janson, S., Gaussian Hilbert spaces, (1997), Cambridge University Press Cambridge · Zbl 0887.60009
[31] Janson, S., 2003. Asymptotic degree distribution in random recursive trees. Preprint. Available from http://www.math.uu.se/ svante/. · Zbl 1059.05094
[32] Johnson, N.L.; Kotz, S., Urn models and their application, (1977), Wiley New York
[33] Kallenberg, O., Foundations of modern probability, (2002), Springer New York · Zbl 0996.60001
[34] Karlin, S., A first course in stochastic processes, (1969), Academic Press New York
[35] Kesten, H.; Stigum, B.P., Additional limit theorems for indecomposable multidimensional galton – watson processes, Ann. math. statist., 37, 1463-1481, (1966) · Zbl 0203.17402
[36] Kesten, H.; Stigum, B.P., Limit theorems for decomposable multi-dimensional galton – watson processes, J. math. anal. appl., 17, 309-338, (1967) · Zbl 0203.17501
[37] Kotz, S.; Mahmoud, H.; Robert, P., On generalized Pólya urn models, Statist. probab. lett., 49, 2, 163-173, (2000) · Zbl 0965.60027
[38] Lew, W.; Mahmoud, H.M., The joint distribution of elastic buckets in multiway search trees, SIAM J. comput., 23, 5, 1050-1074, (1994) · Zbl 0820.68037
[39] Lindvall, T., Weak convergence of probability measures and random functions in the function space D(0,∞), J. appl. probab., 10, 109-121, (1973) · Zbl 0258.60008
[40] Mahmoud, H.M., Evolution of random search trees, (1992), Wiley New York · Zbl 0762.68033
[41] Mahmoud, H.M., On rotations in fringe-balanced binary trees, Inform. process. lett., 65, 1, 41-46, (1998) · Zbl 1339.68057
[42] Mahmoud, H.M., 2000. Urn models evolving by drawing multisets of balls. Preprint.
[43] Mahmoud, H.M., The size of random bucket trees via urn models, Acta inform., 38, 11-12, 813-838, (2002) · Zbl 1034.68121
[44] Mahmoud, H.M.; Pittel, B., Analysis of the space of search trees under the random insertion algorithm, J. algorithms, 10, 1, 52-75, (1989) · Zbl 0685.68060
[45] Mahmoud, H.M.; Smythe, R.T., Asymptotic joint normality of outdegrees of nodes in random recursive trees, Random struct. algorithms, 3, 3, 255-266, (1992) · Zbl 0767.05086
[46] Mahmoud, H.M.; Smythe, R.T.; Szymański, J., On the structure of random plane-oriented recursive trees and their branches, Random struct. algorithms, 4, 2, 151-176, (1993) · Zbl 0773.05040
[47] Meir, A.; Moon, J.W., Recursive trees with no nodes of out-degree one, Congr. numer., 66, 49-62, (1988) · Zbl 0724.05016
[48] Nomizu, K., Fundamentals of linear algebra, (1979), Chelsea Publishing Co New York · Zbl 0148.01601
[49] Pólya, G., Sur quelques points de la théorie des probabilités, Ann. inst. Poincaré, 1, 117-161, (1931) · JFM 57.0610.02
[50] Protter, P., Stochastic integration and differential equations. A new approach, Applications of mathematics, Vol. 21, (1990), Springer Berlin · Zbl 0694.60047
[51] Rachev, S.T., Probability metrics and the stability of stochastic models, (1991), Wiley Chichester, UK · Zbl 0744.60004
[52] Savkevitch, V., Sur le schéma des urnes à composition variable, C. R. (doklady) acad. sci. URSS (N.S.), 28, 8-12, (1940) · Zbl 0024.05202
[53] Seneta, E., Nonnegative matrices and Markov chains, (1981), Springer New York · Zbl 0471.60001
[54] Smythe, R.T., Central limit theorems for urn models, Stochastic process. appl., 65, 1, 115-137, (1996) · Zbl 0889.60013
[55] Smythe, R.T.; Rosenberger, W.F., Play-the-winner designs, generalized Pólya urns, and Markov branching processes, (), 13-22 · Zbl 0949.62578
[56] Tsukiji, T.; Mahmoud, H., A limit law for outputs in random recursive circuits, Algorithmica, 31, 3, 403-412, (2001) · Zbl 0989.68107
[57] Wei, L.J.; Durham, S., The randomized play-the-winner rule in medical trials, J. amer. statist. assoc., 73, 364, 840-843, (1978) · Zbl 0391.62076
[58] Wei, L.J.; Smythe, R.T.; Lin, D.Y.; Park, T.S., Statistical inference with data-dependent treatment allocation rules, J. amer. statist. assoc., 85, 409, 156-162, (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.