Weighted Dyck paths for nonstationary queues

Gianmarco Bet, Jori Selen, Alessandro Zocca

Research output: Contribution to JournalArticleAcademic

34 Downloads (Pure)

Abstract

We consider a model for a queue in which only a fixed number $N$ of customers can join. Each customer joins the queue independently at an exponentially distributed time. Assuming further that the service times are independent and follow an exponential distribution, this system can be described as a two-dimensional Markov process on a finite triangular region $\mathfrak S$ of the square lattice. We interpret the resulting random walk on $\mathfrak S$ as a Dyck path that is weighted according to some state-dependent transition probabilities that are constant along one axis, but are rather general otherwise. We untangle the resulting intricate combinatorial structure by introducing appropriate generating functions that exploit the recursive structure of the model. This allows us to derive a fully explicit expression for the probability density function of the number of customers served in any busy period (equivalently, of the length of any excursion of the Dyck path above the diagonal) as a weighted sum with alternating sign over a certain subclass of Dyck paths, whose study is of independent interest.
Original languageEnglish
Article number03424
Pages (from-to)1-15
Number of pages15
JournalarXiv
Publication statusPublished - 9 Feb 2020

Bibliographical note

14 pages, 3 figures

Keywords

  • math.PR
  • math.CO

Fingerprint

Dive into the research topics of 'Weighted Dyck paths for nonstationary queues'. Together they form a unique fingerprint.

Cite this