Limit laws for lattice paths with catastrophes

Abstract

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths or random walks, it is like having the possibility of jumping from any altitude to zero. Because of this we call them "lattice paths with catastrophes". These objects have the interesting feature that they do not have the same intuitive probabilistic behaviour like classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory). In this talk we will quantify some relations between these two types of paths. We give a bijection with some other lattice paths, show a link with a continued fraction expansion, and prove several formulae for related combinatorial structures conjectured in the On-line Encyclopedia of Integer Sequences. Our main tools will be the kernel method and asymptotic transfer theorems from analytic combinatorics. With these we solve the enumeration problem and derive several limit laws for parameters like the number of returns to zero or the size of an average catastrophe. We end with some considerations on uniform random generation.