Classifying walks in the quarter plane

The objects of study here are two-dimensional lattice walks, with a fixed set of step directions, restricted to the first quadrant. These walks are well studied, both in a general context of probabilistic models, and specifically as particular case studies for fixed direction sets, notably the so-called Kreweras' walks defined by the direction set {NE, W, S}.

The goal here is to examine two series associated to these walks: a simple length generating function, and a complete generating function which encodes endpoints of walks, and to determine combinatorial criteria which decide when these series are algebraic, D-finite, or none of the above. (Indeed we have examples of non-D-finite generating functions.) We shall present a complete classification of all nearest neighbour walks where the set of directions is of cardinality three, and discuss how this leads to a natural conjecture for the classification of nearest walks with any direction set.

(Work in progress with M. Bousquet-Mélou)