Walks in the quarter plane: Kreweras' algebraic model
From MaRDI portal
(Redirected from Publication:558684)
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.
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
Cites work
- scientific article; zbMATH DE number 3653296 (Why is no real title available?)
- scientific article; zbMATH DE number 3693278 (Why is no real title available?)
- scientific article; zbMATH DE number 165064 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1300856 (Why is no real title available?)
- scientific article; zbMATH DE number 3437452 (Why is no real title available?)
- scientific article; zbMATH DE number 3236503 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3390084 (Why is no real title available?)
- A probabilistic method for lattice path enumeration
- A structured computer system model
- An analytical method in the theory of two-dimensional positive random walks
- Analytic models and ambiguity of context-free languages
- Basic analytic combinatorics of directed lattice paths
- Counting Walks in the Quarter Plane
- D-finite power series
- Differentiably finite power series
- Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels
- Generating functions for generating trees
- Linear recurrences with constant coefficients: The multivariate case
- Singularity Analysis of Generating Functions
- The ballot problem with three candidates
- The diagonal of a D-finite power series is D-finite
- Topics in the Constructive Theory of Countable Markov Chains
- Two Parallel Queues Created by Arrivals with Two Demands I
- Two coupled processors: The reduction to a Riemann-Hilbert problem
- Two parallel processors with coupled inputs
- Walks confined in a quadrant are not always D-finite
- Walks on the slit plane
- Walks on the slit plane: Other approaches
Cited in
(62)- Walks avoiding a quadrant and the reflection principle
- Full asymptotic expansion for orbit-summable quadrant walks and discrete polyharmonic functions
- Promotion of Kreweras words
- Counting coloured planar maps
- Computer algebra in the service of enumerative combinatorics
- Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models
- Kernel method and linear recurrence system
- Survival time of a heterogeneous random walk in a quadrant
- The kernel method tail asymptotics analytic approach for stationary probabilities of two-dimensional queueing systems
- On the set of zero coefficients of a function satisfying a linear differential equation
- Non-D-finite excursions in the quarter plane
- Exact solutions of lattice polymer models
- Classifying lattice walks restricted to the quarter plane
- Asymptotics of lattice walks via analytic combinatorics in several variables
- Counting quadrant walks via Tutte's invariant method (extended abstract)
- The complete generating function for Gessel walks is algebraic
- The quasi-holonomic ansatz and restricted lattice walks
- Walks with small steps in the 4D-orthant
- Percolation on Triangulations: A Bijective Path to Liouville Quantum Gravity
- Kernel method and system of functional equations
- Two non-holonomic lattice walks in the quarter plane
- Combinatorics meets potential theory
- Counting colored planar maps: algebraicity results
- Waiting times in classical priority queues via elementary lattice path counting
- A human proof of Gessel's lattice path conjecture
- Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
- Counting Walks in the Quarter Plane
- On the nature of four models of symmetric walks avoiding a quadrant
- Enumeration of bilaterally symmetric 3-noncrossing partitions
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- Walks in the quarter plane: analytic approach and applications
- Square lattice walks avoiding a quadrant
- scientific article; zbMATH DE number 7651047 (Why is no real title available?)
- On walks avoiding a quadrant
- Hypergeometric expressions for generating functions of walks with small steps in the quarter plane
- ANISOTROPIC STEP, SURFACE CONTACT, AND AREA WEIGHTED DIRECTED WALKS ON THE TRIANGULAR LATTICE
- New steps in walks with small steps in the quarter plane: series expressions for the generating functions
- Exact tail asymptotics in a priority queue -- characterizations of the preemptive model
- Bijective counting of Kreweras walks and loopless triangulations
- Exact tail asymptotics for a three-dimensional Brownian-driven tandem queue with intermediate inputs
- Lattice path counting and the theory of queues
- Rényi entropy of the totally asymmetric exclusion process
- Counting walks in a quadrant: a unified approach via boundary value problems
- Quarter-plane lattice paths with interacting boundaries: Kreweras and friends
- A solution to the tennis ball problem
- Algebraic random walks in the setting of symmetric functions
- Combinatorics arising from lax colimits of posets
- Families of prudent self-avoiding walks
- Walks reaching a line
- Promotion of Kreweras words
- An elementary solution of Gessel's walks in the quadrant
- Higher dimensional lattice walks: connecting combinatorial and analytic behavior
- Permutations sortable by two stacks in parallel and quarter plane walks
- Random walks in cones
- Tail asymptotics for a generalized two-demand queueing model -- a kernel method
- Signed enumeration of upper-right corners in path shuffles
- Walks confined in a quadrant are not always D-finite
- Rare event asymptotics for a random walk in the quarter plane
- scientific article; zbMATH DE number 1552344 (Why is no real title available?)
- On 3-dimensional lattice walks confined to the positive octant
- Exact solution of some quarter plane walks with interacting boundaries
- Counting walks with large steps in an orthant
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)
