×

On the functions counting walks with small steps in the quarter plane. (English) Zbl 1255.05012

Summary: Models of spatially homogeneous walks in the quarter plane \({\mathbf{Z}}_{+}^{2}\) with steps taken from a subset \(\mathcal{S}\) of the set of jumps to the eight nearest neighbors are considered. The generating function \((x,y,z) \mapsto Q(x,y;z)\) of the numbers \(q(i,j;n)\) of such walks starting at the origin and ending at \((i,j) \in\mathbf{ Z}_{+}^{2}\) after \(n\) steps is studied. For all non-singular models of walks, the functions \(x \mapsto Q(x,0;z)\) and \(y \mapsto Q(0,y;z)\) are continued as multi-valued functions on \(\mathbf{C}\) having infinitely many meromorphic branches, of which the set of poles is identified.
The nature of these functions is derived from this result: namely, for all the 51 walks which admit a certain infinite group of birational transformations of \({\mathbf{C}}^2\), the interval \(]0,1/| \mathcal{S} |[\) of variation of \(z\) splits into two dense subsets such that the functions \(x \mapsto Q(x,0;z)\) and \(y \mapsto Q(0,y;z)\) are shown to be holonomic for any \(z\) from the one of them and non-holonomic for any \(z\) from the other. This entails the non-holonomy of \((x,y,z) \mapsto Q(x,y;z)\), and therefore proves a conjecture of M. Bousquet-Mélou and M. Mishna [Contemporary Mathematics 520, 1–39 (2010; Zbl 1209.05008)].

MSC:

05A15 Exact enumeration problems, generating functions

Citations:

Zbl 1209.05008

Software:

gfun
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Bostan and M. Kauers, The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc., 432 (2010), 3063–3078. · Zbl 1206.05013 · doi:10.1090/S0002-9939-2010-10398-2
[2] M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, Contemp. Math., 520 (2010), 1–40. · Zbl 1209.05008 · doi:10.1090/conm/520/10252
[3] M. Bousquet-Mélou and M. Petkovsek, Walks confined in a quadrant are not always D-finite, Theor. Comput. Sci., 307 (2003), 257–276. · Zbl 1070.68112 · doi:10.1016/S0304-3975(03)00219-6
[4] G. Fayolle and R. Iasnogorodski, Two coupled processors: the reduction to a Riemann-Hilbert problem, Z. Wahrscheinlichkeitstheor. Verw. Geb., 47 (1979), 325–351. · Zbl 0395.68032 · doi:10.1007/BF00535168
[5] G. Fayolle and K. Raschel, On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane, Markov Process. Relat. Fields, 16 (2010), 485–496. · Zbl 1284.05018
[6] G. Fayolle, R. Iasnogorodski, and V. Malyshev, Random Walks in the Quarter-Plane, Springer, Berlin, 1999. · Zbl 0932.60002
[7] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009. · Zbl 1165.05001
[8] J. Gerretsen and G. Sansone, Lectures on the Theory of Functions of a Complex Variable II: Geometric Theory, Wolters-Noordhoff Publishing, Groningen, 1969. · Zbl 0188.38104
[9] I. Gessel, A probabilistic method for lattice path enumeration, J. Stat. Plan. Inference, 14 (1986), 49–58. · Zbl 0602.05006 · doi:10.1016/0378-3758(86)90009-1
[10] G. Jones and D. Singerman, Complex Functions, Cambridge University Press, Cambridge, 1987. · Zbl 0608.30001
[11] M. Kauers, C. Koutschan, and D. Zeilberger, Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA, 106 (2009), 11502–11505. · Zbl 1203.05010 · doi:10.1073/pnas.0901678106
[12] I. Kurkova and K. Raschel, Explicit expression for the generating function counting Gessel’s walks, Adv. Appl. Math., 47 (2011), 414–433. · Zbl 1234.05027 · doi:10.1016/j.aam.2010.11.004
[13] V. Malyshev, Random Walks, Wiener-Hopf Equations in the Quarter Plane, Galois Automorphisms, Lomonossov Moscow University Press, Moscow, 1970 (in Russian).
[14] V. Malyshev, Positive random walks and Galois theory, Usp. Mat. Nauk, 26 (1971), 227–228. · Zbl 0254.60043
[15] V. Malyshev, An analytical method in the theory of two-dimensional positive random walks, Sib. Math. J., 13 (1972), 1314–1329.
[16] S. Melczer and M. Mishna, Singularity analysis via the iterated kernel method (2011, in preparation). · Zbl 1294.05019
[17] M. Mishna and A. Rechnitzer, Two non-holonomic lattice walks in the quarter plane, Theor. Comput. Sci., 410 (2009), 3616–3630. · Zbl 1228.05038 · doi:10.1016/j.tcs.2009.04.008
[18] K. Raschel, Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc., 14 (2012), 749–777. · Zbl 1238.05014 · doi:10.4171/JEMS/317
[19] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.
[20] G. Watson and E. Whittaker, A Course of Modern Analysis, Cambridge University Press, Cambridge, 1962. · Zbl 0105.26901
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.