On the functions counting walks with small steps in the quarter plane

Kurkova, Irina; Raschel, Kilian

Publications Mathématiques de l'IHÉS, Tome 116 (2012), pp. 69-114.

Models of spatially homogeneous walks in the quarter plane ${𝐙}_{+}^2$ with steps taken from a subset $𝒮$ of the set of jumps to the eight nearest neighbors are considered. The generating function $(x,y,z)\mapsto 𝒬(x,y;z)$ of the numbers $q(i,j;n)$ of such walks starting at the origin and ending at of such walks starting at the origin and ending at $(i,j)\in {𝐙}_{+}^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(x,0;z)$ are continued as multi-valued functions on $𝐂$ 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 ${𝐂}^2$, the interval $]0,1/|𝒮\left|\right[$ of variation of $z$ splits into two dense subsets such that the functions $x\mapsto 𝒬(x,0;z)$ and $y\mapsto 𝒬(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 𝒬(x,y;z)$, and therefore proves a conjecture of Bousquet-Mélou and Mishna in Contemp. Math. 520:1–40(2010).

[1.] Bostan, A.; Kauers, M. The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc., Volume 432 (2010), pp. 3063-3078 | DOI | MR | Zbl

[2.] Bousquet-Mélou, M.; Mishna, M. Walks with small steps in the quarter plane, Contemp. Math., Volume 520 (2010), pp. 1-40 | DOI | MR | Zbl

[3.] Bousquet-Mélou, M.; Petkovsek, M. Walks confined in a quadrant are not always D-finite, Theor. Comput. Sci., Volume 307 (2003), pp. 257-276 | DOI | MR | Zbl

[4.] Fayolle, G.; Iasnogorodski, R. Two coupled processors: the reduction to a Riemann-Hilbert problem, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 47 (1979), pp. 325-351 | DOI | MR | Zbl

[5.] Fayolle, G.; Raschel, K. On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane, Markov Process. Relat. Fields, Volume 16 (2010), pp. 485-496 | MR | Zbl

[6.] Fayolle, G.; Iasnogorodski, R.; Malyshev, V. Random Walks in the Quarter-Plane, Springer, Berlin, 1999 | DOI | MR | Zbl

[7.] Flajolet, P.; Sedgewick, R. Analytic Combinatorics, Cambridge University Press, Cambridge, 2009 | DOI | MR | Zbl

[8.] Gerretsen, J.; Sansone, G. Lectures on the Theory of Functions of a Complex Variable II: Geometric Theory, Wolters-Noordhoff Publishing, Groningen, 1969 | MR | Zbl

[9.] Gessel, I. A probabilistic method for lattice path enumeration, J. Stat. Plan. Inference, Volume 14 (1986), pp. 49-58 | DOI | MR | Zbl

[10.] Jones, G.; Singerman, D. Complex Functions, Cambridge University Press, Cambridge, 1987 | MR | Zbl

[11.] Kauers, M.; Koutschan, C.; Zeilberger, D. Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA, Volume 106 (2009), pp. 11502-11505 | DOI | MR | Zbl

[12.] Kurkova, I.; Raschel, K. Explicit expression for the generating function counting Gessel’s walks, Adv. Appl. Math., Volume 47 (2011), pp. 414-433 | DOI | MR | Zbl

[13.] Malyshev, V. Random Walks, Wiener-Hopf Equations in the Quarter Plane, Galois Automorphisms, Lomonossov Moscow University Press, Moscow (1970) (in Russian) | MR

[14.] Malyshev, V. Positive random walks and Galois theory, Usp. Mat. Nauk, Volume 26 (1971), pp. 227-228 | MR | Zbl

[15.] Malyshev, V. An analytical method in the theory of two-dimensional positive random walks, Sib. Math. J., Volume 13 (1972), pp. 1314-1329 | MR | Zbl

[16.] S. Melczer and M. Mishna, Singularity analysis via the iterated kernel method (2011, in preparation). | Zbl

[17.] Mishna, M.; Rechnitzer, A. Two non-holonomic lattice walks in the quarter plane, Theor. Comput. Sci., Volume 410 (2009), pp. 3616-3630 | DOI | MR | Zbl

[18.] Raschel, K. Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc., Volume 14 (2012), pp. 749-777 | DOI | MR | Zbl

[19.] Stanley, R. Enumerative Combinatorics, 2, Cambridge University Press, Cambridge, 1999 | DOI | MR | Zbl

[20.] Watson, G.; Whittaker, E. A Course of Modern Analysis, Cambridge University Press, Cambridge, 1962 | MR | Zbl