Walks with small steps in the quarter plane

By Mireille Bousquet-M'elou, Marni Mishna. 2008

247 citations recorded by the source corpus.

Let S be a subset of {-1,0,1}^2 not containing (0,0). We address the enumeration of plane lattice walks with steps in S, that start from (0,0) and always remain in the first quadrant. A priori, there are 2^8 problems of this type, but some are trivial. Some others are equivalent to a model of walks confined to a half-plane: such models can be solved systematically using the kernel method, which leads to algebraic generating functions. We focus on the remaining cases, and show that there are 79 inherently different problems to study. To each of them, we associate a group G of birational transformations. We show that this group is finite in exactly 23 cases. We present a unified way of solving 22 of the 23 models associated with a finite group. For each of them, the generating function is found to be D-finite. The 23rd model, known as Gessel's walks, has recently been proved by Bostan et al. to have an algebraic (and hence D-finite) solution. We conjecture that the remaining 56 models, associated with an infinite group, have a non-D-finite generating function. Our approach allows us to recover and refine some known results, and also to obtain new results. For instance, we prove that walks with N, E, W, S, SW and NE steps have an algebraic generating function.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/e8577a344bb5573b8f797bdf0221c0a5328c6d9f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Proof of Ira Gessel's lattice path conjecture (2008, background): “There is, however, strong evidence that even the general counting function F (t; x, y) with “symbolic” x and y is holonomic in t, see [2].”
On the functions counting walks with small steps in the quarter plane (2011, background): “We prove next that function x 7→ Q ( x, 0; z ) does not admit a direct meromorphic continuation on any open domain containing the segment [ x 3 ( z ) , x 4 ( z )] , but admits a meromorphic continuation along any path going once through [ x 3 ( z ) , x 4 ( z )] .”
On 3-Dimensional Lattice Walks Confined to the Positive Octant (2014, unknown): “Can one express all the D-ﬁnite length generating functions that we obtained in terms of hypergeometric series, as was done for quadrant walks in [4]?”
Random walks in cones (2011, background): “Here, we mention papers of Bousquet-Melou [6] and of BousquetMelou and Mishna [7], where the authors obtained exact results for some random walks with bounded steps in the quarter plane.”
The representation of the symmetric group on m-Tamari intervals (2012, unknown): “This idea has already been used for other equations with divided diﬀerences [10].”
Random walks in the quarter plane, discrete harmonic functions and conformal mappings (2013, methodology): “Bousquet-Mélou and Mishna [6] showed that, after eliminating trivial cases, and also those which can be reduced to the walks in a half plane, there remain 79 inherently different models.”
Counting walks in a quadrant: a unified approach via boundary value problems (2010, methodology): “Bousquet-M´elou and Mishna have recently [6] initiated a systematic study of the walks conﬁned to Z 2+ , starting at the origin and having small steps, which means that the set of admissible steps S is included in the set of the eight nearest neighbors, i.e. , S ⊂ { W , NW , N , NE , E , SE , S , SW”