Models of spatially homogeneous walks in the quarter plane with steps taken from a subset of the set of jumps to the eight nearest neighbors are considered. The generating function of the numbers of such walks starting at the origin and ending at of such walks starting at the origin and ending at after steps is studied. For all non-singular models of walks, the functions and 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 , the interval of variation of splits into two dense subsets such that the functions and are shown to be holonomic for any from the one of them and non-holonomic for any from the other. This entails the non-holonomy of , and therefore proves a conjecture of Bousquet-Mélou and Mishna in Contemp. Math. 520:1–40(2010).
@article{PMIHES_2012__116__69_0, author = {Kurkova, Irina and Raschel, Kilian}, title = {On the functions counting walks with small steps in the quarter plane}, journal = {Publications Math\'ematiques de l'IH\'ES}, pages = {69--114}, publisher = {Springer-Verlag}, volume = {116}, year = {2012}, doi = {10.1007/s10240-012-0045-7}, mrnumber = {3090255}, zbl = {1255.05012}, language = {en}, url = {http://www.numdam.org/articles/10.1007/s10240-012-0045-7/} }
TY - JOUR AU - Kurkova, Irina AU - Raschel, Kilian TI - On the functions counting walks with small steps in the quarter plane JO - Publications Mathématiques de l'IHÉS PY - 2012 SP - 69 EP - 114 VL - 116 PB - Springer-Verlag UR - http://www.numdam.org/articles/10.1007/s10240-012-0045-7/ DO - 10.1007/s10240-012-0045-7 LA - en ID - PMIHES_2012__116__69_0 ER -
%0 Journal Article %A Kurkova, Irina %A Raschel, Kilian %T On the functions counting walks with small steps in the quarter plane %J Publications Mathématiques de l'IHÉS %D 2012 %P 69-114 %V 116 %I Springer-Verlag %U http://www.numdam.org/articles/10.1007/s10240-012-0045-7/ %R 10.1007/s10240-012-0045-7 %G en %F PMIHES_2012__116__69_0
Kurkova, Irina; Raschel, Kilian. On the functions counting walks with small steps in the quarter plane. Publications Mathématiques de l'IHÉS, Volume 116 (2012), pp. 69-114. doi : 10.1007/s10240-012-0045-7. http://www.numdam.org/articles/10.1007/s10240-012-0045-7/
[1.] The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc., Volume 432 (2010), pp. 3063-3078 | DOI | MR | Zbl
[2.] Walks with small steps in the quarter plane, Contemp. Math., Volume 520 (2010), pp. 1-40 | DOI | MR | Zbl
[3.] Walks confined in a quadrant are not always D-finite, Theor. Comput. Sci., Volume 307 (2003), pp. 257-276 | DOI | MR | Zbl
[4.] Two coupled processors: the reduction to a Riemann-Hilbert problem, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 47 (1979), pp. 325-351 | DOI | MR | Zbl
[5.] 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.] Random Walks in the Quarter-Plane, Springer, Berlin, 1999 | DOI | MR | Zbl
[7.] Analytic Combinatorics, Cambridge University Press, Cambridge, 2009 | DOI | MR | Zbl
[8.] Lectures on the Theory of Functions of a Complex Variable II: Geometric Theory, Wolters-Noordhoff Publishing, Groningen, 1969 | MR | Zbl
[9.] A probabilistic method for lattice path enumeration, J. Stat. Plan. Inference, Volume 14 (1986), pp. 49-58 | DOI | MR | Zbl
[10.] Complex Functions, Cambridge University Press, Cambridge, 1987 | MR | Zbl
[11.] Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA, Volume 106 (2009), pp. 11502-11505 | DOI | MR | Zbl
[12.] Explicit expression for the generating function counting Gessel’s walks, Adv. Appl. Math., Volume 47 (2011), pp. 414-433 | DOI | MR | Zbl
[13.] Random Walks, Wiener-Hopf Equations in the Quarter Plane, Galois Automorphisms, Lomonossov Moscow University Press, Moscow (1970) (in Russian) | MR
[14.] Positive random walks and Galois theory, Usp. Mat. Nauk, Volume 26 (1971), pp. 227-228 | MR | Zbl
[15.] 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.] Two non-holonomic lattice walks in the quarter plane, Theor. Comput. Sci., Volume 410 (2009), pp. 3616-3630 | DOI | MR | Zbl
[18.] 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.] Enumerative Combinatorics, 2, Cambridge University Press, Cambridge, 1999 | DOI | MR | Zbl
[20.] A Course of Modern Analysis, Cambridge University Press, Cambridge, 1962 | MR | Zbl
Cited by Sources: