Generalized gamma approximation with rates for urns, walks and trees. (English) Zbl 1367.60019

Peköz, Erol A.; Röllin, Adrian; Ross, Nathan

Ann. Probab. 44, No. 3, 1776-1816 (2016).

A generalized gamma distribution \(\mathrm{GG}(\alpha,\beta)\) for \(\alpha,\beta>0\) arises as the distribution of \(X^{1/\beta}\) when the random variable \(X\) is gamma distributed with parameter \(\alpha\). The following Pólya type urn model is investigated. Let \(P^\ell_n(1,w)\) denote the distribution of the number of white balls in an urn after \(n\) draws when starting with one black and \(w\) white balls, and when after each draw the ball is replaced by two balls of the same color and after every \(\ell\)-th draw an additional black ball is added. The main result of the paper shows that the Kolmogorov distance of the distribution of \(N_n/\mu_n\) to \(\mathrm{GG}(w,\ell+1)\), where \(N_n\) is \(P^\ell_n(1,w)\)-distributed, can be bounded from above and below by a constant times \(n^{-\ell/(\ell+1)}\). The normalizing constants \(\mu_n\) depend on \(\mathbb E[N_n^{\ell+1}]\) and are explicitly given. The main technique of proof is an application of Stein’s method for log-concave densities (to which the generalized gamma densities belong) together with a characterization of generalized gamma distributions as fixed points of distributional transformations related to generalized equilibrium distributions. The result is a significant generalization to numerous previous works, e.g., for \(\ell=1\) it gives the rate of convergence in Example 3.1 of S. Janson [Probab. Theory Relat. Fields 134, No. 3, 417–452 (2006; Zbl 1112.60012)]. It can be directly applied to certain preferential attachment random graph models. Some of the urn models can be embedded into certain models for the size of random subtrees and into certain local times of random walks and random walk bridges as well as excursions and meanders of the latter. This also enables the authors to prove the convergence to generalized gamma distributions with optimal rates in these settings.

Reviewer: Peter Kern (Düsseldorf)

MSC:

60F05	Central limit and other weak theorems
60G50	Sums of independent random variables; random walks
60C05	Combinatorial probability
60D05	Geometric probability and stochastic geometry
60E10	Characteristic functions; other transforms
60K99	Special processes

Keywords:

generalized gamma distribution; Pólya urn model; Stein’s method; random walk; random binary trees; random plane trees; preferential attachment random graph

Citations:

Zbl 1112.60012

References:

