Séminaire SPACE Tours
Lattice paths with catastrophes: limit laws and random generationMichael Wallner (Univ. Paris 13)
Friday 24 November 2017 10:45 - Tours - Salle 1180 (Bât E2)
Résumé :
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. This is joint work with Cyril Banderier.
Liens :