×

Periodic Pólya urns, the density method and asymptotics of Young tableaux. (English) Zbl 1453.60010

This paper introduces a balanced periodic Pólya urn model of period \(p\) and establishes some explicit enumeration results and links with hypergeometric functions as well as the limit law using a product of generalized gamma distributions. For example, the re-normalized distribution of black balls in a Young-Pólya urn of period \(p\) and parameter \(l\) is shown to be given by the following product of distributions as \(n\) goes to infinity: \(p^{\delta}B_n/[(p+l)n^{\delta}]\) tends in distribution to \(\mathrm{Beta}(b_0,w_0)\prod_{i=0}^{l-1}\mathrm{GenGamma}(b_0+w_0+p+i,p+l)\), where \(B_n\) is the number of black balls after \(n\) steps, \(\delta=p/(p+l)\) and \(\mathrm{Beta}(b_0,w_0)=1\) when initial white ball number \(w_0=0\) or \(\mathrm{Beta}(b_0,w_0)\) is the beta distribution with support \([0,1]\) and density \([\Gamma(b_0+w_0)/[\Gamma(b_0)\Gamma(w_0)]]x^{b_0-1}(1-x)^{w_0-1}\) otherwise. A relation between the southeast and the northwest corners of triangular Young tableaux is also obtained. Some other tidbits discussed include some universality properties of random surfaces and the tails of Mittag-Leffler distributions.

MSC:

60C05 Combinatorial probability
05A15 Exact enumeration problems, generating functions
60F05 Central limit and other weak theorems
60K99 Special processes

Software:

