Singularity analysis via the iterated kernel method. (English) Zbl 1298.05026
Summary: In the quarter plane, five lattice path models with unit steps have resisted the otherwise general approach featured in recent works by P. Fayolle and K. Raschel [Markov Process. Relat. Fields 16, No. 3, 485–496 (2010; Zbl 1284.05018)] and I. Kurkova and K. Raschel [Adv. Appl. Math. 47, No. 3, 414–433 (2011; Zbl 1234.05027)]. Here we consider these five models, called the singular models, and prove that the univariate generating functions marking the number of walks of a given length are not D-finite. Furthermore, we provide exact and asymptotic enumerative formulas for the number of such walks, and describe an efficient algorithm for exact enumeration.
References:
| [1] | Random Walks in the Quarter-Plane: Algebraic Methods, Boundary Value Problems and Applications (1999) · Zbl 0932.60002 |
| [2] | Analytic Combinatorics (2009) · Zbl 1165.05001 |
| [3] | Markov Process. Rel. Fields 16 pp 485– (2010) |
| [4] | Analytic Number Theory: Tokyo, 1988 pp 45– (1990) |
| [5] | DOI: 10.1016/S0304-3975(03)00219-6 · Zbl 1070.68112 · doi:10.1016/S0304-3975(03)00219-6 |
| [6] | DOI: 10.1016/j.tcs.2009.04.008 · Zbl 1228.05038 · doi:10.1016/j.tcs.2009.04.008 |
| [7] | Algorithmic Probability and Combinatorics pp 1– (2010) |
| [8] | DOI: 10.1016/j.aam.2010.11.004 · Zbl 1234.05027 · doi:10.1016/j.aam.2010.11.004 |
| [9] | DOI: 10.1214/105051605000000142 · Zbl 1105.60012 · doi:10.1214/105051605000000142 |
| [10] | CR Math. Acad. Sci. Soc. R. Can. 26 pp 39– (2004) |
| [11] | DOI: 10.1016/j.jcta.2013.09.005 · Zbl 1279.05003 · doi:10.1016/j.jcta.2013.09.005 |
| [12] | DOI: 10.1073/pnas.0901678106 · Zbl 1203.05010 · doi:10.1073/pnas.0901678106 |
| [13] | DOI: 10.1016/j.jcta.2007.08.003 · Zbl 1160.05003 · doi:10.1016/j.jcta.2007.08.003 |
| [14] | Advances in Math., Supplementary Studies, Studies in Foundations and Combinatorics 1 pp 213– (1978) |
| [15] | Electron. J. Combin. 11 pp 2– (2004) |
| [16] | DOI: 10.1016/S0304-3975(02)00007-5 · Zbl 0996.68126 · doi:10.1016/S0304-3975(02)00007-5 |
| [17] | Markov Process. Rel. Fields 17 pp 619– (2011) |
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.
