On the Holonomy or Algebraicity of Generating Functions Counting Lattice Walks in the Quarter-Plane

G. Fayolle, K. Raschel

2010, v.16, Issue 3, 485-496

ABSTRACT

In two recent works [M. Bousquet-Melou and M. Mishna, Walks with small steps in the quarter plane. In: "Algorithmic Probability and Combinatorics", special volume of the Contemporary Mathematics series of the Amer. Math. Soc., 2010, v. 520, pp. 1-40; A. Bostan and M. Kauers, The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc., 2009, v. 138, N9, 3063-3078], it has been shown that the counting generating functions (CGF) for the 23 walks with small steps confined in a quarter-plane and associated with a finite group of birational transformations are holonomic, and even algebraic in 4 cases - in particular for the so-called Gessel's walk. It turns out that the type of functional equations satisfied by these CGF appeared in a probabilistic context almost 40 years ago. Then a method of resolution was proposed in [G. Fayolle, R. Iasnogorodski and V. Malyshev, Random Walks in the Quarter-Plane, Applications of Mathematics (New York), vol. 40, 1999, Springer-Verlag, Berlin], involving at once algebraic techniques and reduction to boundary value problems. Recently this method has been developed in a combinatorics framework in [K. Raschel, Counting walks in a quadrant: a unified approach via boundary value problems. Preprint http://arxiv.org/abs/1003.1362, 2010], where a thorough study of the explicit expressions for the CGF is proposed. The aim of this paper is to derive the nature of the bivariate CGF by a direct use of some general theorems given in [G. Fayolle, R. Iasnogorodski and V. Malyshev].

Keywords: generating function,piecewise homogeneous lattice walk,quarter-plane,universal covering,Weierstrass elliptic functions,automorphism

COMMENTS

Please log in or register to leave a comment