TDDS; DLMF; gfun
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Abramowitz, M. and Stegun, I. A., eds. (1984). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. A Wiley-Interscience Publication. Wiley, New York. Reprint of the 1972 edition, Selected Government Publications. · Zbl 0643.33001
[2] Aldous, D. and Diaconis, P. (1999). Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.) 36 413-432. · Zbl 0937.60001 · doi:10.1090/S0273-0979-99-00796-X
[3] Andrews, G. E., Askey, R. and Roy, R. (1999). Special Functions. Encyclopedia of Mathematics and Its Applications 71. Cambridge Univ. Press, Cambridge.
[4] Angel, O., Holroyd, A. E., Romik, D. and Virág, B. (2007). Random sorting networks. Adv. Math. 215 839-868. · Zbl 1132.60008 · doi:10.1016/j.aim.2007.05.019
[5] Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Stat. 39 1801-1817. · Zbl 0185.46103 · doi:10.1214/aoms/1177698013
[6] Athreya, K. B. and Ney, P. E. (2004). Branching Processes. Dover, Mineola, NY. Reprint of the 1972 original [Springer, New York; MR0373040]. · Zbl 1070.60001
[7] 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. Algebr. Discrete Methods 6 394-405. · Zbl 0568.60010 · doi:10.1137/0606041
[8] Banderier, C. and Drmota, M. (2015). Formulae and asymptotics for coefficients of algebraic functions. Combin. Probab. Comput. 24 1-53. · Zbl 1371.05009 · doi:10.1017/S0963548314000728
[9] Banderier, C., Marchal, P. and Wallner, M. (2018). Periodic Pólya urns and an application to Young tableaux. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. LIPIcs. Leibniz Int. Proc. Inform. 110 Art. No. 11, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. · Zbl 1483.60010
[10] Banderier, C., Marchal, P. and Wallner, M. (2018). Rectangular Young tableaux with local decreases and the density method for uniform random generation. In GASCom 2018, CEUR Workshop Proceedings 2113 60-68.
[11] Baryshnikov, Y. and Romik, D. (2010). Enumeration formulas for Young tableaux in a diagonal strip. Israel J. Math. 178 157-186. · Zbl 1206.05011 · doi:10.1007/s11856-010-0061-6
[12] Bertoin, J. and Yor, M. (2001). On subordinators, self-similar Markov processes and some factorizations of the exponential variable. Electron. Commun. Probab. 6 95-106. · Zbl 1024.60030 · doi:10.1214/ECP.v6-1039
[13] Biane, P. (1998). Representations of symmetric groups and free probability. Adv. Math. 138 126-181. · Zbl 0927.20008 · doi:10.1006/aima.1998.1745
[14] Borodin, A. and Olshanski, G. (2017). Representations of the Infinite Symmetric Group. Cambridge Studies in Advanced Mathematics 160. Cambridge Univ. Press, Cambridge.
[15] Bostan, A., Chyzak, F., Giusti, M., Lebreton, R., Lecerf, G., Salvy, B. and Schost, É. (2017). Algorithmes Efficaces en Calcul Formel. Self-publishing.
[16] Boulier, F., Lemaire, F., Poteaux, A. and Moreno Maza, M. (2019). An equivalence theorem for regular differential chains. J. Symbolic Comput. 93 34-55. · Zbl 1422.13023 · doi:10.1016/j.jsc.2018.04.011
[17] Boutillier, C., Bouttier, J., Chapuy, G., Corteel, S. and Ramassamy, S. (2017). Dimers on rail yard graphs. Ann. Inst. Henri Poincaré D 4 479-539. · Zbl 1391.82008 · doi:10.4171/AIHPD/46
[18] Bouttier, J., Chapuy, G. and Corteel, S. (2017). From Aztec diamonds to pyramids: Steep tilings. Trans. Amer. Math. Soc. 369 5921-5959. · Zbl 1362.05033 · doi:10.1090/tran/7169
[19] Bubeck, S., Mossel, E. and Rácz, M. Z. (2015). On the influence of the seed graph in the preferential attachment model. IEEE Trans. Netw. Sci. Eng. 2 30-39.
[20] Bufetov, A. and Gorin, V. (2019). Fourier transform on high-dimensional unitary groups with applications to random tilings. Duke Math. J. 168 2559-2649. · Zbl 1436.60016 · doi:10.1215/00127094-2019-0023
[21] Carleman, T. (1923). Sur les équations intégrales singulières à noyau réel et symétrique. Uppsala Universitets Årsskrift. · JFM 49.0272.01
[22] Chauvin, B., Mailler, C. and Pouyanne, N. (2015). Smoothing equations for large Pólya urns. J. Theoret. Probab. 28 923-957. · Zbl 1358.60010 · doi:10.1007/s10959-013-0530-z
[23] Devroye, L. (1986). Nonuniform Random Variate Generation. Springer, New York. · Zbl 0593.65005
[24] Dufresne, D. (2010). \(G\) distributions and the beta-gamma algebra. Electron. J. Probab. 15 2163-2199. · Zbl 1226.60021 · doi:10.1214/EJP.v15-845
[25] Duse, E., Johansson, K. and Metcalfe, A. (2016). The cusp-Airy process. Electron. J. Probab. 21 Paper No. 57, 50. · Zbl 1348.60008 · doi:10.1214/16-EJP2
[26] Eggenberger, F. and Pólya, G. (1923). Über die Statistik verketteter Vorgänge. ZAMM Z. Angew. Math. Mech. 3 279-290. · JFM 49.0382.01
[27] Eggenberger, F. and Pólya, G. (1928). Sur l’interprétation de certaines courbes de fréquence. C. R. Acad. Sci. 187 870-872. · JFM 54.0549.02
[28] Elkies, N. D. (2003). On the sums \(\sum^{\infty}_{k=-\infty}(4k+1)^{-n}\). Amer. Math. Monthly 110 561-573. · Zbl 1083.11055
[29] Fanti, G. and Viswanath, P. (2017). Deanonymization in the Bitcoin P2P network. In Proceedings of the 31st Conference on Neural Information Processing Systems.
[30] Flajolet, P., Dumas, P. and Puyhaubert, V. (2006). Some exactly solvable models of urn process theory. In Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities. Discrete Math. Theor. Comput. Sci. Proc., AG 59-118. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1193.60011
[31] Flajolet, P., Gabarró, J. and Pekari, H. (2005). Analytic urns. Ann. Probab. 33 1200-1233. · Zbl 1073.60007 · doi:10.1214/009117905000000026
[32] Flajolet, P. and Lafforgue, T. (1994). Search costs in quadtrees and singularity perturbation asymptotics. Discrete Comput. Geom. 12 151-175.
[33] Flajolet, P. and Sedgewick, R. (2009). Analytic Combinatorics. Cambridge Univ. Press, Cambridge. · Zbl 1165.05001
[34] Fréchet, M. and Shohat, J. (1931). A proof of the generalized second-limit theorem in the theory of probability. Trans. Amer. Math. Soc. 33 533-543. · Zbl 0002.28003
[35] Gerdt, V. P., Lange-Hegermann, M. and Robertz, D. (2019). The MAPLE package TDDS for computing Thomas decompositions of systems of nonlinear PDEs. Comput. Phys. Commun. 234 202-215. · Zbl 07682604
[36] Goldschmidt, C. and Haas, B. (2015). A line-breaking construction of the stable trees. Electron. J. Probab. 20 no. 16, 24. · Zbl 1409.05054 · doi:10.1214/EJP.v20-3690
[37] Gorin, V. and Rahman, M. (2019). Random sorting networks: Local statistics via random matrix laws. Probab. Theory Related Fields 175 45-96. · Zbl 1422.60081 · doi:10.1007/s00440-018-0886-1
[38] Grace, J. H. and Young, A. (2010). The Algebra of Invariants. Cambridge Library Collection. Cambridge Univ. Press, Cambridge. Reprint of the 1903 original.
[39] Graham, R. L., Knuth, D. E. and Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Addison-Wesley, Reading, MA. · Zbl 0836.00001
[40] Greene, C., Nijenhuis, A. and Wilf, H. S. (1984). Another probabilistic method in the theory of Young tableaux. J. Combin. Theory Ser. A 37 127-135. · Zbl 0561.05004 · doi:10.1016/0097-3165(84)90065-7
[41] Han, G.-N. (2010). New hook length formulas for binary trees. Combinatorica 30 253-256. · Zbl 1250.05017 · doi:10.1007/s00493-010-2503-5
[42] Hwang, H.-K., Kuba, M. and Panholzer, A. (2007). Analysis of some exactly solvable diminishing urn models. In Proceedings of FPSAC’2007 (Formal Power Series and Algebraic Combinatorics). Nankai Univ., Tianjin.
[43] Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 177-245. · Zbl 1075.60109
[44] Janson, S. (2005). Asymptotic degree distribution in random recursive trees. Random Structures Algorithms 26 69-83. · Zbl 1059.05094 · doi:10.1002/rsa.20046
[45] Janson, S. (2006). Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 417-452. · Zbl 1112.60012 · doi:10.1007/s00440-005-0442-7
[46] Janson, S. (2007). Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas. Probab. Surv. 4 80-145. · Zbl 1189.60147 · doi:10.1214/07-PS104
[47] Janson, S. (2010). Moments of gamma type and the Brownian supremum process area. Probab. Surv. 7 1-52. · Zbl 1194.60019 · doi:10.1214/10-PS160
[48] Johansson, K. and Nordenstam, E. (2006). Eigenvalues of GUE minors. Electron. J. Probab. 11 1342-1371. · Zbl 1127.60047 · doi:10.1214/EJP.v11-370
[49] Kahane, J.-P. (1960). Propriétés locales des fonctions à séries de Fourier aléatoires. Studia Math. 19 1-25. · Zbl 0096.11402
[50] Kauers, M. and Paule, P. (2011). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Texts and Monographs in Symbolic Computation. Springer, Vienna. · Zbl 1225.00001
[51] Kenyon, R. (2001). Dominos and the Gaussian free field. Ann. Probab. 29 1128-1137. · Zbl 1034.82021 · doi:10.1214/aop/1015345599
[52] Kerov, S. V. (1993). Transition probabilities of continual Young diagrams and the Markov moment problem. Funct. Anal. Appl. 27 104-117. · Zbl 0808.05098 · doi:10.1007/BF01085981
[53] Khodabin, M. and Ahmadabadi, A. (2010). Some properties of generalized gamma distribution. Math. Sci. 4 9-27. · Zbl 1209.60009
[54] Kuba, M. and Mahmoud, H. M. (2017). Two-color balanced affine urn models with multiple drawings. Adv. in Appl. Math. 90 1-26. · Zbl 1366.60019 · doi:10.1016/j.aam.2017.04.004
[55] Kuba, M. and Panholzer, A. (2016). Combinatorial families of multilabelled increasing trees and hook-length formulas. Discrete Math. 339 227-254. · Zbl 1322.05121 · doi:10.1016/j.disc.2015.08.010
[56] Kuba, M. and Sulzbach, H. (2017). On martingale tail sums in affine two-color urn models with multiple drawings. J. Appl. Probab. 54 96-117. · Zbl 1397.60066 · doi:10.1017/jpr.2016.89
[57] Lah, I. (1954). A new kind of numbers and its application in the actuarial mathematics. Bol. Inst. Dos Actuár. Portugueses 9 7-15. · Zbl 0055.37902
[58] Lasmar, N., Mailler, C. and Selmi, O. (2018). Multiple drawing multi-colour urns by stochastic approximation. J. Appl. Probab. 55 254-281. · Zbl 1401.60035 · doi:10.1017/jpr.2018.16
[59] Linusson, S., Potka, S. and Sulzgruber, R. (2018). On random shifted standard Young tableaux and 132-avoiding sorting networks. Available at arXiv:1804.01795. · Zbl 1435.05223
[60] Logan, B. F. and Shepp, L. A. (1977). A variational problem for random Young tableaux. Adv. Math. 26 206-222. · Zbl 0363.62068 · doi:10.1016/0001-8708(77)90030-5
[61] Macdonald, I. G. (2015). Symmetric Functions and Hall Polynomials, 2nd ed. Oxford Classic Texts in the Physical Sciences. Clarendon, Oxford. With contribution by A. V. Zelevinsky and a foreword by Richard Stanley. Reprint of the 2008 paperback edition [MR1354144].
[62] Mahmoud, H. M. (2009). Pólya Urn Models. Texts in Statistical Science Series. CRC Press, Boca Raton, FL. · Zbl 1149.60005
[63] Marchal, P. (2016). Rectangular Young tableaux and the Jacobi ensemble. Discrete Math. Theor. Comput. Sci. Proc. BC 839-850. · Zbl 1440.05223
[64] Marchal, P. (2018). The density method for permutations with prescribed descents. In GASCom 2018, CEUR Workshop Proceedings 2113 179-186.
[65] McKay, B. D., Morse, J. and Wilf, H. S. (2002). The distributions of the entries of Young tableaux. J. Combin. Theory Ser. A 97 117-128. · Zbl 1006.05062 · doi:10.1006/jcta.2001.3200
[66] Morales, A. H., Pak, I. and Panova, G. (2019). Hook formulas for skew shapes III. Multivariate and product formulas. Algebraic Combin. 2 815-861. · Zbl 1425.05158
[67] Morcrette, B. and Mahmoud, H. M. (2012). Exactly solvable balanced tenable urns with random entries via the analytic methodology. In 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA’12). Discrete Math. Theor. Comput. Sci. Proc., AQ 219-232. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1296.60015
[68] Olver, F. W. J., Lozier, D. W., Boisvert, R. F. and Clark, C. W., eds. (2010). NIST Handbook of Mathematical Functions. U.S. Dept. Commerce, National Institute of Standards and Technology. See also the NIST Digital Library of Mathematical Functions. · Zbl 1198.00002
[69] Pak, I. (2001/02). Hook length formula and geometric combinatorics. Sém. Lothar. Combin. 46 Art. B46f, 13. · Zbl 0982.05109
[70] Peköz, E. A., Röllin, A. and Ross, N. (2016). Generalized gamma approximation with rates for urns, walks and trees. Ann. Probab. 44 1776-1816. · Zbl 1367.60019
[71] Petkovšek, M., Wilf, H. S. and Zeilberger, D. (1996). \(A=B\). AK Peters, Wellesley. · Zbl 0848.05002
[72] Petrov, L. (2015). Asymptotics of uniformly random lozenge tilings of polygons. Gaussian free field. Ann. Probab. 43 1-43. · Zbl 1315.60062 · doi:10.1214/12-AOP823
[73] Pittel, B. and Romik, D. (2007). Limit shapes for random square Young tableaux. Adv. in Appl. Math. 38 164-209. · Zbl 1122.60009 · doi:10.1016/j.aam.2005.12.005
[74] Pólya, G. (1930). Sur quelques points de la théorie des probabilités. Ann. Inst. Henri Poincaré 1 117-161.
[75] Polya, G. (2014). How to Solve It: A New Aspect of Mathematical Method. Princeton Science Library. Princeton Univ. Press, Princeton, NJ. With a foreword by John H. Conway. Reprint of the 1957 second edition [MR2183670].
[76] Prudnikov, A. P., Brychkov, Y. A. and Marichev, O. I. (1992). Integrals and Series. Vol. 4: Direct Laplace Transforms. Gordon & Breach, New York. · Zbl 0786.44003
[77] Riordan, J. (2002). An Introduction to Combinatorial Analysis. Dover, Mineola, NY. Reprint of the 1958 original [Wiley, New York; MR0096594 (20 #3077)]. · Zbl 0078.00805
[78] Rivest, R. L. (2018). Bayesian tabulation audits: Explained and extended. Available at arXiv:1801.00528.
[79] Romik, D. (2004). Explicit formulas for hook walks on continual Young diagrams. Adv. in Appl. Math. 32 625-654. · Zbl 1051.05080 · doi:10.1016/S0196-8858(03)00096-4
[80] Romik, D. (2012). Arctic circles, domino tilings and square Young tableaux. Ann. Probab. 40 611-647. · Zbl 1258.60014 · doi:10.1214/10-AOP628
[81] Romik, D. (2015). The Surprising Mathematics of Longest Increasing Subsequences. Institute of Mathematical Statistics Textbooks 4. Cambridge Univ. Press, New York. · Zbl 1345.05003
[82] Sagan, B. E. and Yeh, Y. N. (1989). Probabilistic algorithms for trees. Fibonacci Quart. 27 201-208. · Zbl 0675.05021
[83] Salvy, B. and Zimmermann, P. (1994). Gfun: A Maple package for the manipulation of generating and holonomic functions in one variable. ACM Trans. Math. Software 20 163-177. · Zbl 0888.65010 · doi:10.1145/178365.178368
[84] Sénizergues, D. (2019). Geometry of weighted recursive and affine preferential attachment trees. Available at arXiv:1904.07115.
[85] Sheffield, S. (2005). Random surfaces. Astérisque 304 vi+175. · Zbl 1104.60002
[86] Sniady, P. (2014). Robinson-Schensted-Knuth algorithm, jeu de taquin, and Kerov-Vershik measures on infinite tableaux. SIAM J. Discrete Math. 28 598-630. · Zbl 1300.60025 · doi:10.1137/130930169
[87] Stacy, E. W. (1962). A generalization of the gamma distribution. Ann. Math. Stat. 33 1187-1192. · Zbl 0121.36802 · doi:10.1214/aoms/1177704481
[88] Stanley, R. P. (1986). Two poset polytopes. Discrete Comput. Geom. 1 9-23. · Zbl 0595.52008 · doi:10.1007/BF02187680
[89] Stanley, R. P. (1999). Enumerative Combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics 62. Cambridge Univ. Press, Cambridge.
[90] Vershik, A. M. (2001). Randomization of algebra and algebraization of probability—an attempt at prediction. In Mathematics Unlimited—2001 and Beyond 1157-1166. Springer, Berlin. · Zbl 1001.60002
[91] Veršik, A. M. and Kerov, S. V. (1977). Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux. Dokl. Akad. Nauk SSSR 233 1024-1027.
[92] Wall, H. S. (1948). Analytic Theory of Continued Fractions. Van Nostrand, New York, NY. · Zbl 0035.03601
[93] Wallner, M. · Zbl 1439.05018 · doi:10.1016/j.ejc.2020.103138
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.