Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-09T21:53:53.320Z Has data issue: false hasContentIssue false
  • English
  • Français

Pólya Urns Via the Contraction Method

Published online by Cambridge University Press:  01 September 2014

MARGARETE KNAPE  and
RALPH NEININGER
MARGARETE KNAPE
Affiliation:
Institute for Mathematics, J. W. Goethe University, 60054 Frankfurt a.M., Germany (e-mail: [email protected], [email protected])
RALPH NEININGER
Affiliation:
Institute for Mathematics, J. W. Goethe University, 60054 Frankfurt a.M., Germany (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We propose an approach to analysing the asymptotic behaviour of Pólya urns based on the contraction method. For this, a new combinatorial discrete-time embedding of the evolution of the urn into random rooted trees is developed. A decomposition of these trees leads to a system of recursive distributional equations which capture the distributions of the numbers of balls of each colour. Ideas from the contraction method are used to study such systems of recursive distributional equations asymptotically. We apply our approach to a couple of concrete Pólya urns that lead to limit laws with normal limit distributions, with non-normal limit distributions and with asymptotic periodic distributional behaviour.

Keywords

Primary 60C05Secondary 60F0560J0568Q25
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 6: Honouring the Memory of Philippe Flajolet - Part 2 , November 2014 , pp. 1148 - 1186
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Athreya, K. B. (1969) On a characteristic property of Pólya'surn. Studia Sci. Math. Hungar. 4 31–35.Google Scholar
[2]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.CrossRefGoogle Scholar
[3]Bagchi, A. and Pal, A. K. (1985) Asymptotic normality in the generalized Polya–Eggenberger urn model, with an application to computer data structures. SIAM J. Algebraic Discrete Methods 6 394–405.CrossRefGoogle Scholar
[4]Bai, Z. D. and Hu, F. (1999) Asymptotic theorems for urn models with nonhomogeneous generating matrices. Stochastic Process. Appl. 80 87–101.CrossRefGoogle Scholar
[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.CrossRefGoogle Scholar
[6]Bickel, P. J. and Freedman, D. A. (1981) Some asymptotic theory for the bootstrap. Ann. Statist. 9 1196–1217.CrossRefGoogle Scholar
[7]Chauvin, B., Liu, Q. and Pouyanne, N. (2012) Support and density of the limit m-ary search tree distribution. In 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms: AofA'12, DMTCS Proc. AQ 2012, pp. 191–200.Google Scholar
[8]Chauvin, B., Liu, Q. and Pouyanne, N. (2014) Limit distributions for multitype branching processes of m-ary search trees. Ann. IHP. 50 628–654.Google Scholar
[9]Chauvin, B., Mailler, C. and Pouyanne, N. (2013) Smoothing equations for large Pólya urns. arXiv:1302.1412Google Scholar
[10]Chauvin, B., Pouyanne, N. and Sahnoun, R. (2011) Limit distributions for large Pólya urns. Ann. Appl. Probab. 21 1–32.CrossRefGoogle Scholar
[11]Drmota, M., Janson, S. and Neininger, R. (2008) A functional limit theorem for the profile of search trees. Ann. Appl. Probab. 18 288–333.CrossRefGoogle Scholar
[12]Fill, J. A. and Kapur, N. (2004) The space requirement of m-ary search trees: Distributional asymptotics for m ⋛ 27. Invited paper, Proc. 7th Iranian Statistical Conference, 2004. www.ams.jhu.edu/~fill/papers/periodic.pdfGoogle Scholar
[13]Flajolet, P., Gabarró, J. and Pekari, H. (2005) Analytic urns. Ann. Probab. 33 1200–1233.CrossRefGoogle Scholar
[14]Hwang, H.-K. and Neininger, R. (2002) Phase change of limit laws in the quicksort recurrence under varying toll functions. SIAM J. Comput. 31 1687–1722.CrossRefGoogle Scholar
[15]Janson, S. (1983) Limit theorems for certain branching random walks on compact groups and homogeneous spaces. Ann. Probab. 11 909–930.CrossRefGoogle Scholar
[16]Janson, S. (2004) Functional limit theorem for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 177–245.CrossRefGoogle Scholar
[17]Janson, S. (2005) Limit theorems for triangular urn schemes. Probab. Theory Rel. Fields 134 417–452.CrossRefGoogle Scholar
[18]Janson, S. (2006) Congruence properties of depths in some random trees. Alea 1 347–366.Google Scholar
[19]Janson, S. (2010) Moments of gamma type and the Brownian supremum process area. Probab. Surv. 7 1–52.Google Scholar
[20]Janson, S. and Kaijser, S. (2012) Higher moments of Banach space valued random variables. Mem. Amer. Math. Soc., to appear.Google Scholar
[21]Janson, S. and Neininger, R. (2008) The size of random fragmentation trees. Probab. Theory Rel. Fields 142 399–442.CrossRefGoogle Scholar
[22]Johnson, N. L. and Kotz, S. (1977) Urn Models and their Application: An Approach to Modern Discrete Probability Theory, Wiley Series in Probability and Mathematical Statistics, Wiley.CrossRefGoogle Scholar
[23]Knape, M. (2013) Pólya urns via the contraction method. PhD dissertation. Submitted at the J. W. Goethe University, Frankfurt am Main, April 2013. urn:nbn:de:hebis:30:3-322846Google Scholar
[24]Kotz, S., Mahmoud, H. M. and Robert, P. (2000) On generalized Pólya urn models. Statist. Probab. Lett. 49 163–173.CrossRefGoogle Scholar
[25]Leckey, K., Neininger, R. and Szpankowski, W. (2013) Towards more realistic probabilistic models for data structures: The external path length in tries under the Markov model. In Proc. ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 877–886.CrossRefGoogle Scholar
[26]Mahmoud, H. M. (2009) Pólya Urn Models, Texts in Statistical Science Series, CRC Press.Google Scholar
[27]Matthews, P. C. and Rosenberger, W. F. (1997) Variance in randomized play-the-winner clinical trials. Statist. Probab. Lett. 35 233–240.CrossRefGoogle Scholar
[28]Neininger, R. (2001) On a multivariate contraction method for random recursive structures with applications to quicksort. Random Struct. Alg. 19 498–524.CrossRefGoogle Scholar
[29]Neininger, R. and Rüschendorf, L. (2004) A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14 378–418.CrossRefGoogle Scholar
[30]Neininger, R. and Sulzbach, H. (2012) On a functional contraction method. Ann. Probab., to appear. arXiv:1202.1370Google Scholar
[31]Pouyanne, N. (2005) Classification of large Pólya–Eggenberger urns with regard to their asymptotics. In 2005 International Conference on Analysis of Algorithms, DMTCS Proc. AD, pp. 275–285.Google Scholar
[32]Pouyanne, N. (2008) An algebraic approach to Pólya processes. Ann. Inst. Henri Poincaré Probab. Stat. 44 293–323.CrossRefGoogle Scholar
[33]Rachev, S. T. and Rüschendorf, L. (1995) Probability metrics and recursive algorithms. Adv. Appl. Probab. 27 770–799.CrossRefGoogle Scholar
[34]Rösler, U. (1991) A limit theorem for ‘Quicksort’. RAIRO Inform. Théor. Appl. 25 85–100.CrossRefGoogle Scholar
[35]Smythe, R. T. (1996) Central limit theorems for urn models. Stochastic Process. Appl. 65 115–137.CrossRefGoogle Scholar
[36]Smythe, R. T. and Rosenberger, W. F. (1995) Play-the-winner designs, generalized Pólya urns, and Markov branching processes. In Adaptive Designs (Flournoy, N. and Rosenberger, W. F., eds), Vol. 25 of IMS Lecture Notes Monograph Series, Institute of Mathematical Statistics, pp. 13–22.CrossRefGoogle Scholar
[37]Wei, L. J. and Durham, S. (1978). The randomized play-the-winner rule in medical trials. J. Amer. Statist. Assoc. 73 840–843.CrossRefGoogle Scholar
[38]Wei, L. J., Smythe, R. T., Lin, D. Y. and Park, T. S. (1990) Statistical inference with data-dependent treatment allocation rules. J. Amer. Statist. Assoc. 85 156–162.CrossRefGoogle Scholar
[39]Zolotarev, V. M. (1976) Approximation of the distributions of sums of independent random variables with values in infinite-dimensional spaces (Russian). Teor. Veroyatnost. i Primenen. 21 741–758. Erratum ibid. 22 (1977), 901. English translation in Theory Probab. Appl. 21 721–737; ibid. 22 881.Google Scholar
[40]Zolotarev, V. M. (1977) Ideal metrics in the problem of approximating the distributions of sums of independent random variables (Russian). Teor. Veroyatnost. i Primenen. 22 449–465. English translation in Theory Probab. Appl. 22 433–449.Google Scholar