zbMATH — the first resource for mathematics

Smoothing equations for large Pólya urns. (English) Zbl 1358.60010
Summary: Consider a balanced nontriangular two-color Pólya-Eggenberger urn process, assumed to be large, which means that the ratio \(\sigma\) of the replacement matrix eigenvalues satisfies \(1/2<\sigma<1\). The composition vector of both discrete-time and continuous-time models admits a drift which is carried by the principal direction of the replacement matrix. In the second principal direction, this random vector admits also an almost sure asymptotics and a real-valued limit random variable arises, named \(W^{\mathrm{DT}}\) in discrete time and \(W^{\mathrm{CT}}\) in continuous time. The paper deals with the distributions of both \(W\). Appearing as martingale limits, known to be nonnormal, these laws remain up to now rather mysterious. Exploiting the underlying tree structure of the urn process, we show that \(W^{\mathrm{DT}}\) and \(W^{\mathrm{CT}}\) are the unique solutions of two distributional systems in some suitable spaces of integrable probability measures. These systems are natural extensions of distributional equations that already appeared in famous algorithmical problems like Quicksort analysis. Existence and unicity of the solutions of the systems are obtained by means of contracting smoothing transforms. Via the equation systems, we find upper bounds for the moments of \(W^{\mathrm{DT}}\) and \(W^{\mathrm{CT}}\) and we show that the laws of \(W^{\mathrm{DT}}\) and \(W^{\mathrm{CT}}\) are moment determined. We also prove that \(W^{\mathrm{DT}}\) is supported by the whole real line, its exponential moment generating series has an infinite radius of convergence and \(W^{\mathrm{DT}}\) admits a continuous density (\(W^{\mathrm{CT}}\) was already known to have a density, infinitely differentiable on \(\mathbb R\setminus\{0\}\) and not bounded at the origin).