[1]	Aldous, D. (1991). The continuum random tree. I. Ann. Probab. 19 1-28. · Zbl 0722.60013
[2]	Aldous, D. (1993). The continuum random tree. III. Ann. Probab. 21 248-289. · Zbl 0791.60009
[3]	Arratia, R., Goldstein, L. and Kochman, F. (2013). Size bias for one and all. Preprint. Available at . arXiv:1308.2729
[4]	Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Statist. 39 1801-1817. · Zbl 0185.46103
[5]	Bai, Z. D., Hu, F. and Zhang, L.-X. (2002). Gaussian approximation theorems for urn models and their applications. Ann. Appl. Probab. 12 1149-1173. · Zbl 1014.60025
[6]	Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223
[7]	Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford Studies in Probability 2 . Oxford Univ. Press, New York. · Zbl 0746.60002
[8]	Batir, N. (2008). Inequalities for the gamma function. Arch. Math. ( Basel ) 91 554-563. · Zbl 1165.33001
[9]	Bolthausen, E. (1982). Exact convergence rates in some martingale central limit theorems. Ann. Probab. 10 672-688. · Zbl 0494.60020
[10]	Borodin, A. N. (1987). On the distribution of random walk local time. Ann. Inst. Henri Poincaré Probab. Stat. 23 63-89. · Zbl 0608.60065
[11]	Borodin, A. N. (1989). Brownian local time. Uspekhi Mat. Nauk 44 7-48. · Zbl 0697.60080
[12]	Brown, M. (2006). Exploiting the waiting time paradox: Applications of the size-biasing transformation. Probab. Engrg. Inform. Sci. 20 195-230. · Zbl 1119.60073
[13]	Chatterjee, S. and Shao, Q.-M. (2011). Nonnormal approximation by Stein’s method of exchangeable pairs with application to the Curie-Weiss model. Ann. Appl. Probab. 21 464-483. · Zbl 1216.60018
[14]	Chen, L. H. Y., Goldstein, L. and Shao, Q.-M. (2011). Normal Approximation by Stein’s Method . Springer, Heidelberg. · Zbl 1213.62027
[15]	Chen, L. H. Y. and Shao, Q.-M. (2005). Stein’s method for normal approximation. In An Introduction to Stein’s Method. Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. 4 1-59. Singapore Univ. Press, Singapore.
[16]	Chung, K. L. (1976). Excursions in Brownian motion. Ark. Mat. 14 155-177. · Zbl 0356.60033
[17]	Chung, K. L. and Hunt, G. A. (1949). On the zeros of \(\sum^{n}_{1}\pm1\). Ann. of Math. (2) 50 385-400. · Zbl 0032.41701
[18]	Csáki, E. and Mohanty, S. G. (1981). Excursion and meander in random walk. Canad. J. Statist. 9 57-70. · Zbl 0478.60076
[19]	Döbler, C. (2012). Stein’s method of exchangeable pairs for absolutely continuous, univariate distributions with applications to the polya urn model.
[20]	Döbler, C. (2012). Stein’s method for the half-normal distribution with applications to limit theorems related to simple random walk. Preprint. Available at . arXiv:1303.4592
[21]	Dudley, R. M. (1968). Distances of probability measures and random variables. Ann. Math. Statist. 39 1563-1572. · Zbl 0169.20602
[22]	Durrett, R. T. and Iglehart, D. L. (1977). Functionals of Brownian meander and Brownian excursion. Ann. Probab. 5 130-135. · Zbl 0356.60035
[23]	Eggenberger, F. and Pólya, G. (1923). Über die Statistik verketteter Vorgänge. Z. angew. Math Mech. 3 279-289. · JFM 49.0382.01
[24]	Feller, W. (1968). An Introduction to Probability Theory and Its Applications. Vol. I , 3rd ed. Wiley, New York. · Zbl 0155.23101
[25]	Flajolet, P., Gabarró, J. and Pekari, H. (2005). Analytic urns. Ann. Probab. 33 1200-1233. · Zbl 1073.60007
[26]	Freedman, D. A. (1965). Bernard Friedman’s urn. Ann. Math. Statist 36 956-970. · Zbl 0138.12003
[27]	Friedman, B. (1949). A simple urn model. Comm. Pure Appl. Math. 2 59-70. · Zbl 0033.07101
[28]	Goldstein, L. and Reinert, G. (1997). Stein’s method and the zero bias transformation with application to simple random sampling. Ann. Appl. Probab. 7 935-952. · Zbl 0903.60019
[29]	Goldstein, L. and Reinert, G. (2005). Zero biasing in one and higher dimensions, and applications. In Stein’s Method and Applications. Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. 5 1-18. Singapore Univ. Press, Singapore.
[30]	Goldstein, L. and Xia, A. (2006). Zero biasing and a discrete central limit theorem. Ann. Probab. 34 1782-1806. · Zbl 1111.60015
[31]	Janson, S. (2006a). Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 417-452. · Zbl 1112.60012
[32]	Janson, S. (2006b). Random cutting and records in deterministic and random trees. Random Structures Algorithms 29 139-179. · Zbl 1120.05083
[33]	Janson, S. (2006c). Conditioned Galton-Watson trees do not grow. Technical report, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees Combinatorics and Probability. · Zbl 1190.05100
[34]	Janson, S. (2012). Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv. 9 103-252. · Zbl 1244.60013
[35]	Luk, H. M. (1994). Stein’s method for the Gamma distribution and related statistical applications. Ph.D. thesis, Univ. Southern California.
[36]	Marchal, P. (2003). Constructing a sequence of random walks strongly converging to Brownian motion. In Discrete Random Walks ( Paris , 2003). Discrete Math. Theor. Comput. Sci. Proc. , AC 181-190 (electronic). Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1034.60049
[37]	Meir, A. and Moon, J. W. (1978). On the altitude of nodes in random trees. Canad. J. Math. 30 997-1015. · Zbl 0394.05015
[38]	Nourdin, I. and Peccati, G. (2009). Stein’s method on Wiener chaos. Probab. Theory Related Fields 145 75-118. · Zbl 1175.60053
[39]	Pakes, A. G. and Khattree, R. (1992). Length-biasing, characterizations of laws and the moment problem. Austral. J. Statist. 34 307-322. · Zbl 0759.62005
[40]	Panholzer, A. (2004). The distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees. Random Structures Algorithms 25 179-207. · Zbl 1053.05113
[41]	Peköz, E. A. and Röllin, A. (2011). New rates for exponential approximation and the theorems of Rényi and Yaglom. Ann. Probab. 39 587-608. · Zbl 1213.60049
[42]	Peköz, E. A., Röllin, A. and Ross, N. (2013a). Degree asymptotics with rates for preferential attachment random graphs. Ann. Appl. Probab. 23 1188-1218. · Zbl 1271.60019
[43]	Peköz, E. A., Röllin, A. and Ross, N. (2013b). Total variation error bounds for geometric approximation. Bernoulli 19 610-632. · Zbl 1412.60012
[44]	Peköz, E., Röllin, A. and Ross, N. (2014). Joint degree distributions of preferential attachment random graphs. Preprint. Available at . arXiv:1402.4686
[45]	Pemantle, R. (2007). A survey of random processes with reinforcement. Probab. Surv. 4 1-79. · Zbl 1189.60138
[46]	Pitman, J. (1999). The distribution of local times of a Brownian bridge. In Séminaire de Probabilités , XXXIII. Lecture Notes in Math. 1709 388-394. Springer, Berlin. · Zbl 0945.60081
[47]	Pitman, J. (2006). Combinatorial Stochastic Processes. Lecture Notes in Math. 1875 . Springer, Berlin. · Zbl 1103.60004
[48]	Pitman, J. and Ross, N. (2012). Archimedes, Gauss, and Stein. Notices Amer. Math. Soc. 59 1416-1421. · Zbl 1284.60036
[49]	Raič, M. (2003). Normal approximation with Stein’s method. In Proceedings of the Seventh Young Statisticians Meeting . Metodoloski zvezki, Ljubljana.
[50]	Reinert, G. (2005). Three general approaches to Stein’s method. In An Introduction to Stein’s Method. Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. 4 183-221. Singapore Univ. Press, Singapore.
[51]	Rémy, J.-L. (1985). Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire. RAIRO Inform. Théor. 19 179-195. · Zbl 0565.05037
[52]	Röllin, A. and Ross, N. (2015). Local limit theorems via Landau-Kolmogorov inequalities. Bernoulli 21 851-880. · Zbl 1320.60065
[53]	Ross, N. (2011). Fundamentals of Stein’s method. Probab. Surv. 8 210-293. · Zbl 1245.60033
[54]	Ross, N. (2013). Power laws in preferential attachment graphs and Stein’s method for the negative binomial distribution. Adv. in Appl. Probab. 45 876-893. · Zbl 1273.05205
[55]	Ross, S. and Peköz, E. (2007). A second course in probability. , Boston, MA.
[56]	Stein, C. (1986). Approximate Computation of Expectations. Institute of Mathematical Statistics Lecture Notes-Monograph Series 7 . IMS, Hayward, CA. · Zbl 0721.60016
[57]	Vervaat, W. (1979). A relation between Brownian bridge and Brownian excursion. Ann. Probab. 7 143-149. · Zbl 0392.60058
[58]	Wendel, J. G. (1948). Note on the gamma function. Amer. Math. Monthly 55 563-564.
[59]	Zhang, L.-X., Hu, F. and Cheung, S. H. (2006). Asymptotic theorems of sequential estimation-adjusted urn models. Ann. Appl. Probab. 16 340-369. · Zbl 1090.62084
[60]	Zhang, L.-X., Hu, F., Cheung, S. H. and Chan, W. S. (2011). Immigrated urn models-theoretical properties and applications. Ann. Statist. 39 643-671. · Zbl 1226.60012