Higher dimensional lattice walks: connecting combinatorial and analytic behavior

DOI10.1137/18M1220856zbMATH Open1433.05026arXiv1810.06170OpenAlexW2984154242MaRDI QIDQ5243172FDOQ5243172

Authors: Stephen Melczer, Mark C. Wilson 

Publication date: 15 November 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We consider the enumeration of walks on the non-negative lattice $mathbb{N}^d$, with steps defined by a set $mathcalSsubset{-1,0,1}^{d}setminusmathbf0$. Previous work in this area has established asymptotics for the number of walks in certain families of models by applying the techniques of analytic combinatorics in several variables (ACSV), where one encodes the generating function of a lattice path model as the diagonal of a multivariate rational function. Melczer and Mishna obtained asymptotics when the set of steps $mathcalS$ is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function whose whose set of singularities is a smooth manifold (the simplest case). Here we go further, providing asymptotics for models with generating functions that must be encoded by multivariate rational functions with non-smooth singular sets. In the process, our analysis connects past work to deeper structural results in the theory of analytic combinatorics in several variables. One application is a closed form for asymptotics of models defined by step sets which are symmetric over all but one axis. As a special case, we apply our results when $d=2$ to give a rigorous proof of asymptotics conjectured by Bostan and Kauers; asymptotics for walks returning to boundary axes and the origin are also given.

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

Recommendations

• Asymptotics of lattice walks via analytic combinatorics in several variables
• The asymptotics of reflectable weighted walks in arbitrary dimension
• Riordan matrices and higher-dimensional lattice walks

zbMATH Keywords

generating functionkernel methodanalytic combinatorics in several variableslattice path enumerationD-finite

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Cites Work

• Analytic combinatorics
• Asymptotics of multivariate sequences. I: Smooth points of the singular variety
• Asymptotics of Multivariate Sequences II: Multiple Points of the Singular Variety
• Title not available (Why is that?)
• Classifying lattice walks restricted to the quarter plane
• 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
• Random walks in cones
• Walks with small steps in the quarter plane
• 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
• On 3-dimensional lattice walks confined to the positive octant
• Walks in the quarter plane: Kreweras' algebraic model
• Asymptotics of coefficients of multivariate generating functions: Improvements for smooth points
• A human proof of Gessel's lattice path conjecture
• Analytic combinatorics in several variables.
• An elementary solution of Gessel's walks in the quadrant
• Random Walk in a Weyl Chamber
• Random walks in Weyl chambers and the decomposition of tensor powers
• Title not available (Why is that?)
• Title not available (Why is that?)
• A probabilistic method for lattice path enumeration
• Random walks in cones: the case of nonzero drift
• Proof of Ira Gessel's lattice path conjecture
• The diagonal of a D-finite power series is D-finite
• 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
• Lattice path combinatorics and asymptotics of multiplicities of weights in tensor powers
• Lattice path enumeration
• Andre's reflection proof generalized to the many-candidate ballot problem
• On the exit time from a cone for random walks with drift
• Title not available (Why is that?)
• Asymptotics for the number of walks in a Weyl chamber of type \(B\)
• Title not available (Why is that?)
• Weighted lattice walks and universality classes
• Counting walks with large steps in an orthant
• Asymptotics of lattice walks via analytic combinatorics in several variables

Cited In (12)

• Riordan matrices and higher-dimensional lattice walks
• Asymptotic enumeration of lonesum matrices
• Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
• Combinatorics of nondeterministic walks of the Dyck and Motzkin type
• On the algebraic area of lattice walks and the Hofstadter model
• Asymptotics of lattice walks via analytic combinatorics in several variables
• INTERACTING QUARTER-PLANE LATTICE WALK PROBLEMS: SOLUTIONS AND PROOFS
• Asymptotics for the number of walks in a Weyl chamber of type \(B\)
• The asymptotics of reflectable weighted walks in arbitrary dimension
• The asymptotics of reflectable weighted walks in arbitrary dimension
• Coefficient asymptotics of algebraic multivariable generating functions
• Title not available (Why is that?)

This page was built for publication: Higher dimensional lattice walks: connecting combinatorial and analytic behavior

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5243172)