zbMATH — the first resource for mathematics

Limiting distributions for a class of diminishing urn models. (English) Zbl 1300.60023
Let \(m, n, a, b, c, d, p\) be fixed integers \(\geq 0\). An urn contains \(md\) white balls and \(na\) black balls. A ball is chosen at random from the urn, its color noted, and it is returned to the urn. Also, if the color is white, \(a\) white balls and \(b\) black balls are added to the urn; similarly, if the color is black, \(c\) white balls and \(d\) black balls are added to the urn. This process is continued. This model is denoted by \(M=\left(\begin{matrix} a &b \\ c & d\end{matrix}\right)\).
The present paper studies the model \(M=\left(\begin{matrix} -a&0\\ c& -d\end{matrix}\right)\), where \(a\geq 1\), \(d\geq 1\), and \(c=pa\) (negative value denotes removal of balls as opposed to adding balls) and the distribution of the r.v. \(X_{md,na}\) representing the number of white balls in the urn when all the black balls have been removed. As motivation for this study, the paper cites the pills problem [D. Knuth, “Problem E3429: big pills and little pills”, Am. Math. Monthly 98, No. 3, 264 (1991), http://www.jstor.org/stable/2325034; “Solution: E3429”, Am. Math. Monthly 99, No. 7, 684 (1992), http://www.jstor.org/stable/2325015] and sampling without replacement defined by the model \(M=\left(\begin{matrix} -a & 0\\ 0& -d\end{matrix}\right)\).
For convenience, denote by \(Y\) the r.v. \(X_{md,na}\). Also, for reference we include here (a) the Kumaraswamy r.v. \(K(r, s)\) with distribution function \(F(x)=1-(1-xr)s\), \(x \in [0, 1]\), (b) the Weibull r.v. \(W(r, s)\) with distribution function \(F(x)=1-\exp[-(x/s)r]\), \(x\geq 0\). Note that \(W(1,s)\) is the exponential r.v. \(E(s)\) and \(W(2, s)\) is the Raleigh r.v. \(R(s)\).
The following limiting distributions are the major results in the paper.
Theorem 1. \((c=0)\). For the model \(M=\left(\begin{matrix} -a& 0\\ 0& -d\end{matrix}\right)\),
for fixed \(m\) and \(n\to\infty\), \(Y/na\) converges in distribution to \(K(d/a, m)\);
for \(m, n \to \infty\) such that \(m^{a/d} = o(n)\), \(m^{a/d} Y/na\) converges in distribution to \(W(d/a, 1)\);
for \(m, n \to \infty\) such that \(n\sim pm^{a/d}\), where \(p >0\), \(Y/a\) converges in distribution to \(U\), where the moment generating function of \(U\) is given by \(\varphi (p (\exp(z)-1)\), with \(\varphi(z)\) being the moment generating function of the Weibull distribution;
for \(m\to \infty\) and \(n=o(m^{a/d} )\), \(Y\) converges in distribution to the point mass at \(0\).
Theorem 2. (\(c>0\) and \(a\leq d\)). For the model \(M=\left(\begin{matrix}-a& 0\\ c& -d\end{matrix}\right)\),
for fixed \(m\) and \(n\to \infty\), \(Y/na\) converges in distribution to \(K(d/a, m)\);
for \(m\to \infty\) and arbitrary \(n\), \(Y/g(m,n)\) converges in distribution to \(W(d/a, 1)\).
The normalizing constants \(g(m,n)\) are explicitly given in the paper. Note that the above Theorem 2 contains the known special cases \(a=c=d=1\) and \(a=c=1\) and \(d=2\) [H. K. Hwang, M. Kuba and A. Panholzer, “Analysis of some exactly solvable diminishing urn models”, in: Proc. 19th Int. Conf. Formal Power Series and Algebraic Combinatorics, Nankai University, Tianjin (2007), http://www.fpsac.cn/PDF-Proc./Posters/43.pdf].
Theorem 3. (\(c>0\) and \(a>d\)). For the model \(M=\left(\begin{matrix}-a& 0\\ c& -d\end{matrix}\right)\),
for fixed \(m\) and \(n\to \infty\), \(Y/na\) converges in distribution to \(K(d/a, m)\);
for \(m, n \to \infty\) such that \(m^{a/d} = o(n)\), the moments of the r.v. \(m^{a/d} Y/na\) converge to the moments of \(W(d/a, 1)\);
for \(m, n \to \infty\) such that \(n \sim pm^{a/d}\), where \(p>0\), the moments of \(Y\) converge to a complicated expression which is explicitly given in the paper;
for \(m\to \infty\) and \(n=o(m^{a/d})\), the moments of \(Y\) converge to a less complicated expression which is explicitly given in the paper.
Detailed derivations of the structure of the moments of the r.v.’s mentioned in the theorems above are obtained in Section 4 of the paper; these are too technical to reproduce here.
The paper ends with a section on the study of a biased Pólya-Eggenberger urn model.

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
Full Text: DOI arXiv
[1] Biane, P., Pitman, J. and Yor, M. (2001). Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions. Bull. Amer. Math. Soc. 38, 435-465. · Zbl 1040.11061 · doi:10.1090/S0273-0979-01-00912-0
[2] Brennan, C. A. C. and Prodinger, H. (2003). The pills problem revisited. Quaest. Math. 26, 427-439. · Zbl 1054.05004 · doi:10.2989/16073600309486073
[3] Crane, E. \et (2011). The simple harmonic urn. To appear in Ann. Prob . · Zbl 1262.60070
[4] Davis, B. (1990). Reinforced random walk. Prob. Theory Relat. Fields 84, 203-229. · Zbl 0665.60077 · doi:10.1007/BF01197845
[5] Flajolet, P., Dumas, P. and Puyhaubert, V. (2006). Some exactly solvable models of urn process theory. In Proc. 4th Coll. Math. Comput. Sci. (Discrete Math. Comput. Sci. AG ), ed. P. Chassaing, pp. 59-118. · Zbl 1193.60011 · www.dmtcs.org
[6] Flajolet, P., Gabarró, J. and Pekari, H. (2005). Analytic urns. Ann. Prob. 33, 1200-1233, · Zbl 1073.60007 · doi:10.1214/009117905000000026
[7] Graham, R. L., Knuth, D. E. and Patashnik, O. (1994). Concrete Mathematics . Addison-Wesley, Reading, MA. · Zbl 0836.00001
[8] Greene, D. H. and Knuth, D. E. (1982). Mathematics for the Analysis of Algorithms . Birkhäuser, Boston, MA. · Zbl 1151.68750
[9] Hwang, H. K., Kuba, M. and Panholzer, A. (2007). Analysis of some exactly solvable diminishing urn models. In Proc. 19th Internat. Conf. Formal Power Series and Algebraic Combinatorics , Nankai University, Tianjin. Available at http://www.fpsac.cn/PDF-Proc./Posters/43.pdf. · Zbl 1192.68968
[10] Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stoch. Process. Appl. 110, 177-245. · Zbl 1075.60109 · doi:10.1016/j.spa.2003.12.002
[11] Janson, S. (2005). Limit theorems for triangular urn schemes. Prob. Theory Relat. Fields 134, 417-452. · Zbl 1112.60012 · doi:10.1007/s00440-005-0442-7
[12] Johnson, N. L. and Kotz, S. (1977). Urn Models and Their Application. John Wiley, New York. · Zbl 0352.60001
[13] Kingman, J. F. C. (1999). Martingales in the OK Corral. Bull. London Math. Soc. 31, 601-606. · Zbl 0933.60007 · doi:10.1112/S0024609399006098
[14] Kingman, J. F. C. (2002). Stochastic aspects of Lanchester’s thoery of warfare. J. Appl. Prob. 39, 455-465, · Zbl 1028.60041 · doi:10.1239/jap/1034082119
[15] Kingman, J. F. C. and Volkov, S. E. (2003). Solution to the OK Corral model via decoupling of Friedman’s urn. J. Theoret. Prob. 16, 267-276, · Zbl 1022.60007 · doi:10.1023/A:1022294908268
[16] Knuth, D. E \et (1992). Problems and solutions: solutions E3429. Amer. Math. Monthly 99, 684.
[17] Knuth, D. E. and McCarthy, J. (1991). Problem E3429: big pills and little pills. Amer. Math. Monthly 98, 264. · doi:10.2307/2324448
[18] 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. · Zbl 0888.60014 · doi:10.1007/978-1-4612-4140-9_14
[19] Loève, M. (1977). Probability Theory. I , 4th edn. Springer, New York.
[20] Puyhaubert, V. (2005). Modéles d’urnes et phénomènes de seuil en combinatoire analytique. Doctoral Thesis, École Polytechnique.
[21] Stadje, W. (1998). Asymptotic probabilities in a sequential urn scheme related to the matchbox problem. Adv. Appl. Prob. 30, 831-849. · Zbl 0922.60064 · doi:10.1239/aap/1035228131
[22] Turner, A. G. (2007). Convergence of Markov processes near saddle fixed points. Ann. Prob. 35, 1141-1171. · Zbl 1134.60019 · doi:10.1214/009117906000000836
[23] Williams, D. and McIlroy, P. (1998). The OK Corral and the power of the law (a curious Poisson-kernel formula for a parabolic equation). Bull. London Math. Soc. 30, 166-170. · Zbl 0933.60006 · doi:10.1112/S0024609397004062
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.