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.

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)𝒬(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)𝐙 + 2 after n steps is studied. For all non-singular models of walks, the functions xQ(x,0;z) and yQ(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 / | 𝒮 | [ of variation of z splits into two dense subsets such that the functions x 𝒬 ( x , 0 ; z ) and y 𝒬 ( 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 ) 𝒬 ( x , y ; z ) , and therefore proves a conjecture of Bousquet-Mélou and Mishna in Contemp. Math. 520:1–40(2010).

DOI: 10.1007/s10240-012-0045-7
Kurkova, Irina 1; Raschel, Kilian 2

1 Laboratoire de Probabilités et Modèles Aléatoires, Université Pierre et Marie Curie 4 Place Jussieu, 75252, Paris Cedex 05 France
2 Faculté des Sciences et Techniques, CNRS and Université de Tours Parc de Grandmont, 37200, Tours France
@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.] 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

Cited by Sources: