Walks in the quarter plane: Kreweras' algebraic model
From MaRDI portal
Publication:558684
DOI10.1214/105051605000000052zbMATH Open1064.05010arXivmath/0401067OpenAlexW2034324189MaRDI QIDQ558684FDOQ558684
Authors: Mireille Bousquet-Mélou 
Publication date: 13 July 2005
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Abstract: We consider planar lattice walks that start from (0,0), remain inthe first quadrant i, j >= 0, and are made of three types of steps: North-East, West and South. These walks are known to have remarkable enumerative and probabilistic properties: -- they are counted by nice numbers (Kreweras 1965), -- the generating function of these numbers is algebraic (Gessel 1986), -- the stationary distribution of the corresponding Markov chain in the quadrant has an algebraic probability generating function (Flatto and Hahn 1984). These results are not well understood, and have been established via complicated proofs. Here we give a uniform derivation of all of them, whichis more elementary that those previously published.We then go further by computing the full law of the Markov chain. This helps to delimit the border of algebraicity: the associated probability generating function is no longer algebraic, unless a diagonal symmetry holds. Our proofs are based on the solution of certain functional equations,which are very simple to establish. Finding purely combinatorial proofs remains an open problem.
Full work available at URL: https://arxiv.org/abs/math/0401067
Recommendations
- Walks in the quarter plane: genus zero case
- Walks in the quarter plane: analytic approach and applications
- scientific article; zbMATH DE number 7651047
- Counting Walks in the Quarter Plane
- On the kernel curves associated with walks in the quarter plane
- Classifying lattice walks restricted to the quarter plane
- On the nature of the generating series of walks in the quarter plane
- scientific article; zbMATH DE number 1300856
- An elementary solution of Gessel's walks in the quadrant
- On the nature of four models of symmetric walks avoiding a quadrant
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Exact enumeration problems, generating functions (05A15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Singularity Analysis of Generating Functions
- Two coupled processors: The reduction to a Riemann-Hilbert problem
- Differentiably finite power series
- Title not available (Why is that?)
- Topics in the Constructive Theory of Countable Markov Chains
- 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
- Counting Walks in the Quarter Plane
- D-finite power series
- Title not available (Why is that?)
- Two Parallel Queues Created by Arrivals with Two Demands I
- Title not available (Why is that?)
- An analytical method in the theory of two-dimensional positive random walks
- A probabilistic method for lattice path enumeration
- The diagonal of a D-finite power series is D-finite
- A structured computer system model
- Analytic models and ambiguity of context-free languages
- Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels
- Title not available (Why is that?)
- Walks on the slit plane
- Title not available (Why is that?)
- Title not available (Why is that?)
- Two parallel processors with coupled inputs
- Title not available (Why is that?)
- Walks on the slit plane: Other approaches
- The ballot problem with three candidates
Cited In (56)
- Counting Walks in the Quarter Plane
- ANISOTROPIC STEP, SURFACE CONTACT, AND AREA WEIGHTED DIRECTED WALKS ON THE TRIANGULAR LATTICE
- Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
- Exact tail asymptotics in a priority queue -- characterizations of the preemptive model
- Bijective counting of Kreweras walks and loopless triangulations
- Lattice path counting and the theory of queues
- The complete generating function for Gessel walks is algebraic
- Title not available (Why is that?)
- The quasi-holonomic ansatz and restricted lattice walks
- Combinatorics meets potential theory
- Asymptotic lattice path enumeration using diagonals
- The kernel method tail asymptotics analytic approach for stationary probabilities of two-dimensional queueing systems
- Non-D-finite excursions in the quarter plane
- On 3-dimensional lattice walks confined to the positive octant
- Two non-holonomic lattice walks in the quarter plane
- Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior
- Exact solution of some quarter plane walks with interacting boundaries
- Classifying lattice walks restricted to the quarter plane
- Exact tail asymptotics for a three-dimensional Brownian-driven tandem queue with intermediate inputs
- An elementary solution of Gessel's walks in the quadrant
- Square lattice walks avoiding a quadrant
- Rare event asymptotics for a random walk in the quarter plane
- Enumeration of bilaterally symmetric 3-noncrossing partitions
- Rényi entropy of the totally asymmetric exclusion process
- Counting coloured planar maps
- Exact solutions of lattice polymer models
- Permutations sortable by two stacks in parallel and quarter plane walks
- Walks confined in a quadrant are not always D-finite
- Survival time of a heterogeneous random walk in a quadrant
- Asymptotics of lattice walks via analytic combinatorics in several variables
- Walks with small steps in the 4D-orthant
- On the nature of four models of symmetric walks avoiding a quadrant
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- New steps in walks with small steps in the quarter plane: series expressions for the generating functions
- Percolation on Triangulations: A Bijective Path to Liouville Quantum Gravity
- Combinatorics arising from lax colimits of posets
- Walks reaching a line
- Title not available (Why is that?)
- Random walks in cones
- Kernel method and system of functional equations
- Promotion of Kreweras words
- Waiting times in classical priority queues via elementary lattice path counting
- Quarter-plane lattice paths with interacting boundaries: Kreweras and friends
- Kernel method and linear recurrence system
- A solution to the tennis ball problem
- Families of prudent self-avoiding walks
- Tail asymptotics for a generalized two-demand queueing model -- a kernel method
- Counting walks in a quadrant: a unified approach via boundary value problems
- Counting colored planar maps: algebraicity results
- A human proof of Gessel's lattice path conjecture
- Counting walks with large steps in an orthant
- Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models
- On the set of zero coefficients of a function satisfying a linear differential equation
- Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
- Promotion of Kreweras words
- Computer algebra in the service of enumerative combinatorics
This page was built for publication: Walks in the quarter plane: Kreweras' algebraic model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q558684)
