×

Asymptotic lattice path enumeration using diagonals. (English) Zbl 1390.05015

Summary: We consider \(d\)-dimensional lattice path models restricted to the first orthant whose defining step sets exhibit reflective symmetry across every axis. Given such a model, we provide explicit asymptotic enumerative formulas for the number of walks of a fixed length: the exponential growth is given by the number of distinct steps a model can take, while the sub-exponential growth depends only on the dimension of the underlying lattice and the number of steps moving forward in each coordinate. The generating function of each model is first expressed as the diagonal of a multivariate rational function, then asymptotic expressions are derived by analyzing the singular variety of this rational function. Additionally, we show how to compute subdominant growth, reflect on the difference between rational diagonals and differential equations as data structures for D-finite functions, and show how to determine first order asymptotics for the subset of walks that start and end at the origin.

MSC:

05A15 Exact enumeration problems, generating functions

Software:

ore_algebra; amgf; GitHub
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] André, D.: Solution directe du problème résolu par M. Bertrand. C. R. Acad. Sci. Paris 105, 436-437 (1887)
[2] Aparicio-Monforte, A., Kauers, M.: Formal Laurent series in several variables. Expos. Math. 31(4), 350-367 (2013) · Zbl 1283.13018 · doi:10.1016/j.exmath.2013.01.004
[3] Bostan, A., Bousquet-Mélou, M., Kauers, M., Melczer, S.: On lattice walks confined to the positive octant. Accepted to the Ann. Comb. November (2014). http://arxiv.org/abs/1409.3669 · Zbl 1354.05006
[4] Bostan, A., Kauers, M.: Automatic classification of restricted lattice walks. In: Proceedings of FPSAC 2009, Discrete Mathematics and Theoretical Computer Science Proceedings, AK, pp. 201-215 (2009) · Zbl 1391.05026
[5] Bostan, A., Kurkova, I., Raschel, K.: A human proof of Gessel’s lattice path conjecture. http://arxiv.org/abs/1309.1023 · Zbl 1350.05006
[6] Bostan, A., Lairez, P., Salvy, B.: Creative telescoping for rational functions using the Griffiths-Dwork method. In: Proceedings of the international symposium on symbolic and algebraic computation (ISSAC), New York, NY, USA. ACM, pp. 93-100 (2013) · Zbl 1360.68921
[7] Bostan, A., Raschel, K., Salvy, B.: Non-D-finite excursions in the quarter plane. J. Comb. Theory Ser. A 121, 45-63 (2014) · Zbl 1279.05003 · doi:10.1016/j.jcta.2013.09.005
[8] Bousquet-Mélou, M.: Walks in the quarter plane: Kreweras’ algebraic model. Ann. Appl. Probab. 15(2), 1451-1491 (2005) · Zbl 1064.05010 · doi:10.1214/105051605000000052
[9] Bousquet-Mélou, M.: An elementary solution of Gessel’s walks in the quadrant. http://arxiv.org/abs/1503.08573 (2015) · Zbl 1351.05017
[10] Bousquet-Mélou, M., Mishna, M.: Walks with small steps in the quarter plane. In: Algorithmic Probability and Combinatorics, vol. 520 of Contemporary Mathematics, pp. 1-40. American Mathematical Society, Providence, RI (2010) · Zbl 1209.05008
[11] Bousquet-Mélou, M., Petkovšek, M.: Walks confined in a quadrant are not always D-finite. Theor. Comput. Sci. 307(2):257-276. Random generation of combinatorial objects and bijective combinatorics (2003) · Zbl 1070.68112
[12] Christol, G.: Globally bounded solutions of differential equations. In: Analytic Number Theory (Tokyo, 1988), vol. 1434 of Lecture Notes in Mathematics, pp. 45-64. Springer, Berlin (1990) · Zbl 0579.05007
[13] Denisov, D., Wachtel, V.: Random walks in cones. Ann. Probab. 43(3), 992-1044 (2015) · Zbl 1332.60066 · doi:10.1214/13-AOP867
[14] Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random Walks in the Quarter-Plane. Algebraic Methods, Boundary Value Problems and Applications, vol. 40. Springer-Verlag, Berlin Heidelberg (1999) · Zbl 0932.60002
[15] Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009) · Zbl 1165.05001 · doi:10.1017/CBO9780511801655
[16] Garrabrant, S., Pak, I.: Counting with irrational tiles. http://arxiv.org/abs/1407.8222
[17] Gessel, I.M., Zeilberger, D.: Random walk in a Weyl chamber. Proc. Am. Math. Soc. 115(1), 27-31 (1992) · Zbl 0792.05148 · doi:10.1090/S0002-9939-1992-1092920-8
[18] Grabiner, D.J.: A combinatorial correspondence for walks in Weyl chambers. J. Comb. Theory Ser. A 71(2), 275-292 (1995) · Zbl 0840.05100 · doi:10.1016/0097-3165(95)90004-7
[19] Grabiner, D.J., Magyar, P.: Random walks in Weyl chambers and the decomposition of tensor powers. J. Algebr. Comb. 2(3), 239-260 (1993) · Zbl 0780.60069 · doi:10.1023/A:1022499531492
[20] Humphreys, J.E.: Introduction to Lie algebras and representation theory. In: Graduate Texts in Mathematics, vol. 9. Springer, New York (1972) · Zbl 0254.17004
[21] Janse van Rensburg, E.J., Prellberg, T., Rechnitzer, A.: Partially directed paths in a wedge. J. Comb. Theory Ser. A 115(4), 623-650 (2008) · Zbl 1160.05003 · doi:10.1016/j.jcta.2007.08.003
[22] Kauers, M., Jaroschek, M., Johansson, F.: Computer Algebra and Polynomials. In: Gutierrez, J., Schicho, J., Weimann, M. (eds.) Ore Polynomials in Sage, vol. 8942, pp. 105-125. Springer International Publishing (2015) · Zbl 1439.16049
[23] Koutschan, C.: A fast approach to creative telescoping. Math. Comput. Sci. 4(2-3), 259-266 (2010) · Zbl 1218.68205 · doi:10.1007/s11786-010-0055-0
[24] Lipshitz, L.: D-finite power series. J. Algebra 122(2), 353-373 (1989) · Zbl 0695.12018 · doi:10.1016/0021-8693(89)90222-6
[25] Melczer, S., Mishna, M.: Singularity analysis via the iterated kernel method. Comb. Probab. Comput. 23, 861-888 (2014) · Zbl 1298.05026 · doi:10.1017/S0963548314000145
[26] Pemantle, R., Wilson, M.C.: Asymptotics of multivariate sequences: I. Smooth points of the singular variety. J. Comb. Theory Ser. A 97(1), 129-161 (2002) · Zbl 1005.05007 · doi:10.1006/jcta.2001.3201
[27] Pemantle, R., Wilson, M.C.: Analytic Combinatorics in Several Variables. Cambridge University Press, Cambridge (2013) · Zbl 1297.05004 · doi:10.1017/CBO9781139381864
[28] Raichev, A.: Amgf documentation—release 0.8. https://github.com/araichev/amgf (2012)
[29] Raichev, A., Wilson, M.C.: Asymptotics of coefficients of multivariate generating functions: improvements for smooth points. Electr. J. Comb. 15(1) (2008) · Zbl 1165.05309
[30] Raichev, A., Wilson, M.C.: Asymptotics of coefficients of multivariate generating functions: improvements for multiple points. Online J. Anal. Comb. 6 (2011) · Zbl 1292.05039
[31] Wimp, J., Zeilberger, D.: Resurrecting the asymptotics of linear recurrences. J. Math. Anal. Appl. 111(1), 162-176 (1985) · Zbl 0579.05007 · doi:10.1016/0022-247X(85)90209-4
[32] Xin, G.: Determinant formulas relating to tableaux of bounded height. Adv. Appl. Math. 45(2), 197-211 (2010) · Zbl 1209.05012 · doi:10.1016/j.aam.2007.04.007
[33] Zeilberger, D.: A holonomic systems approach to special functions identities. J. Comput. Appl. Math. 32(3), 321-368 (1990) · Zbl 0738.33001 · doi:10.1016/0377-0427(90)90042-X
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.