# 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
Full Text:
##### References:
  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  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  Athreya, K. B. and Ney, P. E. (1972). Branching Processes . Springer, New York. · Zbl 0259.60002  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  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  Berger, M. (1977). Géométrie 1 . Actions de Groupes , Espaces Affines et Projectifs . CEDIC, Paris. [English translation published in Universitext . Springer, Berlin (1987).]  Bergeron, F., Labelle, G. and Leroux, P. (1998). Combinatorial Species and Tree-Like Structures . Cambridge Univ. Press. · Zbl 0888.05001  Billingsley, P. (1986). Probability and Measure , 2nd ed. Wiley, New York. · Zbl 0649.60001  Chandrasekharan, K. (1985). Elliptic Functions . Springer, Berlin. · Zbl 0575.33001  den Hollander, F. (2000). Large Deviations . Amer. Math. Soc., Providence, RI. · Zbl 0949.60001  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  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  Flajolet, P. and Sedgewick, R. (2003). Analytic Combinatorics . (Book in preparation; individual chapters are available electronically.) · Zbl 1165.05001  Friedman, B. (1949). A simple urn model. Comm. Pure Appl. Math. 2 59–70. · Zbl 0033.07101 · doi:10.1002/cpa.3160020103  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  Goulden, I. P. and Jackson, D. M. (1983). Combinatorial Enumeration . Wiley, New York. · Zbl 0519.05001  Graham, R. L., Knuth, D. E. and Patashnik, O. (1989). Concrete Mathematics . Addison–Wesley, Reading, MA. · Zbl 0668.00003  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  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  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  Janson, S. (2005). Limit theorems for triangular urn schemes. Probab. Theory Related Fields. · Zbl 1112.60012  Johnson, N. L. and Kotz, S. (1977). Urn Models and Their Application . Wiley, New York. · Zbl 0352.60001  Knuth, D. E. (1998). The Art of Computer Programming , 2nd ed. Addison–Wesley, Reading, MA. · Zbl 0895.65001  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  Lang, S. (1982). Introduction to Algebraic and Abelian Functions , 2nd ed. Springer, New York. · Zbl 0513.14024  Lukacs, E. (1970). Characteristic Functions . Griffin, London. · Zbl 0201.20404  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  Mahmoud, H. M. (1992). Evolution of Random Search Trees . Wiley, New York. · Zbl 0762.68033  Nehari, Z. (1975). Conformal Mapping . Dover, New York. (Reprinting of the 1952 edition.) · Zbl 0048.31503  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  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  Rota, G.-C. (1975). Finite Operator Calculus . Academic Press, New York. · Zbl 0328.05007  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  Taylor, M. E. (1996). Partial Differential Equations 1 . Springer, New York. · Zbl 0869.35002  Whittaker, E. T. and Watson, G. N. (1927). A Course of Modern Analysis , 4th ed. Cambridge Univ. Press. (Reprinted 1973.) · Zbl 0951.30002  Yao, A. C. C. (1978). On random 2–3 trees. Acta Inform. 9 159–170. · Zbl 0369.05024 · doi:10.1007/BF00289075  Yoshida, M. (1997). Hypergeometric Functions , My Love . Vieweg, Braunschweig. · Zbl 0889.33008  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.