Analytic urns (Q1781182): Difference between revisions

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.