Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-14T07:43:20.062Z Has data issue: false hasContentIssue false
  • English
  • Français

The Class of Tenable Zero-Balanced Pólya Urn Schemes: Characterization and Gaussian Phases

Part of:Combinatorial probabilityStochastic processesCombinatoricsLimit theorems

Published online by Cambridge University Press:  04 January 2016

Sanaa Kholfi and
Hosam M. Mahmoud
Sanaa Kholfi*
Affiliation:
The George Washington University
Hosam M. Mahmoud*
Affiliation:
The George Washington University
*
∗ Postal address: Department of Statistics, The George Washington University, Washington, DC 20052, USA.
∗ Postal address: Department of Statistics, The George Washington University, Washington, DC 20052, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study a class of tenable, irreducible, nondegenerate zero-balanced Pólya urn schemes. We give a full characterization of the class by sufficient and necessary conditions. Only forms with a certain cyclic structure in their replacement matrix are admissible. The scheme has a steady state into proportions governed by the principal (left) eigenvector of the average replacement matrix. We study the gradual change for any such urn containing n → ∞ balls from the initial condition to the steady state. We look at the status of an urn starting with an asymptotically positive proportion of each color after j n draws. We identify three phases of j n : the growing sublinear, the linear, and the superlinear. In the growing sublinear phase the number of balls of different colors has an asymptotic joint multivariate normal distribution, with mean and covariance structure that are influenced by the initial conditions. In the linear phase a different multivariate normal distribution kicks in, in which the influence of the initial conditions is attenuated. The steady state is not a good approximation until a certain superlinear amount of time has elapsed. We give interpretations for how the results in different phases conjoin at the ‘seam lines’. In fact, these Gaussian phases are all manifestations of one master theorem. The results are obtained via multivariate martingale theory. We conclude with some illustrating examples.

Keywords

UrnPólya urncombinatorial probabilityphase transitionmultivariate martingale

MSC classification

Primary:60C05: Combinatorial probability60F05: Central limit and other weak theorems05A05: Permutations, words, matrices
Secondary:60G42: Martingales with discrete parameter

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 44 , Issue 3 , September 2012, pp. 702 - 728
Copyright
© Applied Probability Trust 

References

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.Google Scholar
Bagchi, A. and Pal, A. K. (1985). Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures. SIAM J. Algebraic Discrete Meth. 6, 394–405.Google Scholar
Balaji, S., Mahmoud, H. and Zhang, T. (2010). Phases in the diffusion of gases via the Ehrenfest urn model. J. Appl. Prob. 47, 841–855.Google Scholar
Bernstein, S. (1940). Sur un problème du schéme des urnes à composition variable. C. R. (Doklady) Acad. Sci. URSS 28, 5–7.Google Scholar
Chauvin, B., Poyanne, N. and Sahnoun, R. (2011). Limit distributions for large Pólya urns. Ann. Appl. Prob. 21, 1–32.Google Scholar
Chern, H.-H. and Hwang, H.-K. (2001). Phase changes in random m-ary search trees and generalized quicksort. Random Structures Algorithms 19, 316–358.Google Scholar
Eggenberger, F. and Pólya, G. (1923). Über die statistik verketteter vorgäge. Z. Angew. Math. Mech. 3, 279–289.Google Scholar
Ehrenfest, P. and Ehrenfest, T. (1907). Über zwei bekannte einwände gegen das Boltzmannsche H-theorem. Phys. Z. 8, 311–314.Google Scholar
Flajolet, P., Dumas, P. and Puyhaubert, V. (2006). Some exactly solvable models of urn process theory. In 4th Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (Discrete Math. Theoret. Comput. Sci. Proc. AG), Assoc. Discrete Math. Theoret. Comput. Sci. Nancy, pp. 59–118.Google Scholar
Flajolet, P., Gabarró, J. and Pekari, H. (2005). Analytic urns. Ann. Prob. 33, 1200–1233.Google Scholar
Freedman, D. A. (1965). Bernard Friedman's urn. Ann. Math. Statist. 36, 956–970.CrossRefGoogle Scholar
Friedman, B. (1949). A simple urn model. Commun. Pure Appl. Math. 2, 59–70.Google Scholar
Gouet, R. (1989). A martingale approach to strong convergence in a generalized Pólya-Eggenberger urn model. Statist. Prob. Lett. 8, 225–228.Google Scholar
Gouet, R. (1993). Martingale functional central limit theorems for a generalized Pólya urn. Ann. Prob. 21, 1624–1639.CrossRefGoogle Scholar
Gouet, R. (1997). Strong convergence of proportions in a multicolor Pólya urn. J. Appl. Prob. 34, 426–435.Google Scholar
Hall, P. and Heyde, C. (1980). Martingale Limit Theory and Its Applications. Academic Press, New York.Google Scholar
Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stoch. Process. Appl. 110, 177–245.Google Scholar
Janson, S. (2005). Asymptotic degree distribution in random recursive trees. Random Structures Algorithms 26, 69–83.CrossRefGoogle Scholar
Janson, S. (2005). Limit theorems for triangular urn schemes. Prob. Theory Relat. Fields 134, 417–452.Google Scholar
Johnson, N. and Kotz, S. (1977). Urn models and Their Application. John Wiley, New York.Google Scholar
Karlin, S. and McGregor, J. (1965). Ehrenfest urn models. J. Appl. Prob. 2, 352–376.Google Scholar
Kholfi, S. and Mahmoud, H. M. (2012). The class of tenable zero-balanced Pólya urns with an initially dominant subset of colors. Statist. Prob. Lett. 82, 49–57.Google Scholar
Kotz, S. and Balakrishnan, N. (1997). Advances in urn models during the past two decades. In Advances in Combinatorial Methods and Applications to Probability and Statistics. Birkhäuser, Boston, MA, pp. 203–257.Google Scholar
Mahmoud, H. M. (1998). On rotations in fringe-balanced binary trees. Inform. Process. Lett. 65, 41–46.Google Scholar
Mahmoud, H. M. and Smythe, R. T. (1991). On the distribution of leaves in rooted subtrees of recursive trees. Ann. Appl. Prob. 1, 406–418.Google Scholar
Mahmoud, H. M. and Smythe, R. T. (1992). Asymptotic Joint normality of outdegrees of nodes in random recursive trees. Random Structures Algorithms 3, 255–266.Google Scholar
Mahmoud, H. M. and Smythe, R. T. (1995). Probabilistic analysis of bucket recursive trees. Theoret. Comput. Sci. 144, 221–249.Google Scholar
Mahmoud, H. (2003). Pólya urn models and connections to random trees: a review. J. Iranian Statist. Soc. 2, 53–114.Google Scholar
Mahmoud, H. M. (2008). Pólya Urn Models. Chapman & Hall/CRC, Boca Raton, FL.Google Scholar
Mahmoud, H. M., Smythe, R. T. and Szymański, J. (1993). On the structure of plane-oriented recursive trees and their branches. Random Structures Algorithms 4, 151–176.Google Scholar
McKenzie, A. and Steele, M. (2000). Distributions of cherries for two models of trees. Math. Biosci. 164, 81–92.Google Scholar
Pólya, G. (1931). Sur quelques points de la théorie des probabilités. Ann. Inst. H. Poincaré 1, 117–161.Google Scholar
Savkevich, V. (1940). Sur le schéma des urnes à composition variable. C. R. (Doklady) Acad. Sci. URSS 28, 8–12.Google Scholar
Smythe, R. T. (1996). Central limit theorems for urn models. Stoch. Process. Appl. 65, 115–137.Google Scholar