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

Abstract : In two recent works \cite{BMM,BK}, it has been shown that the counting generating functions (CGF) for the 23 walks with small steps confined in a quadrant 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 \cite{FIM}, involving at once algebraic tools and a reduction to boundary value problems. Recently this method has been developed in a combinatorics framework in \cite{Ra}, 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 \cite{FIM}.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00469603
Contributor : Guy Fayolle <>
Submitted on : Friday, April 2, 2010 - 12:09:20 PM
Last modification on : Wednesday, May 15, 2019 - 3:47:53 AM
Long-term archiving on : Monday, July 5, 2010 - 9:07:33 PM

Files

RR-7242.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00469603, version 1
  • ARXIV : 1004.1733

Citation

Guy Fayolle, Kilian Raschel. On the Holonomy or Algebraicity of Generating Functions Counting Lattice Walks in the Quarter-Plane. Markov Processes and Related Fields, Polymath, 2010, 16 (3), pp.485-496. ⟨inria-00469603⟩

Share

Metrics

Record views

571

Files downloads

270