Asymptotics of lattice walks via analytic combinatorics in several variables
From MaRDI portal
Publication:5111013
Abstract: We consider the enumeration of walks on the two dimensional non-negative integer lattice with short steps. Up to isomorphism there are 79 unique two dimensional models to consider, and previous work in this area has used the kernel method, along with a rigorous computer algebra approach, to show that 23 of the 79 models admit D-finite generating functions. In 2009, Bostan and Kauers used Pad'e-Hermite approximants to guess differential equations which these 23 generating functions satisfy, in the process guessing asymptotics of their coefficient sequences. In this article we provide, for the first time, a complete rigorous verification of these guesses. Our technique is to use the kernel method to express 19 of the 23 generating functions as diagonals of tri-variate rational functions and apply the methods of analytic combinatorics in several variables (the remaining 4 models have algebraic generating functions and can thus be handled by univariate techniques). This approach also shows the link between combinatorial properties of the models and features of its asymptotics such as asymptotic and polynomial growth factors. In addition, we give expressions for the number of walks returning to the x-axis, the y-axis, and the origin, proving recently conjectured asymptotics of Bostan, Chyzak, van Hoeij, Kauers, and Pech.
Recommendations
- Higher dimensional lattice walks: connecting combinatorial and analytic behavior
- A combinatorial understanding of lattice path asymptotics
- Statistics on lattice walks and \(q\)-Lassalle numbers
- Asymptotics of distributions of random walks on multidimensional Pascal graphs and on root lattices
- A note on the asymptotics of lattice paths with general boundaries
- scientific article; zbMATH DE number 10643
- Enumeration and asymptotics for the area of lattice paths
- Characterizations of random walks on random lattices and their ramifications
- scientific article; zbMATH DE number 2247483
Cites work
- scientific article; zbMATH DE number 1300856 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- A human proof of Gessel's lattice path conjecture
- Analytic combinatorics
- Analytic combinatorics in several variables.
- Asymptotics of Multivariate Sequences II: Multiple Points of the Singular Variety
- Asymptotics of coefficients of multivariate generating functions: improvements for multiple points
- Asymptotics of multivariate sequences. I: Smooth points of the singular variety
- Automatic Classification of Restricted Lattice Walks
- Basic analytic combinatorics of directed lattice paths
- Classifying lattice walks restricted to the quarter plane
- Families of prudent self-avoiding walks
- Generating functions for generating trees
- Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
- Linear recurrences with constant coefficients: The multivariate case
- Non-D-finite excursions in the quarter plane
- On the functions counting walks with small steps in the quarter plane
- Proof of Ira Gessel's lattice path conjecture
- Random walks in cones: the case of nonzero drift
- Singularity analysis via the iterated kernel method
- Some exact asymptotics in the counting of walks in the quarter plane
- The complete generating function for Gessel walks is algebraic
- Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions
- Two non-holonomic lattice walks in the quarter plane
- Walks confined in a quadrant are not always D-finite
- Walks in the quarter plane: Kreweras' algebraic model
Cited in
(15)- On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks
- Weighted lattice walks and universality classes
- Lattice walks confined to an octant in dimension 3: (non-)rationality of the second critical exponent
- The vectorial kernel method for walks with longer steps
- Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
- The research and progress of the enumeration of lattice paths
- On the nature of four models of symmetric walks avoiding a quadrant
- Statistics on lattice walks and \(q\)-Lassalle numbers
- A combinatorial understanding of lattice path asymptotics
- Singularity analysis via the iterated kernel method
- Riordan matrices and higher-dimensional lattice walks
- Higher dimensional lattice walks: connecting combinatorial and analytic behavior
- scientific article; zbMATH DE number 10643 (Why is no real title available?)
- Counting walks with large steps in an orthant
- Computer algebra in the service of enumerative combinatorics
This page was built for publication: Asymptotics of lattice walks via analytic combinatorics in several variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111013)
