×

zbMATH — the first resource for mathematics

Analytic urns. (English) Zbl 1073.60007
The article considers the “generalized” (or “extended) Pólya-Eggenberger urn model with two types of balls, say “black” (B) and “white” (W). At time \(0\) the urn contains \(a_0\) B-balls and \(b_0\) W-balls. At time \(n\) a ball in the urn is randomly chosen and its color is observed (thus the ball is placed back in the urn). If it is B, then \(\alpha_{BB}\) B-balls and \(\alpha_{BW}\) W-balls are inserted, while if the chosen ball is W, then \(\alpha_{WB}\) B-balls and \(\alpha_{WW}\) W-balls are inserted. This “urn evolution” rule is conveniently represented by the matrix \(M = \{ (\alpha_{BB}, \alpha_{BW}); (\alpha_{WB}, \alpha_{WW}) \}\). It is, furthermore, assumed that the urn is “balanced”, namely the total number of balls inserted (during each step) is always \(s\). Thus, \(s = \alpha_{BB} + \alpha_{BW} = \alpha_{WB} + \alpha_{WW}\), and the total number of balls in the urn at time \(n\) is \(t_0 + s n\), where \(t_0 = a_0 + b_0\) is the initial size. The authors focus attention in the case involving subtraction (although, as they explain, their method can be applied to all other balanced cases), namely when \(\alpha_{BB} = -a\), \(\alpha_{BW} = a + s\), \(\alpha_{WB} = b + s\), and \(\alpha_{WW} = -b\), where \(a,b > 0\), and \(s > 0\). In order for the urn not to be blocked by an infeasible request, one needs to impose the so-called “tenability” conditions: (\({\text T}_0\)) \(a\) divides \(a_0\) and \(b\) divides \(b_0\); (\({\text T}_1\)) \(a\) divides \(b + s\) and \(b\) divides \(a + s\). For \(n = 0, 1, 2, \dots\) let \(X_n\) be the number of B-balls at time \(n\), \(p_n(u) = E[u^{X_n}]\) its PGF (probability generating function), and \(h_n(u) = \sum_{k \geq 0} c(k; n) u^k\) the counting generating function (meaning that \(c(k; n)\) is the number of ways of getting exactly \(k\) B-balls in the urn at time \(n\) – in fact, for each \(n\), the polynomials \(p_n(u)\) and \(h_n(u)\) differ by a simple constant factor).
The authors introduce the exponential generating function of \(h_n(u)\), namely the BGF (bivariate generating function) \(H(z, u) = \sum_{n \geq 0} h_n(u) z^n / n!\) and notice that \(H(z, 1) = (1 - s z)^{-t_0/s}\). Then, after a series of elegant steps, where certain partial differential operators are interpreted combinatorially, they arrive to the “fundamental equation” (14) for \(H(z, u)\), which is a first-order linear PDE. Thus, the old method of characteristics gives \(H(z, u)\) explicitly in terms of the Abelian integral \(I(u) = \int u^{a - 1} v^{- a - b}\) over the (complex) “Fermat curve” \(u^h + v^h = 1\), where \(h = a + b + s\) (Theorem 1), and it turns out that the major characteristics of the associated urn model are determined by the (global) analytic function \(I(u)\). The authors, then, determine the fundamental polygon of \(I(u)\), which is a quadrilateral, the “elementary kite”. In the last part of the paper, the form of \(H(z, u)\) is used in order to obtain some deep probabilistic properties of the urn model (e.g. speed of convergence to the Gaussian limit, as \(n \to \infty\), large deviations, etc). Naturally, particular attention is given to the special case where \(H(z, u)\) can be expressed in terms of elliptic functions. The authors show that there are exactly six (non-equivalent) “elliptic” urn models. The paper ends with some final comments and plans of future research.