60C05 Combinatorial probability
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
Full Text: DOI arXiv
[1] Aldous, D; Bandyopadhyay, A, A survey of MAX-type recursive distributional equations, Ann. Appl. Probab., 15, 1047-1110, (2005) · Zbl 1105.60012
[2] Alsmeyer, G; Biggins, JD; Meiners, M, The functional equation of the smoothing transform, Ann. Probab., 40, 2069-2105, (2012) · Zbl 1266.39022
[3] Athreya, KB, On a characteristic property of Pólya’s urn, Studia Sci. Math. Hung., 4, 31-35, (1969) · Zbl 0185.47301
[4] Athreya, KB; Karlin, S, Embedding of urn schemes into continuous time Markov branching processes and related limit theorems, Ann. Math. Stat., 39, 1801-1817, (1968) · Zbl 0185.46103
[5] Athreya, K.B., Ney, P.: Branching Processes. Springer, Berlin (1972) · Zbl 0259.60002
[6] Barral, J, Moments, continuité, et analyse multifractale des cascades multiplicatives de Mandelbrot, Probab. Theory Rel. Fields, 113, 535-569, (1999) · Zbl 0936.60045
[7] Bertoin, J.: Random Fragmentation and Coagulation Processes, Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2006) · Zbl 1107.60002
[8] Biggins, JD; Kyprianou, A, Fixed points of the smoothing transform: the boundary case, Electron. J. Probab., 10, 609-631, (2005) · Zbl 1110.60081
[9] Blackwell, D; Kendall, DG, The martin boundary for Pólya’s urn and an application to stochastic population growth, J. Appl. Probab., 1, 284-296, (1964) · Zbl 0129.10702
[10] Chaumont, L., Yor, M.: Exercices in Probability. Cambridge University Press, Cambridge (2003) · Zbl 1180.60002
[11] Chauvin, B., Liu, Q., Pouyanne, N.: Support and density of the limit \(m\)-ary search trees distribution. In: 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA’12), DMTCS, pp. 191-200 (2012) · Zbl 1296.68031
[12] Chauvin, B., Liu, Q., Pouyanne, N.: Limit distributions for multitype branching processes of \(m\)-ary search trees. Ann. Inst. Henri Poincaré, to appear (2013) · Zbl 1318.60013
[13] Chauvin, B; Pouyanne, N; Sahnoun, R, Limit distributions for large Pólya urns, Ann. Appl. Probab., 21, 1-32, (2011) · Zbl 1220.60006
[14] Dudley, R.M.: Real Analysis and Probability. Cambridge University Press, Cambridge (2002) · Zbl 1023.60001
[15] Durrett, R; Liggett, T, Fixed points of the smoothing transformation, Z. Wahrsch. verw. Gebeite, 64, 275-301, (1983) · Zbl 0506.60097
[16] Fill, J.A., Kapur, N.: The space requirement of \(m\)-ary search trees: distributional asymptotics for \( m \ge 27\). In: Proceedings of the 7th Iranian Conference, page arXiv:math.PR/0405144 (2004)
[17] Flajolet, J; Gabarró, P; Pekari, H, Analytic urns, Ann. Probab., 33, 1200-1233, (2005) · Zbl 1073.60007
[18] Flajolet, P., Dumas, P., Puyhaubert, V.: Some exactly solvable models of urn process theory. DMTCS Proc. AG, 59-118 (2006) · Zbl 1193.60011
[19] Janson, S, Functional limit theorem for multitype branching processes and generalized Pólya urns, Stoch. Process. Appl., 110, 177-245, (2004) · Zbl 1075.60109
[20] Johnson, N.L., Kotz, S.: Urn Models and Their Application. Wiley, New York (1977) · Zbl 0352.60001
[21] Kahane, J-P; Peyrière, J, Sur certaines martingales de benoit Mandelbrot, Adv. Math., 22, 131-145, (1976) · Zbl 0349.60051
[22] Knape, M., Neininger, R.: Pólya urns via the contraction method. arXiv:1301.3404v2 [math.PR], (2013)
[23] Liu, Q, Fixed points of a generalized smoothing transformation and applications to branching random walks, Adv. Appl. Prob., 30, 85-112, (1998) · Zbl 0909.60075
[24] Liu, Q, Asymptotic properties of supercritical age-dependent branching processes and homogeneous branching random walks, Stoch. Process. Appl., 82, 61-87, (1999) · Zbl 0997.60091
[25] Liu, Q, Asymptotic properties and absolute continuity of laws stable by random weighted Mean, Stoch. Process. Appl., 95, 83-107, (2001) · Zbl 1058.60068
[26] Mahmoud, H.M.: Pólya Urn Models. CRC Press, Boca Raton (2008) · Zbl 1149.60005
[27] Mandelbrot, B.: Multiplications aléatoires itérées et distributions invariantes par moyenne pondérée aléatoire. C. R. Acad. Sci. Paris Ser. A 278, 289-292 (1974) · Zbl 0276.60096
[28] Neininger, R; Rüschendorf, L, A general limit theorem for recursive algorithms and combinatorial structures, Ann. Appl. Probab., 14, 378-418, (2004) · Zbl 1041.60024
[29] Neininger, R., Rüschendorf, L.: Analysis of Algorithms by the Contraction Method: Additive and Max-Recursive Sequences. In: Deuschel, J.-D., Greven, A. (eds.) Interacting Stochastic Systems, pp. 435-450. Springer (2005) · Zbl 1090.68124
[30] Neininger, R; Rüschendorf, L, A survey of multivariate aspects of the contraction method, Discrete Math. Theor. Comput. Sci., 8, 31-56, (2006) · Zbl 1157.60307
[31] Pólya, G, Sur quelques points de la théorie des probabilités, Ann. Inst. Henri Poincaré, 1, 117-161, (1931) · JFM 57.0610.02
[32] Pouyanne, N, An algebraic approach to Pólya processes, Ann. Inst. Henri Poincaré, 44, 293-323, (2008) · Zbl 1185.60029
[33] Rösler, U, A fixed point theorem for distributions, Stoch. Process. Appl., 42, 195-214, (1992) · Zbl 0761.60015
[34] Rösler, U; Rüschendorf, L, The contraction method for recursive algorithms, Algorithmica, 29, 3-33, (2001) · Zbl 0967.68166
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.