Two non-holonomic lattice walks in the quarter plane

DOI10.1016/J.TCS.2009.04.008MaRDI QIDQ837153zbMATH OpenOpenAlexFDO

Authors Marni Mishna, Andrew Rechnitzer

Publication date 10 September 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

enumerationgenerating functionsrandom walkskernel methodP-recursiveholonomicD-finite

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Exact enumeration problems, generating functions (05A15)

Abstract: We present two classes of random walks restricted to the quarter plane whose generating function is not holonomic. The non-holonomy is established using the iterated kernel method, a recent variant of the kernel method. This adds evidence to a recent conjecture on combinatorial properties of walks with holonomic generating functions. The method also yields an asymptotic expression for the number of walks of length n.

Recommendations

• Classifying lattice walks restricted to the quarter plane
• On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane
• Walks confined in a quadrant are not always D-finite
• Counting Walks in the Quarter Plane
• Non-D-finite excursions in the quarter plane

Cites work

• scientific article; zbMATH DE number 1300856 (Why is no real title available?)
• Basic analytic combinatorics of directed lattice paths
• Classifying lattice walks restricted to the quarter plane
• D-finite power series
• Differentiably finite power series
• Haruspicy 2: The anisotropic generating function of self-avoiding polygons is not D-finite
• Indicators of solvability for lattice models
• Lattice animals and heaps of dimers
• On partitions avoiding 3-crossings
• Partially directed paths in a wedge
• Solvability of Some Statistical Mechanical Systems
• The kernel method: a collection of examples
• Walks confined in a quadrant are not always D-finite
• Walks in the quarter plane: Kreweras' algebraic model

Cited in

(49)

• The steep-bounce zeta map in parabolic Cataland
• On walks avoiding a quadrant
• Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
• Non-D-finite walks in a three-quadrant cone
• Harmonic functions for singular quadrant walks
• Walks avoiding a quadrant and the reflection principle
• Generating functions and duality for non-crossing walks on a plane graph
• The complete generating function for Gessel walks is algebraic
• Combinatorics meets potential theory
• The quasi-holonomic ansatz and restricted lattice walks
• Non-D-finite excursions in the quarter plane
• Counting quadrant walks via Tutte's invariant method
• On 3-dimensional lattice walks confined to the positive octant
• Random walks with drift inside a pyramid: convergence rate for the survival probability
• Classifying lattice walks restricted to the quarter plane
• An elementary solution of Gessel's walks in the quadrant
• Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
• Square lattice walks avoiding a quadrant
• Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
• Infinite orders and non-D-finite property of 3-dimensional lattice walks
• Continued Classification of 3D Lattice Walks in the Positive Octant
• A combinatorial understanding of lattice path asymptotics
• On the nature of the generating series of walks in the quarter plane
• Selected non-holonomic functions in lattice statistical mechanics and enumerative combinatorics
• Asymptotics for a variant of the Mittag-Leffler function
• Walks in the quarter plane: analytic approach and applications
• Singularity analysis via the iterated kernel method
• On the functions counting walks with small steps in the quarter plane
• New steps in walks with small steps in the quarter plane: series expressions for the generating functions
• On the nature of four models of symmetric walks avoiding a quadrant
• Asymptotics of lattice walks via analytic combinatorics in several variables
• Counting quadrant walks via Tutte's invariant method (extended abstract)
• Hopf dreams and diagonal harmonics
• The compensation approach for walks with small steps in the quarter plane
• INTERACTING QUARTER-PLANE LATTICE WALK PROBLEMS: SOLUTIONS AND PROOFS
• On the kernel curves associated with walks in the quarter plane
• Enumeration of walks with small steps avoiding a quadrant
• Walks in the quarter plane: genus zero case
• Walks obeying two-step rules on the square lattice: full, half and quarter planes
• On differentially algebraic generating series for walks in the quarter plane
• Conditions for some non stationary random walks in the quarter plane to be singular or of genus 0
• Exact solution of two classes of prudent polygons
• Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
• Lattice walks in the octant with infinite associated groups
• Computer algebra in the service of enumerative combinatorics
• Families of prudent self-avoiding walks
• Counting walks in a quadrant: a unified approach via boundary value problems
• Counting colored planar maps: algebraicity results
• Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models

This page was built for publication: Two non-holonomic lattice walks in the quarter plane

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