Asymptotics of lattice walks via analytic combinatorics in several variables

zbMATH Open1440.05027arXiv1511.02527MaRDI QIDQ5111013FDOQ5111013

Stephen Melczer, Mark C. Wilson

Publication date: 26 May 2020

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.

Full work available at URL: https://arxiv.org/abs/1511.02527

zbMATH Keywords

critical pointsanalytic combinatorics in several variableslattice path enumerationdiagonalD-finite

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotics of multivariate sequences. I: Smooth points of the singular variety
• Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions
• Asymptotics of Multivariate Sequences II: Multiple Points of the Singular Variety
• Classifying lattice walks restricted to the quarter plane
• Generating functions for generating trees
• Linear recurrences with constant coefficients: The multivariate case
• Basic analytic combinatorics of directed lattice paths
• Walks confined in a quadrant are not always D-finite
• On the functions counting walks with small steps in the quarter plane
• Asymptotic lattice path enumeration using diagonals
• Automatic Classification of Restricted Lattice Walks
• Singularity Analysis Via the Iterated Kernel Method
• Non-D-finite excursions in the quarter plane
• The complete generating function for Gessel walks is algebraic
• Walks in the quarter plane: Kreweras' algebraic model
• Two non-holonomic lattice walks in the quarter plane
• A human proof of Gessel's lattice path conjecture
• Analytic combinatorics in several variables.
• Asymptotics of coefficients of multivariate generating functions: improvements for multiple points
• Random walks in cones: the case of nonzero drift
• Proof of Ira Gessel's lattice path conjecture
• Families of prudent self-avoiding walks
• Some exact asymptotics in the counting of walks in the quarter plane
• Hypergeometric expressions for generating functions of walks with small steps in the quarter plane

Cited In (7)

• Statistics on lattice walks and \(q\)-Lassalle numbers
• The research and progress of the enumeration of lattice paths
• Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior
• On the nature of four models of symmetric walks avoiding a quadrant
• Computer algebra in the service of enumerative combinatorics
• Counting walks with large steps in an orthant
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Asymptotics of distributions of random walks on multidimensional Pascal graphs and on root lattices 👍 👎
• A combinatorial understanding of lattice path asymptotics 👍 👎
• Statistics on lattice walks and \(q\)-Lassalle numbers 👍 👎
• Characterizations of random walks on random lattices and their ramifications 👍 👎
• A note on the asymptotics of lattice paths with general boundaries 👍 👎
• Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior 👍 👎

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)