MSC:
60C05 Combinatorial probability
33E05 Elliptic functions and integrals
41A60 Asymptotic approximations, asymptotic expansions (steepest descent, etc.)
60K99 Special processes
60Fxx Limit theorems in probability theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aldous, D. (1991). Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 228–266. · Zbl 0733.60016 · doi:10.1214/aoap/1177005936
[2] Aldous, D., Flannery, B. and Palacios, J. L. (1988). Two applications of urn processes—The fringe analysis of trees and the simulation of quasi-stationary distributions of Markov chains. Probab. Engrg. Inform. Sci. 2 293–307. · Zbl 1134.68592 · doi:10.1017/S026996480000084X
[3] Athreya, K. B. and Ney, P. E. (1972). Branching Processes . Springer, New York. · Zbl 0259.60002
[4] 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 Methods 6 394–405. · Zbl 0568.60010 · doi:10.1137/0606041
[5] Bender, E. A. (1973). Central and local limit theorems applied to asymptotic enumeration. J. Combin. Theory 15 91–111. · Zbl 0242.05006 · doi:10.1016/0097-3165(73)90038-1
[6] Berger, M. (1977). Géométrie 1 . Actions de Groupes , Espaces Affines et Projectifs . CEDIC, Paris. [English translation published in Universitext . Springer, Berlin (1987).]
[7] Bergeron, F., Labelle, G. and Leroux, P. (1998). Combinatorial Species and Tree-Like Structures . Cambridge Univ. Press. · Zbl 0888.05001
[8] Billingsley, P. (1986). Probability and Measure , 2nd ed. Wiley, New York. · Zbl 0649.60001
[9] Chandrasekharan, K. (1985). Elliptic Functions . Springer, Berlin. · Zbl 0575.33001
[10] den Hollander, F. (2000). Large Deviations . Amer. Math. Soc., Providence, RI. · Zbl 0949.60001
[11] Eisenbarth, B., Ziviani, N., Gonnet, G. H., Mehlhorn, K. and Wood, D. (1982). The theory of fringe analysis and its application to 2–3 trees and B-trees. Inform. and Control 55 125–174. · Zbl 0561.68050 · doi:10.1016/S0019-9958(82)90534-4
[12] Flajolet, P. and Odlyzko, A. M. (1990). Singularity analysis of generating functions. SIAM J. Algebraic Discrete Methods 3 216–240. · Zbl 0712.05004 · doi:10.1137/0403019
[13] Flajolet, P. and Sedgewick, R. (2003). Analytic Combinatorics . (Book in preparation; individual chapters are available electronically.) · Zbl 1165.05001
[14] Friedman, B. (1949). A simple urn model. Comm. Pure Appl. Math. 2 59–70. · Zbl 0033.07101 · doi:10.1002/cpa.3160020103
[15] Gouet, R. (1993). Martingale functional central limit theorems for a generalized Pólya urn. Ann. Probab. 21 1624–1639. JSTOR: · Zbl 0788.60044 · doi:10.1214/aop/1176989134 · links.jstor.org
[16] Goulden, I. P. and Jackson, D. M. (1983). Combinatorial Enumeration . Wiley, New York. · Zbl 0519.05001
[17] Graham, R. L., Knuth, D. E. and Patashnik, O. (1989). Concrete Mathematics . Addison–Wesley, Reading, MA. · Zbl 0668.00003
[18] Hwang, H.-K. (1996). Large deviations for combinatorial distributions. I. Central limit theorems. Ann. Appl. Probab. 6 297–319. · Zbl 0863.60013 · doi:10.1214/aoap/1034968075
[19] Hwang, H.-K. (1998). On convergence rates in the central limit theorems for combinatorial structures. European J. Combin. 19 329–343. · Zbl 0906.60024 · doi:10.1006/eujc.1997.0179
[20] Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 177–245. · Zbl 1075.60109 · doi:10.1016/j.spa.2003.12.002
[21] Janson, S. (2005). Limit theorems for triangular urn schemes. Probab. Theory Related Fields. · Zbl 1112.60012
[22] Johnson, N. L. and Kotz, S. (1977). Urn Models and Their Application . Wiley, New York. · Zbl 0352.60001
[23] Knuth, D. E. (1998). The Art of Computer Programming , 2nd ed. Addison–Wesley, Reading, MA. · Zbl 0895.65001
[24] Kotz, S., Mahmoud, H. and Robert, P. (2000). On generalized Pólya urn models. Statist. Probab. Lett. 49 163–173. · Zbl 0965.60027 · doi:10.1016/S0167-7152(00)00045-6
[25] Lang, S. (1982). Introduction to Algebraic and Abelian Functions , 2nd ed. Springer, New York. · Zbl 0513.14024
[26] Lukacs, E. (1970). Characteristic Functions . Griffin, London. · Zbl 0201.20404
[27] Mahmoud, H. (1998). On rotations in fringe-balanced binary trees. Inform. Process. Lett. 65 41–46. · Zbl 1339.68057 · doi:10.1016/S0020-0190(97)00184-1
[28] Mahmoud, H. M. (1992). Evolution of Random Search Trees . Wiley, New York. · Zbl 0762.68033
[29] Nehari, Z. (1975). Conformal Mapping . Dover, New York. (Reprinting of the 1952 edition.) · Zbl 0048.31503
[30] Odlyzko, A. M. (1995). Asymptotic enumeration methods. In Handbook of Combinatorics 2 (R. Graham, M. Grötschel and L. Lovász, eds.) 1063–1229. North-Holland, Amsterdam. · Zbl 0845.05005
[31] Panholzer, A. and Prodinger, H. (1998). An analytic approach for the analysis of rotations in fringe-balanced binary search trees. Ann. Combin. 2 173–184. · Zbl 0936.68110 · doi:10.1007/BF01608487
[32] Rota, G.-C. (1975). Finite Operator Calculus . Academic Press, New York. · Zbl 0328.05007
[33] Smythe, R. T. (1996). Central limit theorems for urn models. Stochastic Process. Appl. 65 115–137. · Zbl 0889.60013 · doi:10.1016/S0304-4149(96)00094-4
[34] Taylor, M. E. (1996). Partial Differential Equations 1 . Springer, New York. · Zbl 0869.35002
[35] Whittaker, E. T. and Watson, G. N. (1927). A Course of Modern Analysis , 4th ed. Cambridge Univ. Press. (Reprinted 1973.) · Zbl 0951.30002
[36] Yao, A. C. C. (1978). On random 2–3 trees. Acta Inform. 9 159–170. · Zbl 0369.05024 · doi:10.1007/BF00289075
[37] Yoshida, M. (1997). Hypergeometric Functions , My Love . Vieweg, Braunschweig. · Zbl 0889.33008
[38] Zwillinger, D. (1989). Handbook of Differential Equations . Academic Press, New York. · Zbl 0678.34001
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.